TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

A Teoria dos Grafos

Por:   •  23/3/2020  •  Pesquisas Acadêmicas  •  592 Palavras (3 Páginas)  •  208 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)

  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.

...

Baixar como (para membros premium)  txt (3.4 Kb)   pdf (105 Kb)   docx (47.3 Kb)  
Continuar por mais 2 páginas »
Disponível apenas no TrabalhosGratuitos.com