Grafos 01 - Uma Breve História de Grafos

Aula por Lucca Siaudzionis

Vamos começar do começo: O que é um grafo?

Formalmente, um grafo é:

um conjunto de vértices $V$ e
um conjunto de arestas $E$ , que consistem de pares de vértices.

Informalmente, um grafo é um grupo de pontos (vértices) ligados por um grupo de linhas (arestas). Aqui, o exemplo de um grafo: Neste exemplo, $V = \{1, 2, 3, 4, 5, 6\}$ e $E = \{(1, 2), (1, 6), (2, 3), (2, 4), (3, 4)\}$ . Cada vértice é um elemento de $V$ (vértices também podem ser chamados de nós). Cada aresta é um membro de $E$ . Vértices que não pertencem a nenhuma aresta (no exemplo, o vértice $5$ ) podem ser chamados de vértices isolados.

Quando se for resolver um problema, grafos podem ser interpretados de diversas maneiras. Vamos ver alguns exemplos:

Problema 1: Você tem um mapa com várias cidades e estradas entre elas e quer saber se existe um caminho entre duas determinadas cidades.

Grafo: Os vértices são as cidades e as arestas são as estradas.

Problema 2: Você tem um tabuleiro de xadrez e um cavalo numa determinada casa. Você quer saber se é possível ir até uma outra determinada casa.

Grafo: Os vértices são as casas do tabuleiro e há uma aresta entre duas casas se é possível ir de uma até outra com um movimento de cavalo.

Problema 3: Você tem um mapa de uma cidade onde cada rua liga duas esquinas. Você quer saber se é possível ir da sua casa (que fica numa esquina) até a casa de um amigo seu (que fica em outra esquina).

Grafo: Os vértices são as esquinas e as arestas são as ruas.

Vamos definir outros termos agora.

Uma aresta é chamada de self-loop se ela é da forma $(u, u)$ . Um grafo é chamado de multi-grafo se possui duas arestas iguais. Um grafo é dito simples se não é um multi-grafo nem possui um self-loop. O grafo do exemplo é simples. A aresta $(u, v)$ equivale a aresta $(v, u)$ (exceto em grafos direcionados, que vamos falar em breve). Ou seja, dá no mesmo chamar a aresta $(1, 2)$ de $(2, 1)$ e dizemos que a aresta $(1, 2)$ é incidente tanto no vértice $1$ quanto no $2$ . O grau de um vértice é o número de arestas que são incidentes nele. No exemplo, o grau do vértice $1$ é $2$ e o grau do vértice $2$ é $3$ .

O vértice $u$ é dito vizinho do vértice $v$ se, e somente se, existir a aresta $(u, v)$ e dizemos que existe um caminho entre $u$ e $v$ se podemos, partindo de um deles, chegar ao outro percorrendo as arestas que existem no grafo. Mais formalmente falando, é dito que que existe um caminho entre $u$ e $v$ se existir uma sequência de vértices $(V_0, V_1, ..., V_k)$ tal que $V_0 = u$ e $V_k = v$ e sempre existe uma aresta entre $V_i$ e $V_{i+1}$ . Neste caso, é dito que o caminho tem tamanho $k$ . Um ciclo num grafo é um caminho (não nulo) de um vértice $u$ para si mesmo.

É dito que um grafo tem peso se suas arestas possuem pesos. Por exemplo: o comprimento da estrada que liga duas cidades pode ser interpretado como o peso dessa aresta.

Grafos Direcionados

Até agora, o exemplo que estivemos trabalhando foi com um grafo bidirecional (ou não-direcionado), porque as arestas são "mão-dupla". Porém, há casos em que a aresta só pode ser percorrida em um sentido. Neste caso, a representação se dá com "setas" onde a aresta $(u, v)$ significa uma aresta partindo de $u$ em direção a $v$ , ou seja, diferente da aresta $(v, u)$ . Olhe um grafo direcionado:

No exemplo, $V = \{1, 2, 3, 4, 5\}$ e $E = \{(1, 2), (2, 3), (3, 4), (4, 5), (5, 2)\}$ . O grau de saída de um vértice é o número de arestas que começam naquele vértice e o grau de entrada é o número de arestas que terminam nele. No exemplo, o grau de saída do vértice $2$ é $1$ e seu grau de entrada é $2$ . Os grafos são sempre assumidos bidirecionais a não ser que seja dito que é direcionado.

Representação de um Grafo (ou, melhor dizendo: como montar um)

Você não pode simplesmente "desenhar" o grafo no seu programa, então, você tem que representá-lo de alguma maneira. Abordaremos algumas maneiras de representar um grafo aqui, cada uma com suas vantagens e desvantagens.

Os vértices geralmente são representados por números. Quando se tem $N$ vértices, alguns preferem representar cada vértice com um número de $0$ a $N-1$ e outros preferem representar de $1$ a $N$ , eu sou do segundo grupo. Mas cuidar dos vértices é fácil, o que veremos aqui são maneiras de representar as arestas.

Vamos tomar como exemplo nosso grafo inicial e fazer várias representações dele: Lista de Arestas

É a maneira mais intuitiva de guardar as arestas: simplesmente salvar os pares de vértices. É muito fácil de implementar e de debugar e tem uma boa eficiência de memória. Inserir uma aresta pode ser feito em $O(1)$ mas deletar uma aresta pode ser a vir bem lento caso você não saiba sua posição na lista. Também, consultar as arestas que partem de um vértice passa a ser uma tarefa bem lenta.

Para grafos com pesos nas arestas, basta salvar mais um número na lista de arestas, sendo esse o próprio peso da aresta.

