Algoritmos para Grafos, via Sedgewick | Índice remissivo
Esta página define um objeto combinatório conhecido como digrafo ou grafo dirigido ou ainda grafo orientado. Digrafos são importantes modelos para uma grande variedade de problemas de engenharia, computação, matemática, economia, biologia, etc.
(Esta página corresponde aproximadamente às seções 17.0 e 17.1 (Glossary) do capítulo 17 (Graph Properties and Types) e às seções 19.0 e 19.1 (Glossary and Rules of the Game) do capítulo 19 (Digraphs and DAGs) do livro de Sedgewick.)
Um digrafo (= digraph = directed graph) é uma coisa que consiste em dois conjuntos: um conjunto de coisas conhecidas como vértices e um conjunto de coisas conhecidas como arcos. [Sedgewick diz directed edge em lugar de arc.] Cada arco é um par ordenado de vértices. O primeiro vértice do par é a ponta inicial do arco e o segundo é a ponta final.
[A palavra digrafo não consta dos dicionários, mas é cômoda e corresponde bem ao termo digraph em inglês, que já está bastante arraigado. Alguns autores descuidados escrevem "dígrafo", com acento; isso não faz sentido algum e deve ser evitado a todo custo.]
A ponta final de todo arco é diferente de sua ponta inicial. [O livro de Sedgewick admite arcos cuja ponta final é igual à inicial. Arcos desse tipo são conhecidos como laços (= loops). Nossos digrafos não terão laços.] Um arco com ponta inicial v e ponta final w será denotado por
v-w .
(É preciso estar atento ao contexto para não confundir essa expressão com "v menos w".) A presença de um arco v-w é independente da presença do arco w-v: o digrafo pode ter os arcos v-w e w-v, pode ter apenas um deles, ou pode não ter nenhum deles.
Dizemos que um vértice w é vizinho de um vértice v se v-w é um arco do digrafo. Dizemos também, nessa circunstância, que w é adjacente a v. [É mais comum e menos ambíguo dizer que v domina w quando v-w é um arco. Infelizmente, Sedgewick não usa essa terminologia.]
Uma boa maneira de especificar um digrafo é exibir o seu conjunto de arcos. Por exemplo, o conjunto de arcos
0-1 0-5 1-0 1-5 2-4 3-1 5-3
define um digrafo sobre o conjunto de vértices 0..5. É claro que um digrafo definido dessa maneira não tem vértices isolados.
Dois arcos são antiparalelos se a ponta inicial de um é a ponta final do outro e vice-versa. Em outras palavras, dois arcos são antiparalelos se um é da forma v-w e o outro da forma w-v.
Poderíamos tentar dizer que dois arcos são paralelos se têm a mesma ponta inicial e a mesma ponta final. Mas esse conceito não faz sentido, uma vez que arcos são meros pares de vértices e portanto dois arcos diferentes não podem ter a mesma ponta inicial e a mesma ponta final. [O livro de Sedgewick permite arcos paralelos, tratando-os como "cópias" distintas de um mesmo arco.] Nossos digrafos não têm "arcos paralelos".
Um digrafo é simétrico se cada um de seus arcos é antiparalelo a algum outro arco: para cada arco v-w, o digrafo também tem o arco w-v.
Por exemplo, o conjunto de arcos abaixo define um digrafo simétrico.
0-1 1-0 0-5 5-0 1-5 5-1 2-4 4-2 3-1 1-3 5-3 3-5
O grau de saída (= outdegree) de um vértice v num digrafo é o número de arcos que têm ponta inicial v. O grau de entrada (= indegree) de um vértice w num digrafo é o número de arcos que têm ponta final w.
Num digrafo simétrico, todo vértice tem grau de entrada igual ao grau de saída.
Uma fonte (= source) é um vértice que tem grau de entrada nulo. Um sorvedouro (= sink) é um vértice que tem grau de saída nulo.
Um vértice é isolado se seu grau de entrada e seu grau de saída são ambos nulos. É claro que um digrafo sem vértices isolados é completamente definido pelo seu conjunto de arcos.
Quantos arcos, no máximo, tem um digrafo com V vértices? Não é difícil verificar que a resposta a essa pergunta é o produto
V·(V-1).
Para valores grandes de V, esse número é apenas um pouco menor que V2.
Um digrafo é completo se todo par ordenado de vértices distintos é um arco. Um digrafo completo com V vértices tem exatamente V·(V-1) arcos.
Um digrafo é denso se tem muitos arcos em relação ao número de vértices. Mais precisamente, um digrafo é denso se o seu número de arcos é proporcional ao quadrado do número de vértices. É claro que essa definição só faz sentido para coleções infinitas de digrafos, e não para digrafos individuais.
Um digrafo é esparso se for o complemento de um digrafo denso, ou seja, se o número de pares ordenados de vértices que não são arcos for proporcional ao quadrado do número de vértices. É claro que essa definição só faz sentido para coleções infinitas de digrafos, e não para digrafos individuais.