Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Digrafos

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.)

Definições básicas

Um  digrafo  (= digraphdirected 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.]

Exemplo

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.

Arcos antiparalelos e "arcos paralelos"

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".

Digrafos simétricos

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

Grau de entrada e grau de saída

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.

Número 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.

Exercícios

  1. Quantos digrafos diferentes existem com conjunto de vértices  0..V-1  e  A  arcos?

 


URL of this site: http://www.ime.usp.br/~pf/algoritmos_para_grafos/
Last modified: Wed Aug 25 08:01:07 BRT 2010
Paulo Feofiloff
IME-USP

Valid HTML 4.0!     Valid CSS!