Graph Algorithms - Rafael

 Take a look at the following graphs. Graph 1: Graph 2: Graph 3: 1. If we plot the degree distribution of Graph 2 in a log-log plot, we would get a shape similar to a line. 2. For Graph 2 to keep the same number of nodes, but become connected, the probability \(p\) should be roughly 0.0038. 3. Graph 1 operates in the subcritical regime, which means it lacks a giant component. 4. Graph 3 can be accurately approximated by a Poisson Distribution. The correct statements are: a) 1 and 2. b) 1 and 4. c) 2 and 3. d) Just 3. e) None of the above. Original idea by: Rafael Brusiquesi Martins

 Consider the following graph and the subsequent statements: 1. The link ( g , a ) is a back edge when starting DFS from node  d  (alphabetical order). 2. The link ( g ,  a ) is a back edge when starting DFS from node  a  (alphabetical order). 3. The number of tree edges is the same when applying DFS from node a and from node d . 4. If we remove nodes h and i , the remaining graph will have a hamiltonian path. The correct statements are: a) 1, 3 and 4. b) 1, 2 and 3. c) 2, 3 and 4. d) Just 1 and 4. e) None of the above. Original idea by: Rafael Brusiquesi Martins

 Consider the following graph and the subsequent affirmations: 1. The graph is connected because the links (0, 1), (0, 2) and (0, 3) instersect with the links (4, 5), (4, 6) and (5, 6). 2. If we consider the components of this graph as projections of a bipartite graph, the parent bipartite graph could be: 3. The adjacency matrix of this graph can be rearranged and separated into two non-zero submatrices of size 4x4 and 3x3. The correct affirmations are: a) 1 and 2 b) 1 and 3 c) 2 and 3 d) Just 3 e) None of the above. Original idea by: Rafael Brusiquesi Martins