Encontro 02, Parte 1: Revisão de Grafos

Este guia foi escrito para ajudar você a atingir os seguintes objetivos:

• formalizar conceitos básicos de teoria dos grafos;
• usar funcionalidades básicas da biblioteca da disciplina.

Grafos não-dirigidos

Um grafo não-dirigido (undirected graph) é um par

$(N, E)$,

onde $N$ é um conjunto qualquer e $E$ é um conjunto de pares não-ordenados de elementos de $N$, ou seja,

$E \subseteq \{\{n, m\} \colon n \in N \textrm{ e } m \in N\}$.

Um elemento de $N$ chama-se nó (node) e um elemento de $E$ chama-se aresta (edge). Em alguns trabalhos, usa-se $V$ e vértice em vez de $N$ e nó.

Grafos dirigidos

Formalmente, um grafo dirigido (directed graph) é um par

$(N, E)$,

onde $N$ é um conjunto qualquer e $E$ é um conjunto de pares ordenados de elementos de N, ou seja,

$E \subseteq \{(n, m) \colon n \in N \textrm{ e } m \in N\}$.

Um elemento de $N$ chama-se nó (node) e um elemento de $E$ chama-se aresta (edge). Em alguns trabalhos, usa-se $V$ e vértice em vez de $N$ e nó e usa-se $A$ e arco em vez de $E$ e aresta.

Instalando as dependências

Antes de continuar, instale as duas dependências da biblioteca da disciplina:

pip install networkx plotly

Em algumas distribuições Linux você deve usar o comando pip3, pois o comando pip está associado a Python 2 por padrão.

Importando a biblioteca

Não mova ou renomeie os arquivos do repositório, a menos que você esteja disposto a adaptar os notebooks de acordo.

Vamos importar a biblioteca da disciplina no notebook:

Configurando a biblioteca

A socnet disponibiliza variáveis de módulo que permitem configurar propriedades visuais. Os nomes são auto-explicativos e os valores abaixo são padrão.

Uma variável de cor armazena uma tupla contendo três inteiros entre 0 e 255 que representam intensidades de vermelho, verde e azul respectivamente.

Uma variável de posição armazena uma string contendo duas palavras separadas por um espaço:

• a primeira representa o alinhamento vertical e pode ser top, middle ou bottom;
• a segunda representa o alinhamento horizontal e pode ser left, center ou right.

Carregando grafos

Vamos carregar dois grafos no formato GML:

Abra esses arquivos em um editor de texto e note como o formato é auto-explicativo.

Visualizando grafos

Vamos visualizar o primeiro grafo, que é não-dirigido:

Essa é a representação mais comum de grafos não-dirigidos: círculos como nós e retas como arestas. Se uma reta conecta o círculo que representa $n$ ao círculo que representa $m$, ela representa a aresta $\{n, m\}$.

Vamos agora visualizar o segundo grafo, que é dirigido:

Essa é a representação mais comum de grafos dirigidos: círculos como nós e setas como arestas. Se uma seta sai do círculo que representa $n$ e entra no círculo que representa $m$, ela representa a aresta $(n, m)$.

Note que as duas primeiras linhas não são necessárias se você rodou a célula anterior, pois os valores atribuídos a graph_width e graph_height são exatamente iguais.

Atributos de nós e arestas

Na estrutura de dados usada pela socnet, os nós são inteiros e cada nó é asssociado a um dicionário que armazena seus atributos. Vamos modificar e imprimir o atributo color do nó $0$ do grafo ug. Esse atributo existe por padrão.

Cada aresta também é asssociada a um dicionário que armazena seus atributos. Vamos modificar e imprimir o atributo color da aresta $\{1, 2\}$ do grafo ug. Esse atributo existe por padrão.

Note que a ordem dos nós não importa, pois ug é um grafo não-dirigido.

Os atributos color são exibidos na visualização.

Podemos usar funções de conveniência para reinicializar as cores.

