Ensino Superior ⇒ Grafos, Grafo Bipartido e Hamiltoniano

[brunobm2]

Olá caros amigos,

Sou estudante de física computacional e estou com problema de provar essas 2 questões se verdadeira ou falsa.

a) Os elementos de uma matriz de adjacência do [tex3]K_5[/tex3] (grafo completo com 5 vértices) são todos unitários com exceção dos elementos da diagonal principal, que são nulos.

b) O grafo bipartido completo [tex3]K_{4,\,4}[/tex3] é hamiltoniano e é também euleriano.

Agradeço desde já pela atenção.

Abraços.

[Rafa2604]

a) Os elementos de uma matriz de adjacência do [tex3]K_5[/tex3] (grafo completo com 5 vértices) são todos unitários com exceção dos elementos da diagonal principal, que são nulos.

Verdadeiro

Definição: O grafo completo de n vértices, [tex3]K_n[/tex3], é o grafo simples que contém exatamente uma aresta entre cada par de vértices distintos.

grafo1.png (3.56 KiB) Exibido 2209 vezes

Portanto, sua matriz de adjacências é dada por:
[tex3]A = \begin{pmatrix}
0 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 0 \\
\end{pmatrix}[/tex3]



b) O grafo bipartido completo [tex3]K_{4,4}[/tex3] é hamiltoniano e é também euleriano.

Verdadeiro

Definição: O grafo bipartido completo de n vértices, [tex3]K_{m,n}[/tex3], é um grafo que tem seu conjunto de vértices dividido em dois subconjuntos de m e n vértices, respectivamente. Existe uma aresta entre dois vértices se e somente se um vértice estiver no primeiro subconjunto e o outro vértice no segundo subconjunto.

grafo2.png (6.83 KiB) Exibido 2209 vezes

Teorema: Um grafo conexo, com pelo menos, dois vértices tem um ciclo euleriano se e somente se cada um de seus vértices tiver grau par.

Podemos ver que os todos os vértices do grafo K_{4,4} possuem grau de vértice igual a 4, portanto, todos os seus vértices possuem grau par.
Logo, o grafo [tex3]K_{4,4}[/tex3] é euleriano.

Teorema de Dirac: Se G for um grafo simples com n vértices com [tex3]n \geq 3[/tex3] tal que o grau de todo vértice em G seja, pelo menos, n/2, então G tem um ciclo hamiltoniano.

Como o grafo [tex3]K_{4,4}[/tex3] possui 8 vértices, então temos: [tex3]gr(v) \geq \frac{n}{2} = \frac{8}{2} \;\; \rightarrow \;\; gr(v) \geq 4[/tex3].
Como todos seus vértices possuem grau igual a 4, então temos que o grafo [tex3]K_{4,4}[/tex3] é hamiltoniano.