共计 7797 个字符，预计需要花费 20 分钟才能阅读完成。
CSCI 3110 Assignment 1 posted: 04.05.2022
Instructor: Travis Gagie due: midnight 20.05.2022
You can work in groups of up to three people. One group member should submit a copy of the
solutions on Brightspace, with all members’names and banner numbers on it; the other group
members should submit text files with all members’names and banner numbers. (Brightspace
won’t let us assign marks to people who haven’t submitted anything!) You may consult with other
people but each group should understand the solutions: after discussions with people outside the
groups, discard any notes and do something unrelated for an hour before writing up your solutions;
it’s a problem if no one in a group can explain one of their answers. For programming questions
you should submit your code, which should compile and run correctly to receive full marks.
- Write a program that takes the adjacency-list representation of an undirected graph G =
(V, E) and prints an Eulerian cycle (or non-Eulerian if no such cycle exists) in linear expected
time.
Your program should first convert each vertex’s adjacency list into a doubly-linked list (store
the pointers to the heads in an array), and add each edge in G to a map. Given an edge
e = (u, v) in E, the map should return a pointer to the list node storing v in u’s adjacency
list and a pointer to the list node storing u in v’s adjacency list. This way, you can delete e
from G in expected constant time (assuming your map is implemented reasonably well) by
deleting those two list nodes. You can use Java’s built-in Map class if you want.
Start at the beginning of the first adjacency list and walk around the graph until you get
stuck, deleting from G each edge you cross and always leaving the vertex v you’re currently
visiting by crossing the first edge remaining in v’s adjacency list. If you get stuck somewhere
other than where you started then, as we saw in the first class, G cannot be Eulerian. If you
get stuck back where you started, then the edges you’ve removed form a cycle in G. As you
go, add the label of each vertex you visit to yet another doubly-linked list, L.
For example, if G is the graph on the left below and it’s given as the the set of adjacency lists
in the center below, then you’ll start at 1 and visit 11 and 4, in that order, before returning
to 1 and getting stuck. When you get stuck, L will contain 1, 11, 4, 1, in that order; the
adjacency lists with (1, 11),(4, 11),(1, 11) deleted are shown on the right below.
Starting at the beginning of L, walk along it until you find a vertex which still has edges
incident to 11. Starting at that vertex, walk around the remainder of G until you get stuck
again, deleting edges as you cross them and inserting the labels into L as if you’d interrupted
your first walk, performed this new walk, and then finished your first walk. (Again, if you
don’t end up back where you started, then G cannot be Eulerian.) This way, L ends up
containing the labels of the vertices in a walk that combines both walks. Note that vertices
can appear several times! Eventually, each vertex will appear once in L for each incident edge
it had in G originally.
In our example above, 1 has no more edges incident to it, but 11 does. The first edge in
11’s remaining adjacency list goes to 2, the first edge in 2’s adjacency list goes to 8, the first
edge in 8’s adjacency list goes to 6, and the first edge in 6’s adjacency list — ignoring the
edge to 8 which we just crossed and deleted! — goes back to 11. After you delete the edges
(2, 11) and (6, 11), there are no more edges incident to 11, so you’re stuck. L now contains
1, 11, 2, 8, 6, 11, 4, 1 in that order. The remainder of G and the adjacency lists are shown
below; notice the missing edges are the ones you’ve crossed in your walks so far, and are the
adjacent pairs in L.
Again, walk along L until you find a vertex that has remaining incident edges. (You don’t
need to go back to the beginning of L, or even backward in L; indeed, doing so could make
you take more than linear time.) Again, walk around the remainder of G, deleting edges and
inserting vertices’labels into L. In our example, now you start at 2 — because it’s the next
vertex with incident edges in L, not because it’s the such one in numerical order! — and
walk to 9, then to 5, then to 4, then back to 2. When you’re finished this walk, L contains
1, 11, 2, 9, 5, 4, 2, 8, 6, 11, 4, 1.
Keep going like this until there are no vertices in L with remaining incident edges. (You only
ever need to walk forward in L. Why?) If you ever get stuck somewhere you shouldn’t be, G
cannot be Eulerian because some vertex must have odd degree, and if there are still edges left
when you’re done, G cannot be Eulerian because it isn’t connected. With our example, after
another walk, L should contain 1, 11, 2, 9, 4, 7, 5, 3, 9, 5, 4, 2, 8, 6, 11, 4, 1; after yet another walk,
L should contain 1, 11, 2, 9, 4, 7, 5, 3, 8, 10, 3, 9, 5, 4, 2, 8, 6, 11, 4, 1, which represents an Eulerian
cycle of G.
The format of the input should be as follows: first, a line containing a number n between 2 and - indicating the size of the vertex set V = {1, . . . , n} and a number m indicating the
2
total number of edges (so it’s easy to set up the map); then n lines containing the adjacency
lists. Your output should be a list of the vertices’labels as they are visited in an Eulerian
cycle of G, or non-Eulerian if G is not Eulerian.
To make it easy to read the file, the first line will say n = … m = …, with the dots
replaced by the appropriate numbers, and the ith adjacency list will start with i, a close
parenthesis, the degree of vertex i, a colon, and then the adjacency list.
INPUT:
n = 11 m = 19
1) 2: 11 4
2) 4: 8 9 11 4
3) 4: 5 9 8 10
4) 6: 1 2 11 5 9 7
5) 4: 4 9 7 3
6) 2: 8 11
7) 2: 4 5
8) 4: 6 2 10 3
9) 4: 2 5 4 3
10) 2: 8 3
11) 4: 4 2 6 1
OUTPUT: - 11 2 9 4 7 5 3 8 10 3 9 5 4 2 8 6 11 4 1
INPUT:
n = 3 m = 2
1) 1: 2
2) 2: 1 3
3) 1: 2
OUTPUT:
non-Eulierian
You can get part marks for well-documented code even if it doesn’t work. You may get no
marks (and possibly a referral to the AIO committee) for code that works but you’ve clearly
downloaded from somewhere without understanding it.
Notice I’ve changed the input format to make it easier to read! Also, I’ve
uploaded to BrightSpace a .h file I wrote and a .c file with the code for
the basic subroutines; you just have to write the main .c file, and maybe
translate it into Java if that’s what Mimir wants. (The sample inputs on
BrightSpace are not our actual test cases.)
3 - Write a program that takes the adjacency-list representation of an undirected graph G =
(V, E) and prints Hamiltonian if G is Hamiltonian and non-Hamiltonian otherwise. Your
input format should be the same as for the first question. Follow the pseudo-code below (but
note, for example, that you might have problems declaring visited before you read n). Your
program won’t be polynomial time — so it won’t handle big graphs — but try to make it as
efficient as you can (without knocking yourself out over it).
Notice that you don’t need a dictionary after all — just an array
adjacentTo1[1..n]!
int n is the number of vertices
int degree[1..n] stores the degrees of the vertices
int **list is an array of arrays storing the adjacency lists
boolean visited[1..n] is initially all false
boolean adjacentTo1[1..n] says whether a vertex is adjacent to vertex 1
void main {
read the input
visited[1] = true
if finishHamCycle(1, 1) == true
print “Hamiltonian”
else
print “non-Hamiltonian”
end if
return
}
boolean finishHamCycle (vertex u, int visitedCount) {
if visitedCount == n and adjacentTo1[u]
return true
end if
for v in u’s adjacency list
if visited[v] == false
visited[v] = true
if finishHamCycle(v, visitedCount + 1) == true
return true
end if
visited[v] = false
end if
end for
return false
}
4
How can you modify your program so that it actually prints a Hamiltonian cycle? How can
you modify it so that it counts the number of distinct Hamiltonian cycles (remembering not
to count the same cycle twice, once for each direction)? - We heard in class that in a planar graph on n vertices you can always find a separator of size
at most 2√
n whose removal leaves no connected component of size more than 2n/3, and we
discussed how you can use that fact to speed up counting 3-colourings of planar graphs.
It’s not so easy to use a separator like that to speed up counting Hamiltonian cycles, but
suppose you’re lucky and you can find a separator consisting of only two vertices whose removal
leaves no connected component of size more than 2n/3 (and that you can keep doing this
recursively). How can you use these really small separators to speed up counting Hamiltonian
cycles?
For example, there is such a small separator for the mainland of Nova Scotia: Hants and
Lunenberg (or Hants and Halifax, or. . .). Notice the graph for all of Nova Scotia is not
Hamiltonian because it’s not connected — Cape Breton Island is an island — and you can
get to Cumberland only through Colchester. If we want to count the Haliltonian cycles of
Nova Scotia ignoring Cape Breton Island and Cumberland, though, then you can break it
down into counting the Hamiltonian cycles in the two graphs shown below. Why and how?
(Notice Hants and Lunenberg are in both graphs!)
Hants Lunenberg Halifax Colchester Guysborough Pictou Antigonish KingsQueens Annapolis Digby Yarmouth Shelburne southern mainland northern mainland Hants Lunenberg KingsQueens Annapolis Digby Yarmouth Shelburne Hants Lunenberg Halifax Colchester Guysborough Pictou Antigonish (except Cumberland)
正文完
