Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Grafos

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

Definições básicas

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

Exemplo

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

Exercícios 1

  1. Exiba todos os grafos com conjunto de vértices 0..3.  Para cada valor de E, quantos grafos diferentes existem com vértices 0..3 e E arestas?

Graus de vértices

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.

Número de arestas

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.

Sparse and dense graphs
Dois grafos com 50 vértices: um esparso e um denso.
[Copied from 'Algorithms', 4th.ed., by Sedgewick and Wayne.]

Exercícios 2

  1. [Sedgewick 17.9, p.16]  Quantos grafos diferentes existem com conjunto de vértices 0..V-1 e E arestas?

Valid HTML 4.01 Strict Valid CSS!