Os atributos label também podem ser exibidos na visualização, mas não existem por padrão. Primeiramente, precisamos criá-los.

Depois, precisamos usar os argumentos nlab e elab para indicar que queremos exibi-los. Esses argumentos são False por padrão.

Vizinhos, predecessores e sucessores

Considere um grafo $(N, E)$ e um nó $n$. Suponha que esse grafo é não-dirigido.

Nesse caso, dizemos que $n$ é vizinho (neighbor) de $m$ se $\{n, m\} \in E$. Denotamos por $\mathcal{N}(n)$ o conjunto dos vizinhos de $n$.

Suponha agora que o grafo $(N, E)$ é dirigido.

Nesse caso, dizemos que $n$ é predecessor de $m$ se $(n, m) \in E$ e dizemos que $n$ é sucessor de $m$ se $(m, n) \in E$. Denotamos por $\mathcal{P}(n)$ o conjunto dos predecessores de $n$ e denotamos por $\mathcal{S}(n)$ o conjunto dos sucessores de $n$.

Passeios, trilhas e caminhos

Se $(N, E)$ é um grafo não-dirigido:

• um passeio (walk) é uma sequência de nós $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ tal que, para todo $i$ entre $0$ e $k-2$, temos que $\{n_i, n_{i + 1}\} \in E$;

• uma trilha (trail) é um passeio $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ no qual não existem índices $i$ e $j$ entre $0$ e $k-2$ tais que $i \neq j$ e $\{n_i, n_{i+1}\} = \{n_j, n_{j+1}\}$;

• um caminho (path) é um passeio $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ no qual não existem índices $i$ e $j$ entre $0$ e $k-1$ tais que $i \neq j$ e $n_i = n_j$.

Se $(N, E)$ é um grafo dirigido:

• um passeio (walk) é uma sequência de nós $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ tal que, para todo $i$ entre $0$ e $k-2$, temos que $(n_i, n_{i + 1}) \in E$;

• uma trilha (trail) é um passeio $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ no qual não existem índices $i$ e $j$ entre $0$ e $k-2$ tais que $i \neq j$ e $(n_i, n_{i+1}) = (n_j, n_{j+1})$;

• um caminho (path) é um passeio $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ no qual não existem índices $i$ e $j$ entre $0$ e $k-1$ tais que $i \neq j$ e $n_i = n_j$.

Pode-se dizer que uma trilha é um passeio que não repete arestas e um caminho é um passeio que não repete nós.

Exercício 1

Dê um exemplo de passeio que não é trilha no grafo ug.

Um passeio que não é trilha é o seguinte:

- 0, 1, 7, 8, 6, 7, 1, 0

Exercício 2

Dê um exemplo de passeio que não é trilha no grafo dg.

Um exemplo de passeio que não é trilha é o seguinte:

- 0, 1, 3, 4, 0, 1, 2

Exercício 3

Dê um exemplo de trilha que não é caminho no grafo ug.

Um exemplo de trilha que não é caminho é o seguinte:

- 0, 1, 2, 5, 6, 8, 2, 3, 4, 5, 3

Exercício 4

Dê um exemplo de trilha que não é caminho no grafo dg.

Um exemplo de trilha que não é caminho é o seguinte:

- 0, 1, 3, 2, 4, 2

Exercício 5

Use cores para dar um exemplo de caminho no grafo ug.

Exercício 6

Use cores para dar um exemplo de caminho no grafo dg.

Posicionamento dos nós

Para encerrar, vamos carregar o grafo do encontro anterior. O próprio arquivo atribui label aos nós, portanto não é necessário criá-los.

Usamos o argumento has_pos para indicar que os atributos x e y devem ser usados para posicionar os nós. Esse argumento é False por padrão, pois nem todo arquivo atribui essas coordenadas.

Se elas não forem usadas, a visualização usa um tipo de force-directed graph drawing.

Esse posicionamento parece familiar?