Questões

 Questões para o quiz da matéria de Algoritmos em Grafos em 2025S2:

Scale-free Network Question

Consider two information dissemination networks: Network A represents the spread of a viral rumor on the internet, where a few influencers are responsible for most of the shares. Network B is an emergency phone network of a government agency, designed so that each operator connects to a specific and limited number of other operators in a redundant way. Which scenario best describes the vulnerability of each network?

A) Both networks are highly vulnerable to the random removal of their members.
B) The rumor network (A) is robust to censorship attempts targeting the super-spreaders, but the emergency network (B) would fail if any operator were removed.
C) The emergency network (B) is overall more fragile, since the removal of a single operator causes the collapse of the entire system.
D) The rumor network (A) would be little affected if thousands of random people stopped sharing, but would be severely disrupted if the few super-spreaders were blocked. The emergency network (B) degrades more consistently with the removal of any operator.
E) None of the above

Original ideia by: Lademir Junior

Graph theory question

Let G = (V, E) be a complete (A, B)-bipartite graph, such that the set of vertices of G is partitioned into two parts that have no edges between themselves.

A graph G′ is said to be k-colorable if it is possible to partition its set of vertices into at most k independent sets (that is, groups of vertices with no edges between them). Moreover, if a graph is k-colorable, then it is also (k+1)-colorable, (k+2)-colorable, and so on, since additional colors can always be assigned without breaking the coloring rules.

Using this concept and the handshaking lemma, which states that the sum of the degrees of the vertices of a graph is equal to twice the number of its edges, analyze the alternatives below.

I - A complete bipartite graph $K_{n,n}$ has $\frac{n(n-1)}{2}$ edges.

II - A complete bipartite graph $K_{n,n}$ has $n^3$ edges.

III - A complete bipartite graph $K_{n,n}$ has $n^2$ edges.

IV - A $(A,B)$-bipartite graph with $|A|=113$ and $|B|=17$ is 2-colorable.

V - A $(A,B)$-bipartite graph with $|A|=113$ and $\mathrm{\mid }B\mathrm{\mid }=\mathrm{17\; is\; 3-colorable.}$

Which of the alternatives below contains all the correct items?

A) Only II
B) III and IV
C) I and V
D) III, IV and V
E) None of the above

Original ideia by: Lademir Junior

Random Network question

What is the main discrepancy observed between the clustering coefficient of real-world networks and that predicted by the random network model?

A) The clustering coefficient in real networks is significantly lower than in random networks of comparable size and density.

B) In both types of networks, the clustering coefficient is independent of the node degree.

C) Random networks and real networks present very similar clustering coefficients, indicating a good fit of the model.

D) The clustering coefficient in real networks is much higher than the value predicted by the random model, which decreases with the network size N.

E) None of the above

Original ideia by: Lademir Junior