Dois grafos com 50 vértices: um esparso e um denso.
[Copied from 'Algorithms', 4th.ed., by Sedgewick and Wayne.]
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 outros 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 da aresta são as pontas dos seus dois arcos. As duas pontas de uma aresta são diferentes mas indistinguíveis: não há ponta "inicial" nem ponta "final". 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 o 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.
Os conceitos de grafo é denso e grafo esparso já foram introduzidos quando tratamos de digrafos.
