Exercícios
1) O grafo dos estados do Brasil é definido assim: cada vértice é um dos estados da República Federativa do Brasil; dois estados são adjacentes se têm uma fronteira comum. Quantos vértices tem o grafo? Quantas arestas?
Grafo não direcionado
Resposta: Para resolver tal questão, basta contar os pontos e os segmentos de reta da figura, onde cada ponto equivale a um vértice do grafo e os segmentos de reta são as arestas. No total, o grafo possui 26 vertices, 49 arestas.
2) Os hidrocarbonetos conhecidos como alcanos têm fórmula química CpH2p+2 , onde C e H representam moléculas de carbono e hidrogênio respectivamente. Os vértices em que incide uma só aresta representam átomos de hidrogênio (H ); os demais representam átomos de carbono (C ).Desenhe um grafo para Etano (C2H6 ), butano (C4H10 ) e isobutano (C4H10).
Resposta 2.
3) Encontre a soma do grau de cada vértice dos exemplos 1 e 2 abaixo, e verifique que seu valor é o dobro do numero de arestas no grafo.
Resposta: O grau de um vértice é a quantidade de arestas que este vértice possui. No caso 1, temos que o grau de a é 2 (a-b, a-f), b é 4 (b-a, b-c, b-e, b-f), c é 1 (c-b), e é 2 (e-b, e-f) e f é 3 (f-a, f-b, f-e). Portanto, temos que a soma dos graus é 2+4+1+2+3=12. O número de arestas é 6, portanto a soma dos graus é igual ao dobro do número de arestas.No caso 2, a resolução é a mesma. No caso de laços, como c-c, devemos considerar como aresta. No total, o grafo possui 12 arestas e a soma dos graus dos vértices é 24, ou seja, o proposto no exercício é verdadeiro.