Problems relating to graph theory
3
votes
6answers
490 views
Alex the Truck Driver
Alex is a Truck Driver who wants to find the quickest way to deliver goods to multiple cities. He knows the distances between his destinations, but you need to write a program to help him find the ...
3
votes
3answers
162 views
Determine number of unconnected components
You are given a graph represented through an adjacency list. For example, the input
1-2 2-3 3-4 4-1
would correspond to the graph with nodes 1, 2, 3 and 4, where 1 is connected to 2, 2 is connected ...
8
votes
3answers
593 views
Score a game of Go
Scoring a Go game is a task that is not all too easy. In the past there have been several debates about how to design rules to cover all the strange corner cases that may occur. Luckily, in this task ...
7
votes
11answers
721 views
City names game
If you like, write a program which sorts cities according to the rules of city name game.
Each name of the city should start from the last letter in the previous city name. E.g. Lviv -> v -> ...
1
vote
1answer
426 views
Calculate Network Average Clustering Coefficient
The clustering coefficient of a graph (or network) is a:
measure of degree to which nodes in a graph tend to cluster together
The Wikipedia article gives a much better description of how ...
5
votes
3answers
390 views
Shortest route through a one-way system
My home town, Rhyl, has a one-way traffic system which seems to have been designed to keep people away from their destination for as long as possible. Your task, should you choose to attempt it, is to ...
4
votes
2answers
166 views
BWInf 2011, question 5: Twin towns
This is a challenge that was originally a tas for the German Bundeswettbewerb Informatik (federal competition of computer science [?]), a competition for highschool students. As opposed to the ...
12
votes
9answers
1k views
Choose Your Own Adventure
Choose Your Own Adventure books are a form of interactive literature where the reader must
make decisions that affect the outcome of the story. At certain points in the story, the
reader has multiple ...
2
votes
0answers
340 views
Traffic light synchronization problem [closed]
I'm not a 100% sure if this qualifies under this stack exchange; however, I asked this question on the stats stackexchange with no answers. I wonder if you can solve it:
Traffic light synchronization ...
9
votes
4answers
419 views
Help Mr Jones to enjoy his bicycle round-trip
Mr Jones wants to do a round-trip on his bicycle. He wants to visit several cities in arbitrary order, but his route must not cross it self, since he hates to be at the same place twice in his ...
4
votes
1answer
353 views
Shortest path in a graph
Write a program to take a graph (from either standard input or a file, your choice) and find a shortest path in the graph.
Graphs are specified using the following format:
A---S F--T
| / \ |
| / ...
