A Teoria dos Grafos

Resumo teoria dos grafos Np1

[pic 1]

Arestas: (a1 até a5)

Vértices: pontos vermelhos de 1 a 5

Laço: a3

Aresta paralela: (a2 com a1)

1. Dois vértices são adjacentes se forem os extremos da mesma aresta
2. o vértice 2 é adjacente a ele mesmo (laço)
3. Um laço em um grafo é uma aresta com extremas N – N para um só N. Um grafo que não tem laços, chama-se (sem laço).
4. Duas arestas que partilham os mesmos extremos são arestas paralelas
5. Um grafo sem aresta paralelas e sem laços é um grafo simples
6. Um vértice isolado é aquele que não é adjacente a nenhum outro vértice
7. O grau de um vertice é o número de arestas que o tem como um ponto extremo
8. Um grafo completo tem todos seus vértices são adjacentes.[pic 2]

Ex:

1. Um subgrafo consiste de um conjunto de vértices e o outro de arestas que são subconjuntos dos vértices e arestas de um grafo maior. É um grafo obtido apagando-se parte de um grafo maior.

Ex

[pic 3]

Grafo maior: chamamos de 1;

[pic 4]

1.  Um caminho N0 a um vertici NK é uma sequencia

Ex: N0,A0,N1,A1.... AK-1, NK

“No grafo 1 o caminho de 2 a 4 pode ser

1º (2,a1,a5,3,a6,4)

2º (2,a1,1,a5,3,a6,4)

1.  O comprimento é o número de arestas que ele contém. Se uma aresta for usada mais de uma vez, ela deve ser contada quantas vezes for usada.
2.  Um grafo e dito conexo quando existe um caminho entre dos vértices
3. Um cicle em um grafo é um caminho a um vertice N0 ate ele mesmo, de forma que nenhum vertice ocorra mais de uma vez no caminho, N0 é o único vertice que pode se repetir, por ser o começo e o fim do caminho.

Ex: no grafo 1 se seguirmos o ciclo (1, a1, 2 a4, 3, a5, 1).

Um grafo sem ciclo é dito acíclico.

Exercícios: para o grafo 1.

1. Encontre 2 vertices não adjacentes.

1. Encontre um vertice adjacente a ele mesmo.

1. Encontre um laço.

1. Encontre duas arestas paralelas.

1. Encontre o grau de vertice 3

1. Encontre um caminho de comprimento 5

1. Encontre um ciclo

1. Este grafo é completo?

1. Este grafo é conexo?

Aula 03

[pic 5]

Exercícios 2:

1. Este grafo é simples? Explique.

1. Este grafo é simples? Explique.

1. Este grafo é conexo? Explique.

1. Existem 2 caminhos entre os vertices 3 e 5, se sim mostre.

1. Este grafo possui algum ciclo?

1. O grafo possui algum vertice cujo a remoção o tornaria desconexo?

Exercícios 3 a partir das informações monte os grafos:

1. Um grafo simples com 3 vertices, cada qual om grau 2.

1.  Um grão com 4 vertices, com ciclos de tamanho 1,2,3 e 4

Exercício 4: para cada descrição monte um grafo se possível.

...