Algoritmos para Grafos | Índice
Este capítulo define o objeto combinatório conhecido como grafo, ou grafo dirigido, ou ainda grafo orientado. Grafos são importantes modelos para uma grande variedade de problemas de engenharia, computação, matemática, economia, biologia, etc.
Sumário:
Um grafo (= graph) é um par de 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.
Os arcos dos grafos são dirigidos:
cada arco começa
na sua ponta inicial
e termina
na sua ponta final.
Para enfatizar esse fato,
usamos ocasionalmente a expressão grafo dirigido
(= directed graph)
no lugar de grafo,
embora o adjetivo dirigido seja redundante.
(Alguns livros usam o termo
digrafo.
Esse termo é uma tradução
de digraph,
que resultou da contração de directed
e graph.)
A ponta final de todo arco é diferente da ponta inicial. Um arco com ponta inicial v e ponta final w será denotado por
v-w .
(Não confunda essa expressão
com v menos w
.)
Dizemos que o arco v-w
sai de v e
entra em w.
A presença de um arco v-w
é independente da presença do
arco w-v:
o grafo
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 grafo. Dizemos também, nessa circunstância, que w é adjacente a v. A relação de vizinhança não é simétrica: w pode ser vizinho de v sem que v seja vizinho de w.
O tamanho de um grafo com V vértices e A arcos é a soma V + A.
Exemplo A. Uma boa maneira de especificar um grafo é 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 7-11 8-1 8-4 10-3 11-8
define um grafo sobre o conjunto de vértices 0..11. [Este exemplo foi copiado do livro Algorithms, de Sedgewick e Wayne.]
Exemplo B.
A estrutura da rede WWW
pode ser representada por um grafo:
os vértices são as páginas HTML e os arcos são os links
que apontam de uma página para outra.
Navegar
na rede
é pular de um vértice a outro seguindo os arcos.
a-b b-c c-d d-a a-e e-f f-b e-d f-c
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 é v-w e o outro é 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.
Portanto, nossos grafos não têm arcos paralelos
.
O leque de saída (= fan-out) de um vértice num grafo é o conjunto de todos os arcos que saem do vértice. O leque de entrada (= fan-in) de um vértice é o conjunto de todos os arcos que entram no vértice.
Dado um conjunto X de vértices de um grafo, o leque de saída de X é o conjunto dos arcos que saem de X, ou seja, saem de algum vértice em X e entram em algum vértice fora de X. O leque de entrada de X é o conjunto dos arcos que entram em X.
O grau de saída (= outdegree) de um vértice num grafo é o tamanho do seu leque de saída, ou seja, o número de arcos que saem do vértice. O grau de entrada (= indegree) é o tamanho do leque de entrada do vértice.
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 grafo sem vértices isolados é completamente definido por seu conjunto de arcos.
É fácil verificar que a soma dos graus de saída de todos os vértices de um grafo é igual ao número de arcos do grafo. A soma dos graus de entrada de todos os vértices também é igual ao número de arcos. Segue daí que um grafo com V vértices tem no máximo
V (V−1)
arcos. Esse número é apenas um pouco menor que V2.
Um grafo é completo se todo par ordenado de vértices distintos é um arco. Um grafo completo com V vértices tem exatamente V (V−1) arcos. Um torneio é qualquer grafo dotado da seguinte propriedade: para cada par v w de vértices distintos, v-w é um arco ou w-v é um arco, mas não ambos. Um torneio com V vértices tem exatamente ½V(V−1) arcos.
Um grafo é denso se tem muitos arcos em relação ao seu número de vértices e esparso se tem poucos arcos. Mais precisamente, um grafo é denso se o seu número de arcos é da mesma ordem que o quadrado do número de vértices, digamos V2/2, ou V2/10, ou V2/100, ou algo assim. (Portanto, o tamanho de um grafo denso é proporcional a V2.) Um grafo é esparso se seu número de arcos é da mesma ordem que V, digamos 10V, ou V/2, ou algo assim. (Portanto, o tamanho de um grafo esparso é proporcional a V.) É claro que essas definições não se aplicam a grafos individuais, mas a famílias infinitas de grafos.
Um subgrafo de um grafo G é um pedaço
de G.
O conjunto de vértices e o conjunto de arcos do
pedaço
de G
devem ser coerentes.
Assim,
é melhor formular o conceito
como uma relação entre dois grafos:
Um grafo H é
subgrafo
de um grafo G se
todo vértice de H é vértice de G
e
todo arco de H é arco de G.
(Notação:
H ⊆ G.)
Por exemplo, se G é o grafo definido por todos os arcos da figura e H é o grafo formado apenas pelos arcos escuros, então H ⊆ G. Outro exemplo: o grafo que tem vértices 1 3 5 7 e arcos 1-3 5-1 5-7 é um subgrafo de H (e também de G). Já os vértices 1 3 5 e os arcos 1-3 5-1 5-7 nem chegam a constituir um grafo.
Alguns tipos de subgrafos merecem destaque. Um subgrafo H de um grafo G é
Dado um conjunto X de vértices de um grafo G, o subgrafo de G induzido por X é o subgrafo formado por X e todos os arcos de G que têm ambas as pontas em X. Esse grafo pode ser denotado por G[X].
Se a é um arco de um grafo G, denotaremos por G−a o subgrafo que resulta da remoção do arco a de G.
Um supergrafo é o contrário de um subgrafo: um grafo G é supergrafo de um grafo H se H for subgrafo de G.
Um grafo é não-dirigido (= undirected) se cada um de seus arcos é antiparalelo a algum outro arco: para cada arco v-w, o grafo também tem o arco w-v. Por exemplo, o conjunto de arcos abaixo define um grafo não-dirigido.
0-1 0-2 0-5 1-2 2-3 2-4 3-4 3-5 1-0 2-0 5-0 2-1 3-2 4-2 4-3 5-3
Num grafo não-dirigido, a relação de adjacência é simétrica:
um vértice w é adjacente a um vértice v
se e somente se v é adjacente a w.
(O mesmo se aplica ao sinônimo vizinho
de adjacente
.)
Convém tratar os pares de arcos antiparalelos de um grafo não-dirigido como uma nova entidade. Assim, diremos que cada par de arcos antiparalelos é uma aresta (= edge). Qualquer um dos dois arcos da aresta pode ser usado para representar a aresta. Podemos dizer, então, que
0-1 0-2 0-5 1-2 2-3 2-4 3-4 3-5
é o conjunto de arestas do grafo não-dirigido que aparece no exemplo acima. O número de arestas de um grafo não-dirigido é a metade do seu número de arcos: se E denota o número de arestas e A denota o número de arcos então E = A / 2 . Diremos que uma aresta v-w liga os vértices v e w. Diremos também que v-w incide em v e em w.
Num grafo não-dirigido, o leque de um vértice v é o conjunto de arestas que incidem em v. O grau de v é o número de arestas no leque de v. É claro que o grau de um vértice é igual ao seu grau de entrada e também ao seu grau de saída. É fácil verificar que a soma dos graus de todos os vértices de um grafo não-dirigido vale 2E, sendo E o número de arestas.
Subgrafos. Um subgrafo de um grafo não-dirigido pode não ser não-dirigido (pois pode incluir apenas um dos arcos de alguma aresta). Se queremos um subgrafo não-dirigido, precisamos dizer isso explicitamente.
A propósito, é claro que todo subgrafo induzido de um grafo não-dirigido é necessariamente não-dirigido.
a-d b-c h-f e-g a-e b-h c-f d-g a-b d-c h-e f-g
Resposta: Nããão! Dígrafo (com acento) é outra coisa muito diferente!
adjacente: se v-w é um arco, devo dizer
w é adjacente a vou
v é adjacente a w?
Resposta:
É a primeira alternativa. Mas eu também fico confuso.
Teria sido melhor, quem sabe,
dizer algo como v domina w
.
Resposta:
Arcos são meros pares de vértices.
Assim,
não é possível ter dois arcos com a mesma ponta inicial
e a mesma ponta final.
O livro de Sedgewick
permite arcos paralelos de maneira apenas informal,
tratando-os como cópias
distintas
de um mesmo arco.
Resposta: Porque isso simplifica ligeiramente as coisas e não traz nenhum prejuízo.