Trabalho elaborado para obtenção de nota na disciplina Matemática Discreta

...

[pic 1]

Figura 1: Grafo com 6 vértices, 8 arestas, simples, conexo, planar e semi-euleriano

Na Figura 1 por exemplo temos:

Vértices - V (G) = { 1 ,2 ,3 ,4 ,5 ,6 }

Arestas - A(G) = { (1,3) (1,5) (2,4) (2,5) (2,6) (3,4) (4,5) (4,6) }

Vértice

Vértice adjacentes

1

5,3

2

4,5,6

3

1,4

4

2,3,5,6

5

1,2,4

6

2,4

Tabela 1: Vertices Adjacentes

TERMINOLOGIA E APLICAÇÕES DE GRAFOS

REPRESENTAÇÕES COMPUTACIONAIS DE GRAFOS

Para representar os grafos estudados em um ambiente computacional devemos estudar qual estrutura devemos utilizar. Em geral, a estrutura de dados adotada está relacionada com qual a função do algoritmo que irá atuar no grafo.

Em casos gerais, com uma estrutura básica deveríamos ser capazes de responder as perguntas:

1. qual é o tamanho do conjunto de vértices de um grafo G? │V (G) │

2. qual é o tamanho do conjunto de arestas de um grafo G? │E(G) │

3. qual é o grau de um determinado vértice de um grafo G? dG(u) ∴ u ∈ V (G)

4. uma aresta {u, v} pertence ao conjunto de arestas do grafo G? {u, v} ∈ E(G)

5. qual a vizinhança de um vértice u do conjunto de vértices do grafo G? NG(u) ∴ u ∈ V (G)

Algumas perguntas, como a 3, são perguntas secundárias, por exemplo o grau de um vértice está ligado com a quantidade de vizinhos desse vértice, outro exemplo de pergunta secundária é uma pergunta do tipo: O grafo G é completo?, pois também depende de outras informações obtidas por perguntas primárias.

Para representação computacional de um grafo, é necessário trechos de algoritmos que percorram os vizinhos de um determinado vértice, assim respondendo tanto perguntas primárias quanto secundárias.

Uma das perguntas mais recorrentes nos algoritmos que percorrem os nodos de um grafo é: "para todo u ∈ Ng(v) faça". Essa pergunta pode ser traduzida de duas formas diferentes:

• "para todo u ∈ V (G) ∴ {u, v} ∈ E faça";

• "u ← primeiro vizinho (v)" + "u ← próximo vizinho (v)".

O primeiro laço necessita que se responda a pergunta 4, enquanto que a segunda necessita que se responda a pergunta 5. Uma questão interessante ao se codificar a estrutura de dados de um grafo é o método de indexação, vértices x arestas. Mesmo assim existem casos particulares em que algum tipo de indexação pode ser mais eficiente que outro.

Lista de Arestas

É uma representação de um grafo na qual é dado um vetor ou lista com pares de vértices representando as arestas desse grafo.

Exemplo 7: Seja um grafo G de exemplo, definido por:

V (G) = {1, 2, 3, 4, 5}

E(G) = {{1, 2}, {2, 5}, {5, 4}, {4, 3}, {4, 2}}

Sua representação por lista de arestas é dada por:

{1, 2}, {2, 5}, {5, 4}, {4, 3}, {4, 2}

Para representar os vértices nessa notação utiliza-se um vetor de vértices de 1 a n com n = |V (G)|

V = {1, 2, 3, 4, 5}

GRAFOS EULERIANOS E CICLO HAMILTONIANO

Voltando ao problema do grafo da introdução, dizemos que um grafo G com n vértices e m arestas é Euleriano se ele possui uma trilha fechada de mesmo comprimento m, começando e terminado no mesmo vértice. Ou seja, percorrer o grafo formando um ciclo fechado que utiliza cada aresta uma única vez. Com isso, o grafo da introdução, e os grafos de passa-tempo deixados pelo aluno, não são eulianos, pois conseguimos até um caminho mas, formando uma trilha aberta de comprimento m no grafo G, e sempre terminaremos em outro vértice daquele ao qual começamos. Euler considerou esses casos, e os chamou de grafos semi-eulerianos, por possuírem tal propriedade.

A diferença entre grafo euleriano e semi-euleriano, consistem em que no primeiro todos os vértices possuem graus pares e existe uma trilha fechada de mesmo comprimento m do grafo dado. No segundo caso, temos um par de vértices de grau ímpar e possui uma trilha aberta de comprimento m do grafo.

Teorema 3.1. Um grafo conexo G (não necessariamente simples) é euleriano, se, e somente se, possuir vértices com graus pares.

CICLO HAMILTONIANOS

Paralelamente à ideia dos grafos eulerianos, de passar por cada aresta uma única vez, os grafos hamiltonianos consistem em passar por cada vértice uma única vez. Caminho hamiltoniano em um grafo é o caminho que visita cada vértice exatamente uma vez.

Um ciclo hamiltoniano é um ciclo que visita cada vértice uma só vez (uma trilha fechada que começa e termina no mesmo vértice).

[pic 2]

Figura 2

O grafo da Figura 2 contém um caminho hamiltoniano. Enquanto determinar se um dado grafo contém um caminho ou ciclo euleriano é trivial, o mesmo problema para caminhos e ciclos hamiltonianos é extremamente árduo.

Recursos computacionais são necessários para testar todas as possíveis soluções.

Caso