Matemática Discreta

3- Desenhe um grafo com quatro nós de graus 2, 3, 3 e 4, respectivamente, ou explique por que não existe tal grafo.

R-

4- Desenhe um grafo com quatro nós de graus 2, 3, 3 e 3, respectivamente, ou explique por que não existe tal grafo.

R-

Notemos que não é possível desenhar o grafo pedido.

Pois, os nós 1 e 4 já possuem dois nós, se ligarmos um ao outro ficarão com grau 3, e mesmo que façamos um laço no nó 2 ou no 4, eles ficariam com grau 4.

6- Um grafo completo é regular? Justifique.

R- Um grafo completo é aquele em que dois nós distintos quaisquer são adjacentes, enquanto o grafo regular os nós possuem o mesmo grau. Portanto, concluímos que se um grafo é inicialmente completo e todos os seus nós são adjacentes, ou, estão ligados entre si, então este também será regular.

7- Um grafo bipartido completo é regular? Justifique.

R- Um grafo bipartido completo é aquele que seus nós podem ser divididos em dois conjuntos disjuntos não vazios e tais que dois nós são adjacentes se, e somente se, um deles pertence a e o outro pertence a . Se | |=m e | |=n, o grafo bipartido é denotado por , onde m pode ser diferente de n, por exemplo, . Já um grafo regular é um grafo onde cada vértice tem o mesmo número de adjacências, ou seja, mesmo grau ou valência.

Desta forma verificamos que o grau G de um grafo bipartido permite grau K distintos, portanto a resposta é não, um grafo bipartido completo não é necessiariamente um grafo regular. Confirma-se no grafo abaixo.

10- Os grafos (a) e (b) são isomorfos? Demonstre que são isomorfos, se o forem; caso contrário, justifique porque não o são.

R- Os grafos (a) e (b) não são isomorfos, pois, apesar de ambos terem 6 nós e cada nó ter grau 3, no grafo (b) existe ciclo de tamanho 3 e no grafo (a) não. Para existir um ciclo de grau 3 em um grafo, é preciso que dois dos adjacentes de um nó sejam adjacentes entre si. No grafo (b), os nós ‘d’ e ‘e’ são adjacentes de ‘a’ e também são adjacentes entre si.

13- Os grafos abaixo são isomorfos? Justifique.

Os grafos não são isomormos. Embora possuam algumas estruturas semelhantes: dez arestas, oito nós, quatro nós de grau 3 e dois de grau 2, o isomorfismo não se confirma.

Percebe-se que há diferença nos seus ciclos, por exemplo, no primeiro há dois ciclos de grau 6, o que não verificamos no segundo grafo.

14-Os grafos abaixo são isomorfos? Justifique.

R- Comparemos seus elementos:

Elemento Grafo 1 Grafo 2

Nós 8 8

Arestas 12 12

Ciclos de grau 3 3 não possui

Pela quantidade de ciclos podemos afirmar que os grafos não são isomorfos.

16-Na questão anterior pode-se dizer que a recíproca é verdadeira?

R- A questão 15 diz: Prove que se dois grafos são isomorfos, então possuem o mesmo número de vértices e o mesmo número de arestas.

De acordo com a questão 14 podemos afirmar que a recíproca não verdadeira, pois naquele exercício os grafos possuem o mesmo números de vértices e o mesmo número de arestas, isso não garante o isomorfismo. Há outras características avaliadas no isomorfismo, como: existência e quantidade de arestas paralelas, ciclos e outros elementos.

23- Se todos os nós de um grafo planar simples e conexo têm grau 4 e se o número de arcos é 12, em quantas regiões ele divide o plano?

R- Para desenhar o grafo precisamos encontrar a quantidade de nós, para em seguida encontrar a quantidade de regiões.

Pela fórmula de Euler encontraremos a quantidade de nós, pois temos a quantidade de arestas.

Grafo encontrado: