Projeto e Análise de Algoritmos I

Aula 06 - Introdução à Teoria dos Grafos

Lucas Nunes Alegre

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica


Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado, André Grahl Pereira, Lucas Nunes Alegre, Marcus Ritt e Luciana Buriol.

Introdução

Grafos

Grafos: Cubo

Grafos: Máquina de Turing

Grafos: Organização de Computadores

Grafos: Local Area Network

Grafos: Deep Learning

Grafos: Graph Neural Network

Grafos: Sistema Nervoso

Grafos: Rede de Genes

Grafos: Filogenia

Grafos: Cadeia Alimentar

Grafos: Rede Social

Grafos: Rede de Citações

Grafos: Personagens

I will be there for you: six friends in a clique

Grafos: Rodovias

Grafos: Rotas Aéreas

Grafos: Cabos Submarinos

Grafos: Mundo

Grafos

Leonhard Euler (1707–1783)

As Sete Pontes de Königsberg (1736)

Wikipedia

Grafos Simples

Grafos Simples

Definição: Um grafo simples é uma tupla (V,E) onde:

  • V é um conjunto não-vazio de vértices.
  • E é um conjunto de subconjuntos de V com exatos dois elementos (chamados arestas).

Exemplo:

G_1 = (\{A,B,C,D,E,F\}, \{\{A,B\}, \{B,D\}, \{B,E\}, \{D,E\}, \{E,F\}\})

  • Grafos são comumente desenhados como diagramas onde vértices são pontos e arestas são linhas conectando dois vértices distintos.
G_1 =

Representação Gráfica

Nota: Um mesmo grafo pode ser desenhado de muitas formas diferentes.


Contudo, o jeito de desenhá-lo não o modifica, visto que o grafo é uma estrutura algébrica que representa somente conexão entre nodos.


Exemplo:

=

Grafos Simples: Contagem Básica

  • Considere um conjunto V de tamanho n.


Pergunta: Se formos construir um grafo simples usando os elementos de V como nodos, qual o número máximo de arestas que podemos inserir?

Resposta: Uma aresta para cada par distinto de nodos, ou seja, o número de possíveis pares de nodos (sem considerar ordem entre eles).

\binom{n}{2} = \frac{n!}{(n-2)! \cdot 2!} = \frac{1}{2}n^2 - \frac{1}{2}n

Grafos Simples: Contagem Básica

  • Considere um conjunto V de tamanho n.


Pergunta: Quantos grafos distintos podemos construir sobre o conjunto de vértices V?

Resposta: Considerando que todos os nodos sempre estarão presentes, o que diferenciará os grafos será quais arestas estão presentes. Cada aresta pode ou não existir no grafo (duas opções), e temos \binom{n}{2} possíveis arestas.

2 \times 2 \times 2 \times \dots = 2^{\binom{n}{2}} = 2^{\frac{1}{2}n^2 - \frac{1}{2}n}

Grafos Simples: Contagem Básica


n 1 2 3 4 5 6 7 8
Máximo de arestas 0 1 3 6 10 15 21 28
Grafos simples possíveis 1 2 8 64 1.024 32.768 2.097.152 268.435.456

Relações de Incidência e Adjacência

Relação de Incidência

Definição: Relação de incidência de G (sobre E \times V) relaciona arestas com os vértices que elas conectam.

Definição: Matriz de incidência: representação matricial da relação de incidência de um grafo simples.

Exemplo: Matriz de incidência de G_1:

\begin{array}{c|cccccc} & A & B & C & D & E & F \\ \hline \{A,B\} & 1 & 1 & 0 & 0 & 0 & 0 \\ \{B,D\} & 0 & 1 & 0 & 1 & 0 & 0 \\ \{B,E\} & 0 & 1 & 0 & 0 & 1 & 0 \\ \{D,E\} & 0 & 0 & 0 & 1 & 1 & 0 \\ \{E,F\} & 0 & 0 & 0 & 0 & 1 & 1 \end{array}

Relação de Adjacência (Vértices)

Definição: Relação de adjacência de vértices de G (sobre V\times V) relaciona vértices conectados por arestas.

Definição: Matriz de adjacência de vértices: representação matricial da relação de adjacência de um grafo simples.

Exemplo: Matriz de adjacência (vértices) de G_1:

\begin{array}{l|cccccc} & A & B & C & D & E & F \\ \hline A & 0 & 1 & 0 & 0 & 0 & 0 \\ B & 1 & 0 & 0 & 1 & 1 & 0 \\ C & 0 & 0 & 0 & 0 & 0 & 0 \\ D & 0 & 1 & 0 & 0 & 1 & 0 \\ E & 0 & 1 & 0 & 1 & 0 & 1 \\ F & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{array}

Relação de Adjacência (Arestas)

Definição: Relação de adjacência de arestas de G (sobre E\times E) relaciona arestas que incidem sobre um único vértice comum.

Definição: Matriz de adjacência: representação matricial da relação de adjacência.

Exemplo: Matriz de adjacência (arestas) de G_1:

\footnotesize \begin{array}{c|ccccc} & \{A,B\} & \{B,D\} & \{B,E\} & \{D,E\} & \{E,F\} \\ \hline \{A,B\} & 0 & 1 & 1 & 0 & 0 \\ \{B,D\} & 1 & 0 & 1 & 1 & 0 \\ \{B,E\} & 1 & 1 & 0 & 1 & 1 \\ \{D,E\} & 0 & 1 & 1 & 0 & 1 \\ \{E,F\} & 0 & 0 & 1 & 1 & 0 \end{array}

Propriedades da Relação de Adjacência

Uma relação de adjacência R sobre U \times U é:

  • Irreflexiva:

\forall a \in U, \quad (a,a) \notin R

  • Simétrica:

\forall a,b \in U, \quad (a,b) \in R \Rightarrow (b,a) \in R

Nota: U pode ser V (nodos) ou E (arestas) de um grafo simples.

Armazenamento de Grafos em Memória

Grafos simples podem ser armazenados de várias formas em computadores:

  • Matriz de incidência
  • Matriz de adjacência de vértices
  • Lista encadeada de incidência/adjacência

Representações de Grafos em Memória

Lista de Adjacência

  • Em Python, representamos grafos através de dicionários de listas de adjacência:
    • Vértice (u \in V): chave do dicionário (qualquer tipo hashable, ex: str, int).
    • Vizinhos (\text{Adj}(u)): lista de vértices conectados a u.
    • Invariante: todo vértice referenciado nas listas de adjacência deve ser uma chave válida do dicionário.

Exemplo: Grafo em Python

Matriz de adjacência:

\begin{array}{l|cccccc} & A & B & C & D & E & F \\ \hline A & 0 & 1 & 0 & 0 & 0 & 0 \\ B & 1 & 0 & 0 & 1 & 1 & 0 \\ C & 0 & 0 & 0 & 0 & 0 & 0 \\ D & 0 & 1 & 0 & 0 & 1 & 0 \\ E & 0 & 1 & 0 & 1 & 0 & 1 \\ F & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{array}

Código Python (dicionário de adjacências):

g1 = {
    'A': ['B'],
    'B': ['A', 'D', 'E'],
    'C': [],
    'D': ['B', 'E'],
    'E': ['B', 'D', 'F'],
    'F': ['E'],
}

Análise de Complexidade

Algoritmos e Análise


Pergunta: Qual a complexidade de encontrar o tamanho de uma lista com n elementos?

Resposta: O(n) ou O(1) se o tamanho atual da lista sempre for guardado junto dela.


Complexidade: Matriz vs. Lista de Adjacência

Seja n = |V| e m = |E|.

Operação Matriz Lista
Espaço O(n^2) O(n + m)
Verificar aresta (u,v) O(1) O(\deg(u))
Listar vizinhos de v O(n) O(\deg(v))
Inserir aresta O(1) O(1)
Remover aresta O(1) O(\deg(u))

Quando Usar Cada Representação?

Matriz de adjacência:

  • Grafo denso (m \approx n^2):
    • o custo de espaço O(n^2) é aceitável.
  • Consultas de adjacência frequentes: verificar (u,v) \in E em O(1).

