Teoria de Grafos

Páginas: 3 (745 palavras) Publicado: 18 de setembro de 2014
Revisão para prova de Teoria dos Grafos

Aula 1 - 2
Grafos - Características
Representação Matemática:
V(G) = {v1,v2,v3,v4,v5,v6,v7}
E(G) = {(v1, v2); (v1,v5); (v2,v5); (v3,v4); (v5,v7)}

-Ordem de um grafo – número de vértices
- Ordem de arestas de um grafo – número de arestas
|V(G)| = 7
|E(G)| = 5

- Grau – é o maior grau encontrado entre seus vértices
- Grafo Simples – nãopossui arestas múltiplas nem laços
- Grafo Regular – todos os vértices tem o mesmo grau
- Grafo Completo – todos os vértices são adjacentes

Vértices - Características
- Vértices adjacentes – são osvértices vizinhos
- Grau – número de arestas ligadas a ele
- Grau – pode ser encontrado como valência do vértice. Grau 1 = pendulo
- Grau – a soma dos graus dos vértices de qualquer grafo é igualao dobro do número de arestas / o número de arestas multiplicado por 2 é igual à soma dos graus dos vértices / a soma dos graus dos vértices de um grafo é sempre par

Arestas - Características
-Arestas Adjacentes - são as arestas ligadas aos vértices
----------------------------------------------------------------------------------------------------------
Aula 3
Grafos Orientados
Um grafoorientado (ou dígrafo) D = (V,E) consiste de um conjunto V (vértices) e de um conjunto de E (arestas) de pares ordenados de vértices distintos.
Em um grafo orientado, cada aresta e = (x,y) possui umaúnica direção de x para y. Diz-se que (x, y) é divergente de x e convergente a y.

- Grau de Entrada – quantidade de arestas que chegam no vértice
- Grau de Entrada – se for igual a nulo (0), échamado fonte
- Grau de Saída – quantidade de arestas que saem do vértice
- Grau de Saída – se for igual a nulo (0), é chamado sumidouro

Grade
3x3----------------------------------------------------------------------------------------------------------

Aula 4 - 5
Caminhos – Características
É uma sequência de vértices e arestas que une x e y
- Caminho Simples – os vértices não...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Teoria Grafos
  • Teoria dos Grafos
  • teoria dos grafos
  • Teoria dos grafos
  • Teoria dos grafos
  • Teoria Dos Grafos
  • Teoria de grafos
  • Teoria dos grafos

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!