A Teoria dos Grafos
Por: borgesddr • 23/3/2020 • Pesquisas Acadêmicas • 592 Palavras (3 Páginas) • 206 Visualizações
Página 1 de 3
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)
- Dois vértices são adjacentes se forem os extremos da mesma aresta
- o vértice 2 é adjacente a ele mesmo (laço)
- 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).
- Duas arestas que partilham os mesmos extremos são arestas paralelas
- Um grafo sem aresta paralelas e sem laços é um grafo simples
- Um vértice isolado é aquele que não é adjacente a nenhum outro vértice
- O grau de um vertice é o número de arestas que o tem como um ponto extremo
- Um grafo completo tem todos seus vértices são adjacentes.[pic 2]
Ex:
- 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]
- 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)
- 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.
- Um grafo e dito conexo quando existe um caminho entre dos vértices
- 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.
- Encontre 2 vertices não adjacentes.
- Encontre um vertice adjacente a ele mesmo.
- Encontre um laço.
- Encontre duas arestas paralelas.
- Encontre o grau de vertice 3
- Encontre um caminho de comprimento 5
- Encontre um ciclo
- Este grafo é completo?
- Este grafo é conexo?
Aula 03
[pic 5]
Exercícios 2:
- Este grafo é simples? Explique.
- Este grafo é simples? Explique.
- Este grafo é conexo? Explique.
- Existem 2 caminhos entre os vertices 3 e 5, se sim mostre.
- Este grafo possui algum ciclo?
- O grafo possui algum vertice cujo a remoção o tornaria desconexo?
Exercícios 3 a partir das informações monte os grafos:
- Um grafo simples com 3 vertices, cada qual om grau 2.
- 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.
...
Disponível apenas no TrabalhosGratuitos.com