Algoritmos para Grafos, via Sedgewick | Índice remissivo
Um grafo é um tipo especial de digrafo, também conhecido como grafo não dirigido e grafo não orientado. Grafos são modelos naturais para muitos problemas práticos.
(Esta página corresponde aproximadamente às seções 17.0 e 17.1 (Glossary) do capítulo 17 (Graph Properties and Types) do livro de Sedgewick.)
Um grafo (= graph) é um digrafo simétrico. Em virtude de suas propriedades especiais e de suas aplicações práticas, grafos merecem ser estudados à parte dos digrafos.
Os arcos de um grafo andam aos pares: cada arco v-w é acompanhado do arco w-v. Convém tratar esse par de arcos como uma nova entidade. Assim, diremos que um par de arcos antiparalelos é uma
aresta (= edge).
As pontas dos dois arcos são as pontas da aresta. As duas pontas de uma aresta são indistinguíveis: não há ponta inicial nem ponta final. (Mas convém lembrar que as duas pontas são diferentes.) Uma aresta com pontas v e w será denotada, indiferentemente, por
v-w ou w-v.
(Convém lembrar que nossos grafos não têm "arestas paralelas", ou seja, arestas com um mesmo par de pontas.)
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.
O número de arestas de um grafo é 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
A = 2·E .
Uma maneira cômoda de especificar um grafo é exibir o conjunto de suas arestas. Por exemplo, o conjunto de arestas
0-1 0-5 1-5 2-4 3-1 5-3
define um grafo sobre o conjunto de vértices 0..5. Cada elemento v-w dessa lista representa dois arcos: o arco v-w e o arco w-v. (Compare com o exemplo de digrafo simétrico na página anterior.)
O grau de um vértice em um grafo é o número de arestas que incidem no vértice. Esse número é igual ao grau de entrada do vértice e também ao grau de saída do vértice.
É fácil verificar que a soma dos graus de todos os vértices de um grafo vale 2E, sendo E o número de arestas. Portanto, o grau médio do grafo é o número 2E/V , sendo V o número de vértices.
Convém lembrar que um vértice é isolado se o seu grau é nulo.
Quantas arestas, no máximo, tem um grafo com V vértices? [Veja Property 17.1, p.8, em Sedgewick.] Não é difícil verificar que a resposta é
V·(V-1)/2 .
Esse número é pouco menor que ½ V2.
Um grafo é completo se todo par não ordenado de vértices distintos é um aresta. Um grafo completo com V vértices tem exatamente V·(V-1)/2 arestas.