代写CSCI 3110、代写Java，Python编程

日期：2022-05-08 06:51

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.

1. 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

1000000 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:

1 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

2. 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)?

3. 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)

5