Graph Theory Question

 

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 Kn,nK_{n,n} has n(n−1)2\frac{n(n-1)}{2} edges.

II - A complete bipartite graph Kn,nK_{n,n} has n3n^3 edges.

III - A complete bipartite graph Kn,nK_{n,n} has n2n^2 edges.

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

V - A  (A,B)(A,B)-bipartite graph with ∣A∣=113|A|=113 and ∣B∣=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



Comentário do professor:

Caro Lademir, sua questão é interessante. Apesar de conter todas as definições necessárias para seu entendimento e resposta, ela aborda conceitos que não são explorados no capítulo 2 do livro utilizado. Temo que isto possa aumentar o risco de contestações, caso esta questão seja usada num teste. Para evitar problemas, prefiro deixá-la de fora do blog oficial.

Comentários

Postar um comentário

Postagens mais visitadas deste blog

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 Comentário do professor: Questão interessante, mas já temos algumas parecidas.
Leia mais

Scale-free network

 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 eme...
Leia mais