Consider a simple, undirected graph $G$ with n vertices and $m$ edges. Let $d(v)$ denote the degree of vertex v in $G$. The degree distribution of $G$ is the probability distribution $P(k)$ that a randomly selected vertex has degree $k$. Which of the following statements is true regarding the degree distribution of a simple graph?

a) For any simple graph with $n$ vertices and $m$ edges, the sum of the degrees of all vertices is equal to $n+m$.

b) In any simple graph, the degree distribution $P(k)$ is always uniform, meaning all vertices have the same degree.

c) In a simple graph, the degree distribution $P(k)$ must sum to 1 when considering all possible degrees $k$.

d) If a simple graph is connected, its degree distribution must be a normal distribution.

e) None of above

Which of the following statements about evolving networks is FALSE?

a) In the Barabási–Albert (BA) model, new nodes are added to the network with a preference for connecting to high-degree nodes.

b) The Erdős-Rényi random network model grows by adding nodes over time, similar to the BA model.

c) In evolving networks, the degree distribution can change as new nodes and edges are added.

d) In the BA model, the probability of a new node connecting to existing nodes is uniform across all nodes.

e) None of the above. 

Consider a network modeled by a connected, undirected graph $G = (V, E)$, where each vertex $v_i\in \mathrm{V\; represents\; a\; node,\; and\; each\; edge }$$(v_i, v_j) \in E$ represents a connection between nodes.

 Let $x_i(\mathrm{t)\; be\; the\; state\; of\; vertex }$$v_i$at time t, which evolves according to the following ordinary differential equation (ODE): 

This equation models the change in state of node $v_i$as a result of interactions with its neighbors.

Which of the following statements is true regarding the behavior of this system over time?

(a) The system represents a diffusion process, and all nodes will eventually reach the same state.

(b) The system will exhibit chaotic behavior for sufficiently large graphs.

(c) The solution to the system depends on the initial states of only the boundary nodes.

(d) The state of each node will remain constant over time if it starts in the same state as its neighbors.

(e) The system represents a decay process where all node states approach zero over time.

Original idea by Thalia Anastácia da Silva Araujo.

 Consider an undirected graph G=(V,E), where V={A,B,C,D,E,F} and the edges are E={(A,B),(A,C),(B,D),(C,D),(C,E),(D,F),(E,F)}. Starting from vertex A, which of the following sequences represents the correct order of vertex visits by the BFS? 

a) A,B,C,D,E,F

b) A,C,B,E,D,F

c)A,B,C,D,F,E

d)A,C,B,D,F,E

e) A,B,C,E,D,F

Original idea by Thalia Anastácia da Silva Araujo

 

That's an X-ray of a very worried person. This is Kenzo. Kenzo is very worried about his research future in the graphs field. So worried that the doctors could see a graph of his thoughts! Seizing the opportunity, the doctors were also a great admirer of graphs and said to Kenzo: 

- "I have the results of your brain exams, Kenzo...I have news... a good and a not so good one. Which of them you want me to tell first?"
- "The good one first, please..."

- "The good one is that we found a graph in your brain that we could solve it and have some fun!" 

- "That sounds okay..! So what would be the other one then?"

- "This graph helped us to find a tumor in your brain! (😃)"

- "... a tumor?"

- "...Yes, a tumor."

- "(😐)"

- "(😅)"

