Teoria de Grafos

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ão possui 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 os vé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 é igual ao 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 grafo orientado (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