GRAFOS

Teoria dos Grafos
•
•
•
•
•
•
•

Definição e Aplicação
Terminologia de Grafo
Representação Computacional
Matriz de adjacência
Matriz de incidência
Caminho de euller
Caminho minimo

Teoria dos Grafos

Representação
Representação Computacional
• E se quisermos armazenar um grafo em um computador ?
• Precisamos armazenar os dados essenciais da definição de grafo. • A partir desta informação pode-se construir uma representação visual ou efetuar operações sobre o grafo.
• Estruturas comumente utilizadas:
• Matriz de Adjacência;
• Matriz de Incidência;

Matriz de Adjacência

Representação
Matriz de adjacência
• Lembrando o conceito de adjacência:
- a é adjacente a b se está conectado a b;
• A matriz de adjacência possui informação que reflete este conceito:
• Suponha a matriz quadrada M

Representação
Matriz de adjacência

Representação
Matriz de adjacência

Vantagem ou desvantagem ????

Representação
Matriz de adjacência

Representação
Matriz de adjacência
• É possível representar grafos direcionados usando matriz de adjacência ????

Representação
Matriz de adjacência
• É possível representar arestas laço usando matriz de adjacência ????

Representação
Matriz de adjacência
• É possível representar arestas paralelas usando matriz de adjacência ????

Representação
Matriz de adjacência
• É possível representar arestas valoradas usando matriz de adjacência ????

Representação
Matriz de adjacência
• É possível representar grafos com arestas valoradas e com arestas paralelas usando matriz de adjacência ????

Matriz de Incidência

Representação
Matriz de incidência
• A matriz de incidência possui a seguinte dimensão: • Suponha a matriz M

Representação
Matriz de incidência

Representação
Matriz de incidência
• Podemos representar grafos orientados utilizando matriz de incidência ?

Representação
Matriz de incidência

Representação
Matriz de incidência
• É