A representação ficaria desta maneira:

Slice 4

Matriz de Adjacência

Como já se foi comentado em aulas anteriores, matriz é um array onde casa é um array (um array de arrays). Simplificando isso, pode ser dito que matriz é simplesmente uma tabela. Na matriz de adjacência, iremos guardar informações sobre todos os possíveis pares de vértices, então, sua complexidade de espaço fica $O(V^2)$ .

Na posição $(i, j)$ da matriz, iremos guardar informações sobre a aresta $(i, j)$ : podemos definir $0$ caso não exista aresta ou $1$ caso exista. No caso de grafo com peso, colocamos a posição $(i, j)$ para receber $w$ , onde $w$ é o peso da aresta.

Esta representação é fácil de implementar, não tão fácil de debugar e não tem uma eficiência tão boa de espaço. Porém, fazer alterações sobre arestas ou consultas sobre vértices passa a ser bem mais rápido que na lista de arestas. A representação ficaria desta maneira: Slice 5 Lista de Adjacência

Outra maneira de se guardar as arestas é, para cada vértice, guardar um array contendo seus vizinhos. Isto pode ser feito guardando um array de tamanho $V$ onde a $i$ -ésima casa contém os vizinhos do vértice $i$ .

Esta maneira é bem mais difícil de implementar e de debugar, mas acaba sendo a mais usada por pessoas experientes. Isso se deve ao fato de a memória usada ser em torno da mesma da Lista de Arestas e as consultas sobre um vértice serem consideravelmente mais rápidas. Adicionar uma aresta é bem rápido (remover uma, nem tanto, mas é bem mais rápido que a lista de arestas).

A representação fica desta maneira: Slice 6

Representação Implícita

Em alguns casos, você não precisa guardar as arestas! Olhe, por exemplo, o Problema 2 que citei no começo do artigo. Para cada casa do tabuleiro, você sempre sabe quais são seus vizinhos, sendo estes as 8 possíveis casas para as quais você pode se mover (de acordo com o movimento do cavalo). Esta é, sem dúvida, a melhor maneira de representar um grafo. Porém, nem sempre o grafo pode ser representado desta maneira (na maior parte das vezes, não pode). Se você puder representar o grafo assim, geralmente é a coisa mais sensata a se fazer.

Se $V$ for o número de vértices, $E$ o número de arestas e $d$ o grau máximo de um vértice, podemos resumir nossas complexidades na seguinte tabela:

Eficiência	Lista de Arestas	Matriz de Adj.	Lista de Adj.
Espaço	$2E$	$V^2$	$2E$
Checar Vizinhos	$E$	$1$	$d$
Listar Vizinhos	$E$	$V$	$d$
Adicionar Aresta	$1$	$1$	$1$
Remover Aresta	$E$	$1$	$2d$

Alguns outros conceitos

Antes de acabar aula, vou dar uma introdução em outros nomes comuns de aparecem quando se está trabalhando com grafos.

Conexidade

Um grafo (bidirecional) é dito conexo se, para todo vértice $u$ e para todo vértice $v$ pertencentes ao grafo existir um caminho de $u$ a $v$ . O exemplo trabalhado não é conexo, pois não existe caminho de $1$ a $5$ (na verdade, não existe caminho de nenhum vértice a $5$ ). Porém, se acrescentarmos a aresta $(5, 6)$ , por exemplo, teremos:

Agora, sim, o grafo é conexo.

Componente Conexa e Fortemente Conexa

Componente conexa é um conjunto (máximo) de vértices tal que, para qualquer vértice $u$ e $v$ pertencentes a componente, existe um caminho de $u$ a $v$ . Os vértices $u$ e $v$ pertecem a mesma componente se, e somente se, existe um caminho entre eles. No grafo original, tínhamos duas componentes, a primeira era $\{1, 2, 3, 4, 6\}$ e a outra era $\{5\}$ .

O conceito de componente fortemente conexa é semelhante ao acima, porém aplicado a grafos direcionados. Neste caso, porém, não basta existir um caminho de $u$ a $v$ , precisa-se, também, existir um caminho de $v$ a $u$ .

Sub-Grafo

Um grafo $G' = (V', E')$ é dito um sub-grafo de $G = (V, E)$ se, e somente se, $V' \subset V$ e $E' \subset E$ . O sub-grafo de $G$ induzido por $V'$ é o sub-grafo tal que $E'$ consiste exatamente de todas as arestas cujos vértices estão em $V'$ .

No exemplo, se fizermos $V'= \{2, 3, 4, 5\}$ , seu sub-grafo induzido será:

Grafos Especiais

Um grafo bidirecional é chamado de árvore se, e somente se, ele for conexo e não tiver ciclos. Abaixo, o exemplo de uma árvore:

Um grafo que não contém ciclos, mas que também não é conexo pode ser interpretado como um conjunto de árvores (cada componente conexa sua será uma árvore) e é então chamado de floresta.

Um grafo é chamado de completo se possui arestas entre todo par possível de vértices. O grafo completo com $5$ vértices é

Os conceitos falados agora devem ter ajudado bastante a se ter uma boa introdução. Não conheço questões que cobrem apenas o conteúdo falado agora, mas você pode treinar tentando montar grafos sozinho. Estude bem esta aula para poder entender bem as aulas seguintes sobre grafos. Não se assuste com os conceitos de grafos simplesmente por ser algo totalmente novo, você aprenderá, com o tempo, que é uma ferramenta bem útil para a resolução de problemas.

Caso tenha alguma dúvida sobre a teoria apresentada, volte para a página inicial do curso para preencher o formulário e nos enviar sua dúvida!

As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.