Um grande piloto de uma famosa categoria do automobilismo precisa percorrer um grafo passando por todos os "pit stops" (vértices) exatamente 1 única vez cada um, e dessa forma completar um ciclo que leva seu nome (ciclo Hamiltoniano). Dado que o grafo é o da figura abaixo, de quantas maneiras distintas esse grande piloto pode realizar essa tarefa?
a-) Mais do que 3
b-) 2
c-) 1
d-) 0
e-) N.D.A.
Ideia original de: Guilherme A. Terrell
Considere o grafo \(G\) tal que:
\(V(G)=\{A,B,C,D\}\)
\(E(G)=\{(A,B),(A,C),(A,D),(B,C),(C,D)\}\)
Qual é o número cromático do grafo de linha \(L(G)\)?
a) 5
b) 4
c) 3
d) 2
e) N.D.A.
Ideia original de: Glaymar A. França
Considere o grafo abaixo:
Quais das afirmações abaixo estão corretas?
I - O grafo acima é planar;
II - O grafo acima possui um ciclo hamiltoniano;
III - o grafo acima é euleriano;
a) I, II e III;
b) I e II;
c) II e III;
d) I e III;
e) NDA;
Ideia original de: Gabriel S. Kraszczuk
Considere as seguintes afirmações a respeito do grafo linha \(L(G)\) de um grafo \(G\) qualquer:
1) Se \(G\) é conexo, então \(L(G)\) é conexo.
2) Se \(L(G)\) é conexo, então \(G\) é conexo.
4) \(\chi'(G)=\chi(L(G))\)
8) \(K_n\) é isomorfo a \(L(K_n)\) se, e somente se, \(n=3\).
A soma das alternativas corretas é:
A) 15
B) 13
C) 10
D) 7
E) NDA
Ideia Original de: Gabriel Cruz Vitale Torkomian
Dado o contexto de grafos-linha, assinale a alternativa incorreta:
a) O grafo \( L(G) \) possui um ponto de articulação se e somente se \( G \) tem uma ponte.
b) O índice cromático de um grafo \( G \) é igual ao número cromático de \( L(G) \).
c) O grafo linha de um grafo conexo é um grafo conexo.
d) O grafo linha de uma árvore é uma árvore.
e) N.D.A.
Ideia original: Daniel Hosomi
Considere as afirmações abaixo a respeito do grafo de Petersen e assinale a alternativa correta:
I) O grafo de Petersen não é planar.
II) O grafo de Petersen possui crossing number = 2 (lembrando que o crossing number é o menor número de cruzamentos de arestas que se pode obter ao desenhar o grafo em um plano).
III) O grafo de Petersen possui um \( K_5 \) como menor.
IV) O grafo de Petersen menos um vértice é uma subdivisão do \( K_{3,3} \).
a) Apenas as afirmações I , II e III estão corretas.
b) Apenas as afirmações I, III e IV estão corretas.
c) Apenas as afirmações I, II e IV estão corretas.
d) Todas as afirmações estão corretas.
e) N.D.A.
Ideia original de: G. Michel Carvalho
Considere as seguintes afirmações:
I-) Seja G* (figura baixo) o grafo dual de um grafo conexo G. Podemos afirmar que G é o grafo casa.
