# Todai Entrance Exam: Subject 2013 – Problem 3

**(1)**

Skip.

**(2)**

The adjacency matrix representation uses 36 memory units. The adjacency list representation uses 20 memory units. Therefore, the adjacency matrix representation uses more memory space than the list representation.

**(3)**

Let be the number of edges. The adjacency matrix representation uses memory units while the adjacency list representation uses memory units ( is the number of vertices pointing to at least one other vertice, if and then there is no way the graph satisfies the condition, if then the graph is connected). So when , both representations require the same size of memory space.

Here we use the pigeonhole principle. Let’s assume that the graph is disconnected and parted into 2 subgraphs. The first subgraph has vertices with maximum edges, the second subgraph has vertices with maximum edges. Then the maximum number of edge in this case is:

attains maximum value at . It is easy to see in this case that if the first subgraph is further biparted into 2 other subgraphs A and B then the sum of number of edges of A and B will be less than .

When the memory space condition is obtained, , so the graph must be weakly connected.

**(4)**

Skip.

**(5)**

GetCycle(Graph G)

- foreach { v.setMark(UNVISITED) }
- foreach {
- if (v.getMark() == UNVISITED) {
- nodelist, iscycle = DFS(G, v)
- if (iscycle == TRUE) return nodelist

- }

- if (v.getMark() == UNVISITED) {
- }
- return 0

DFS(Graph G, Vertex v)

- v.setMark(VISITED)
- nodelist = [v]
- iscycle = FALSE
- foreach {
- if (w.getMark() == UNVISITED) {
- subnodelist, subiscycle = DFS(G, w)
- if (subiscycle == TRUE) {
- nodelist.concat(subnodelist)
- iscycle = subiscyle
- break

- }

- else {
- iscycle = TRUE
- nodelist = [v, w]
- break

- }

- if (w.getMark() == UNVISITED) {
- }
- return nodelist, iscycle