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 E be the number of edges. The adjacency matrix representation uses N^{2} memory units while the adjacency list representation uses 2(E - N_{E}) + N_{E} memory units (1 \leq N_{E} \leq N is the number of vertices pointing to at least one other vertice, if N_{E} = 0 and N > 1 then there is no way the graph satisfies the condition, if N = 1 then the graph is connected). So when E = \frac{1}{2}(N^{2} + N_{E}), 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 k vertices with maximum k^{2} edges, the second subgraph has N - k vertices with maximum (N - k)^{2} edges. Then the maximum number of edge in this case is:

    \[ f(k) = (N - k)^{2} + k^{2} \]

f(k) attains maximum value \frac{N^{2}}{2} at k = \frac{N}{2}. 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 k^{2}.

When the memory space condition is obtained, E = \frac{1}{2}(N^{2} + N_{E}) > \frac{N^{2}}{2}, so the graph must be weakly connected.

(4)

Skip.

(5)

GetCycle(Graph G)

  • foreach v \in V { v.setMark(UNVISITED) }
  • foreach v \in V {
    • if (v.getMark() == UNVISITED) {
      • nodelist, iscycle = DFS(G, v)
      • if (iscycle == TRUE) return nodelist
    • }
  • }
  • return 0

DFS(Graph G, Vertex v)

  • v.setMark(VISITED)
  • nodelist = [v]
  • iscycle = FALSE
  • foreach (v, w) \in E {
    • 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
    • }
  • }
  • return nodelist, iscycle

Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *