[Copied from 'Algorithms', 4th.ed.,
by Sedgewick and Wayne.]
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. 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 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. Mas não vamos usar esse termo.]
Uma boa maneira de especificar um digrafo é exibir o seu conjunto de arcos. Por exemplo, o conjunto de arcos
0-5 0-6 2-0 2-3 3-6 3-10 4-1 5-2 5-10 6-2 7-8 8-1 8-4 10-3 11-8
define um digrafo sobre o conjunto de vértices 0..11. Note que o vértice 9 é isolado.
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" (ou "repetidos") se têm a mesma ponta inicial e a mesma ponta final. Mas esse conceito não faz sentido sob nossas definições, 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.] Resumindo: 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 e esparso de se tem poucos arcos. Mais precisamente, um digrafo é denso se o seu número de arcos é da mesma ordem de grandeza que o quadrado do número de vértices, digamos V2/10, ou V2/100, ou algo assim. Um digrafo é esparso se seu número de arcos é da mesma ordem de grandeza que V, digamos 10V, ou V/2, ou algo assim. É claro que essas definições só fazem sentido no contexto de uma família infinita de digrafos, e não para um digrafo individual.
Resposta: Nããão! A palavra digrafo é uma adaptação do termo digraph, que por sua vez resultou da contração de directed e graph. Já dígrafo (com acento) é outra coisa muito diferente!
