Acessorios

Rodrigo da Cruz Fujioka Estrutura de Dados www.rodrigofujioka.com

I

Aula 6: Teoria Grafos
Breve Introdução

Slides originais do professor Rodrigo César Lobo http://rclobo.googlepages.com/

Definições
• Um grafo G é constituído por um conjunto V, não vazio, de elementos, chamados vértices, e por uma relação binária entre eles (A). Os elementos de A são denominados arestas.
G = (V, A) V = { 1, 2, 3, 4 } A = { {1,2}, {2,3}, {3,4},{1,4} }

2

Definições
• Um grafo G é dirigido quando fazemos distinção entre a origem e o destino da aresta. Nos grafos dirigidos, chamamos as arestas de arcos.
G = (V, A) V = { 1, 2, 3, 4, 5, 6 } A = { (1,2), (2,1), (2,3), (2,4), (3,3), (4,1), (4,3), (5,6) }
3

Grafos
Grafo Grafo dirigido

2 1 3 1

2 3 5

6

4

Notação
• O Número de vértices de um grafo G é denotado por |V|, que representa a ordem do grafo. • O Número de arestas de um grafo G é denotado por |A|.
G = (V, A) V = { 1, 2, 3, 4, 5, 6 } A = { (1,2), (2,1), (2,3), (2,4), (3,3), (4,1), (4,3), (5,6) } |V| = 6 e |A| = 8.
5

Definições
• Vértices adjacentes: São vértices ligados por arestas.
– Ex.: o vértice 2 é adjacente a 1, 3 e 4); 2 1 3 5
6

6

Definições
• No caso do grafo ser dirigido, a adjacência é especializada em: • Sucessor: um vértice w é sucessor de v se há um arco que parte de v e chega em w. • Antecessor: um vértice v é antecessor de w se há um arco que parte de v e chega em w. Ex: no grafo G1, 5 é antecessor e 6 é sucessor.
G1

6 5

7

Definições
• Arestas incidentes: Dizemos que uma aresta a1 = {x,y} incide sobre os vértices x e y.
– Ex.: {1,2} incide sobre 1 e 2. 2 1 3 5
8

6

Definições
• Arestas incidente (em grafos dirigidos): Arestas são incidentes de ou a determinados vértices, conforme partem ou chegam a eles
– Ex.: (1,2) é incidente de 1 e incidente a 2;

2 1 3 5

6

9

Definições
• Grau de um vértice: É igual ao número de arestas incidentes nesse vértice (ex.: o grau do vértice 1