Lista de adjacência:

  • Grafo esparso (m \ll n^2): economia de espaço O(n+m).
  • Algoritmos que percorrem vizinhos de cada vértice (BFS, DFS, …):
    • custo O(\deg(v)) por vértice é ótimo.

Nota: A maioria dos grafos do mundo real é esparsa \Rightarrow listas de adjacência são a representação padrão.

Subgrafos

Subgrafo

Definição: Dois grafos G = (V,E) e G'=(V',E') são iguais sss V = V' e E = E'.

Definição: Um grafo G = (V,E) é subgrafo de G'=(V',E'), escrito G \subseteq G', sss V \subseteq V' e E \subseteq E'. O grafo G' é chamado sobregrafo de G.

Definição: Um grafo G é subgrafo próprio de G', escrito G \subset G', sss G \subseteq G' e G \neq G'.

Exemplo:

⊂

Subgrafo Induzido

Definição: Seja G = (V,E) um grafo e V' \subseteq V um subconjunto de vértices de G. O subgrafo G' induzido por V' é definido por: G' = (V', \{\{a,b\} \mid \{a,b\} \in E \land a \in V' \land b \in V'\})

Intuição: O subgrafo induzido por um conjunto de vértices contém todas (e somente) as arestas do grafo original sobre os vértices selecionados.


Exemplo: Para G com V' = \{A,B,C,E\}:

⇒

Graus

Graus

Grau de um Nodo

Definição: O grau de um nodo n, escrito \deg(n), é o número de arestas que incidem sobre n.

Exemplo:

  • \deg(A) = 1
  • \deg(B) = 3
  • \deg(C) = 0
  • \deg(D) = 2
  • \deg(E) = 3
  • \deg(F) = 1

Nota: \deg(n) é definido somente quando o número de arestas incidentes sobre n é finito.

Grau de um Nodo e Matriz de Incidência

Em um grafo simples, podemos calcular o grau de um nodo somando a coluna correspondente ao nodo na matriz de incidência.

Exemplo:

\begin{array}{c|cccccc} & A & B & C & D & E & F \\ \hline \{A,B\} & 1 & 1 & 0 & 0 & 0 & 0 \\ \{B,D\} & 0 & 1 & 0 & 1 & 0 & 0 \\ \{B,E\} & 0 & 1 & 0 & 0 & 1 & 0 \\ \{D,E\} & 0 & 0 & 0 & 1 & 1 & 0 \\ \{E,F\} & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline \hline \deg & 1 & 3 & 0 & 2 & 3 & 1 \\ \end{array}

Lema: (Handshaking Lemma) Em um grafo simples G=(V,E): \sum_{v \in V} \deg(v) = 2 |E|

Demonstração: Soma total da matriz de incidência por linhas vs. por colunas.

Calculando Graus: Matriz vs. Lista de Adjacência

Grau de um único nodo v:

  • Matriz: percorre a linha v inteira \Rightarrow O(n).
  • Lista: comprimento da lista de v \Rightarrow O(\deg(v)) ou O(1) dependendo da implementação.

Graus de todos os nodos:

  • Matriz: percorre todas as n linhas de tamanho n \Rightarrow O(n^2).
  • Lista: percorre todas as listas, cujo tamanho total é 2m \Rightarrow O(n + m) ou O(n) dependendo da implementação.
Operação Matriz Lista
\deg(v) de um nodo O(n) O(\deg(v))
\deg(v) de todos O(n^2) O(n + m)

Graus de um Grafo

Definição: O grau mínimo de um grafo G, denotado \delta(G), é o menor grau de nodo do grafo.

Definição: O grau máximo de um grafo G, denotado \Delta(G), é o maior grau de nodo do grafo.

Definição: Um grafo é k-regular, ou simplesmente regular, quando \delta(G) = \Delta(G) = k (todos os nodos têm o mesmo grau k).

Graus de um Grafo: Exemplos

G_1 =
  • \delta(G_1) = 0
  • \Delta(G_1) = 3
  • G_1 não é regular
G_2 =
  • \delta(G_2) = 1
  • \Delta(G_2) = 1
  • G_2 é 1-regular
G_3 =
  • \delta(G_3) = 3
  • \Delta(G_3) = 3
  • G_3 é 3-regular

?