Below we have Kenzo's brain graph. Considering the weights here helped the doctor to find the tumor, then the weights represents intensity or abnormal activity levels. Which of the statements the doctor and Kenzo conclude are true? 

            I. The graph is directed, weighted and its adjacency matrix has order 6, its last element is 0, it has one strongly connected component, the trace of the adjacency matrix is 0 and the total degree is equal to 68.3 ;

            II. The graph is directed, weighted and the adjacency matrix is squared, its last element is 0, it has two strongly connected component, the adjacency is symmetric and the total degree is equal to 68.3;

            III. Nodes A and B are In-components and the tumor is in the node's E neighborhood;

            IV. The element a_{35}  = 1.3, that's a complete graph and the node D is a tumor;%3CmxGraphModel%3E%3Croot%3E%3CmxCell%20id%3D%220%22%2F%3E%3CmxCell%20id%3D%221%22%20parent%3D%220%22%2F%3E%3CmxCell%20id%3D%222%22%20value%3D%222%26lt%3Bspan%20style%3D%26quot%3Bcolor%3A%20rgba(0%2C%200%2C%200%2C%200)%3B%20font-family%3A%20monospace%3B%20font-size%3A%200px%3B%20text-align%3A%20start%3B%20text-wrap%3A%20nowrap%3B%26quot%3B%26gt%3B%253CmxGraphModel%253E%253Croot%253E%253CmxCell%2520id%253D%25220%2522%252F%253E%253CmxCell%2520id%253D%25221%2522%2520parent%253D%25220%2522%252F%253E%253CmxCell%2520id%253D%25222%2522%2520value%253D%25221%2522%2520style%253D%2522text%253Bhtml%253D1%253Balign%253Dcenter%253BverticalAlign%253Dmiddle%253BwhiteSpace%253Dwrap%253Brounded%253D0%253Brotation%253D-70%253B%2522%2520vertex%253D%25221%2522%2520parent%253D%25221%2522%253E%253CmxGeometry%2520x%253D%2522295%2522%2520y%253D%2522204.63%2522%2520width%253D%252260%2522%2520height%253D%252230%2522%2520as%253D%2522geometry%2522%252F%253E%253C%252FmxCell%253E%253C%252Froot%253E%253C%252FmxGraphModel%253E%26lt%3B%2Fspan%26gt%3B%26lt%3Bspan%20style%3D%26quot%3Bcolor%3A%20rgba(0%2C%200%2C%200%2C%200)%3B%20font-family%3A%20monospace%3B%20font-size%3A%200px%3B%20text-align%3A%20start%3B%20text-wrap%3A%20nowrap%3B%26quot%3B%26gt%3B%253CmxGraphModel%253E%253Croot%253E%253CmxCell%2520id%253D%25220%2522%252F%253E%253CmxCell%2520id%253D%25221%2522%2520parent%253D%25220%2522%252F%253E%253CmxCell%2520id%253D%25222%2522%2520value%253D%25221%2522%2520style%253D%2522text%253Bhtml%253D1%253Balign%253Dcenter%253BverticalAlign%253Dmiddle%253BwhiteSpace%253Dwrap%253Brounded%253D0%253Brotation%253D-70%253B%2522%2520vertex%253D%25221%2522%2520parent%253D%25221%2522%253E%253CmxGeometry%2520x%253D%2522295%2522%2520y%253D%2522204.63%2522%2520width%253D%252260%2522%2520height%253D%252230%2522%2520as%253D%2522geometry%2522%252F%253E%253C%252FmxCell%253E%253C%252Froot%253E%253C%252FmxGraphModel%253E%26lt%3B%2Fspan%26gt%3B%22%20style%3D%22text%3Bhtml%3D1%3Balign%3Dcenter%3BverticalAlign%3Dmiddle%3BwhiteSpace%3Dwrap%3Brounded%3D0%3Brotation%3D-10%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22343.74%22%20y%3D%22160%22%20width%3D%2260%22%20height%3D%2230%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3C%2Froot%3E%3C%2FmxGraphModel%3E

(A) I., III. and IV. are true.

(B) I. and III. are true.

(C) Only II. is true.

(D) Only IV. is true.

(E) All of the statements are false.

Original idea by: Thalia Anastácia da Silva Araujo

How does Depth-First Search (DFS) help in detecting cycles in a directed graph? 

Which of the alternatives best describes the DFS process?

(A) DFS detects cycles by tracking the nodes in the current recursion stack. If a node is revisited while still in the stack, it indicates a backward edge and therefore a cycle in the graph.

(B) DFS detects cycle by tracking the edges in the current graph. If an edge is created, it indicates a cycle in the graph.

(C) DFS detects cycle by tracking the nodes in the current stack. If a node is visited, it indicates a cycle in the graph.

(D) DFS does not detect cycles.

(E) None of the above.