Projeto e Análise de Algoritmos I

Aula 07 - Operações sobre Grafos, Isomorfismo, Famílias de Grafos, Conectividade, Pseudografos

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.

Operações Sobre Grafos

Operações sobre Grafos

Grafos podem ser manipulados de diversas formas:

  • Complemento, união, interseção, união disjunta
  • Deleção de aresta/vértice
  • Soma, multiplicação

A seguir, veremos algumas dessas operações.

Complemento de Grafos

Definição: O complemento \overline{G} de um grafo simples G = (V,E) é definido por:

\overline{(V,E)} = (V, \{ e \mid e \in 2^V \land |e| = 2 \land e \notin E \} )

Exemplo:

G =
G =

União de Grafos

Definição: A união G_1 \cup G_2 de dois grafos G_1 = (V_1, E_1) e G_2 = (V_2, E_2) é dada por:

(V_1, E_1) \cup (V_2, E_2) = (V_1 \cup V_2, E_1 \cup E_2)

Exemplo:

∪
=

Interseção de Grafos

Definição: A interseção G_1 \cap G_2 de dois grafos G_1 = (V_1, E_1) e G_2 = (V_2, E_2) é dada por:

(V_1, E_1) \cap (V_2, E_2) = (V_1 \cap V_2, E_1 \cap E_2)

Exemplo:

∩
=

Remoção de Aresta

Definição: A remoção de uma aresta e = \{a,b\} de um grafo G = (V,E) produz o grafo G - e:

(V,E) - \{a,b\} = (V, E \setminus \{\{a,b\}\})

Exemplo:

− {1, 2} =

Remoção de Vértice

Definição: A remoção de um vértice v de um grafo G = (V,E) produz o grafo G - v:

(V,E) - v = (V \setminus \{v\}, \ E \setminus \{ e \in E \mid v \in e \})

Exemplo:

− 1 =

Nota: Todas as arestas incidentes ao nó deletado também são removidas.

Isomorfismo

Isomorfismo

Definição: Um isomorfismo entre dois grafos G=(V,E) e G'=(V',E') é uma função bijetora f: V \to V' entre os vértices dos dois grafos tal que: \{u,v \} \in E \Longleftrightarrow \{f(u),f(v)\} \in E'

Definição: Um isomorfismo de G para si mesmo é chamado automorfismo.


A existência de algum isomorfismo entre dois grafos significa que eles têm exatamente a mesma forma, apesar de poderem ter nomes de nodos e arestas distintos, ou serem desenhados de formas diferentes.

Grafos Isomorfos

Definição: Dois grafos G e G' são isomorfos, denotado G \cong G', sss existe um isomorfismo entre eles.


Nota: Pode haver dois ou mais isomorfismos distintos entre dois grafos.


Nota: A relação de isomorfismo (dois grafos são relacionados sss são isomorfos) é uma relação de equivalência.

Isomorfismo: Exercício

Exercício:

G1
G2
G3
G4
G5
  1. Quais grafos acima são isomorfos entre si?
  2. Para os grafos isomorfos: quantos isomorfismos distintos há entre eles?
  3. Apresente algum automorfismo de G_2.

Isomorfismo: Exemplo

  • Os dois grafos abaixo, apesar de aparentemente possuírem formatos distintos, são na verdade isomorfos.

Nota: Esse grafo é chamado grafo de Petersen.

Isomorfismo: Aplicações

  • Grafos são usados para representar estruturas em várias áreas, como visão computacional e reconhecimento de padrões.
  • Nessas áreas, o isomorfismo de grafos aparece como casamento exato de grafos (exact graph matching).
  • Em quimioinformática e química matemática, o teste de isomorfismo é usado para:
    • identificar compostos químicos em bases de dados;
    • gerar grafos moleculares;
    • apoiar síntese computacional.
  • Em automação de projeto eletrônico, o isomorfismo é usado na etapa Layout Versus Schematic (LVS), para verificar se o circuito projetado corresponde ao circuito esquemático.

Isomorfismo: Complexidade

Def. O problema do isomorfismo de grafos é o problema de decidir se dois grafos são isomorfos.

  • Não se sabe se ele pode ser resolvido em tempo polinomial.
  • Também não se sabe se ele é NP-completo.
  • Por isso, é um candidato à classe NP-intermediário.
  • Sabe-se que ele está na low hierarchy de NP.
  • Para várias classes especiais de grafos, há algoritmos polinomiais.
  • Na prática, muitas instâncias podem ser resolvidas eficientemente.


Questão em aberto:

O problema do isomorfismo de grafos pode ser resolvido em tempo polinomial?

Isomorfismo: Algoritmos

  • Em 2015, László Babai anunciou um algoritmo em tempo quase-polinomial para isomorfismo de grafos.
  • Em 2017, houve uma correção na prova, e o resultado quase-polinomial foi mantido.
  • A complexidade anunciada é da forma: 2^{O((\log n)^c)} com evidências de que pode ser 2^{O((\log n)^3)}.
  • Antes disso, o melhor algoritmo teórico conhecido tinha tempo 2^{O(\sqrt{n}\log n)}.
  • Na prática, existem algoritmos eficientes para muitos casos, mas com tempo exponencial no pior caso.

Mensagem principal: O problema de isomorfismo de grafos teve avanços teóricos importantes, mas ainda não se conhece um algoritmo em tempo polinomial.

Grafos Abstratos

Podemos enxergar grafos de duas formas:

  • Concreta: nomes dos nodos e arestas importam, assim como topologia (formato das interconexões).
  • Abstrata: somente topologia importa.


Definição: Um grafo abstrato é uma classe de equivalência de grafos isomorfos.


Exemplo: Grafo abstrato de quatro vértices, totalmente conectado (K_4): \left\{ \begin{gathered} \text{Grafo com vértices } \{a,b,c,d\} \text{ e 6 arestas},\\ \text{Grafo com vértices } \{1,2,3,4\} \text{ e 6 arestas},\\ \text{Grafo com vértices } \{\alpha,\beta,\gamma,\delta\} \text{ e 6 arestas}, \ldots \end{gathered} \right\}

Subgrafo a Menos de Isomorfismo

  • Habitualmente estamos interessados em grafos abstratos, e não nas representações concretas.

  • Podemos estender conceitos como subgrafo para o caso abstrato.


Definição: G é subgrafo de G' a menos de isomorfismo sss existe H \subseteq G' tal que G \cong H.


Exemplo:

G
≅
H
⊆
G'

Famílias de Grafos

Famílias Comuns de Grafos Simples

  • Algumas formas para grafos representam padrões comuns, e portanto recebem nomes especiais (normalmente parametrizados pelo número de vértices).

  • Veremos os seguintes formatos de grafo:

  • Nulo (ou discreto)
  • Completo
  • Caminho
  • Ciclo
  • Grade
  • Estrela
  • Roda
  • k-cubo


Nota: Cada topologia com um dado número de nodos representa um grafo abstrato distinto.

Grafos Nulos e Completos

Grafo nulo: N_n (sem arestas)

N₁
N₂
N₃
N₄
N₅
N₆


Grafo completo: K_n (todas as arestas possíveis)

K₁
K₂
K₃
K₄
K₅
K₆

Curiosidade: K vem da palavra “komplett” em alemão.

Grafos Caminho e Ciclo

Grafo caminho: P_n (path)

P₁
P₂
P₃
P₄
P₅


Grafo ciclo: C_n (para n \geq 3)

C₃
C₄
C₅
C₆
C₇
C₈

Grafos Estrela e Roda

Grafo estrela: S_n (star)

S₁
S₂
S₃
S₄
S₅
S₆
S₇


Grafo roda: W_n (wheel, n \geq 4)

W₄
W₅
W₆
W₇
W₈
W₉

Grafos Grade e k-Cubo

Grafo grade: G_{m,n} (m linhas, n colunas)

G₁,₃ =
G₃,₄ =


Grafo k-cubo: Q_k

Q₀
Q₁
Q₂
Q₃
Q₄

Nota: Ao contrário das outras famílias, onde n representa o número de vértices, k representa as dimensões do cubo.

Famílias Comuns de Grafos Simples: Exercício

Exercício: Determine fórmulas de contagem do número de arestas a partir do número de vértices para as seguintes famílias de grafos:

  • Nulo (ou discreto)
  • Completo
  • Caminho
  • Ciclo
  • Grade
  • Estrela
  • Roda
  • k-cubo

Passeios

Passeios

Passeio

Definição: Um passeio (walk) p entre nodos x e y, denotado p(x,y), é uma sequência alternada p(x,y) = v_0, e_1, v_1, e_2, v_2, \ldots, e_n, v_n de vértices e arestas no qual:

  • x = v_0 e y = v_n;
  • há ao menos uma aresta; e
  • toda aresta e_i conecta os vértices adjacentes v_{i-1} e v_i.

Definição: O tamanho do passeio, denotado |p|, é a quantidade de arestas presentes (contando repetições).

Nota: No caso de grafos simples o passeio é determinado unicamente pelos vértices, portanto podemos escrever simplesmente p(v_1,v_n) = v_1, v_2, \ldots, v_n. Outros tipos de grafos requerem que se nomeie explicitamente as arestas.

Passeio: Exemplo

  • Grafo exemplo (arestas nomeadas):

Exemplos de passeios:

  • p_1(A,B) = A, 1, B \qquad \implies |p_1| = 1
  • p_2(A,E) = A, 1, B, 2, E \qquad \implies |p_2| = 2
  • p_3(B,A) = B, 2, E, 4, D, 3, B, 2, E, 4, D, 3, B, 1, A \qquad \implies |p_3| = 7

Tipos de Passeio

Def. Um passeio p(x,y) é fechado quando x = y.

Def. Uma trilha (trail) é um passeio sem arestas repetidas.

Def. Um caminho (path) é uma trilha p(x,y) sem nodos repetidos (com exceção de x e y, que podem ser iguais).

Def. Nomes especiais para alguns passeios:

  • circuito (circuit): trilha fechada
  • ciclo (cycle): caminho fechado
  • laço (loop): caminho fechado de tamanho 1

%%{init: {'themeVariables': { 'fontSize': '26px' }}}%%
graph TD
  A([Passeio])
  B([Trilha])
  C(["Passeio Fechado"])
  D([Caminho])
  E([Circuito])
  F([Ciclo])
  G([Laço])

  A --> B
  A --> C
  B --> D
  B --> E
  C --> E
  D --> F
  E --> F
  F --> G

  classDef default fill:#23373b,color:#fafafa,stroke:none,font-size:26px;

Propriedades de Passeios

Lema: De todo passeio p(x,y) podemos extrair um caminho c(x,y).

Demonstração: Seja n = |p|. Provaremos por indução em n que todo passeio de tamanho n entre dois vértices contém um caminho entre esses vértices.

Hipótese Indutiva: Para todo k < n, todo passeio de tamanho k entre dois vértices a e b contém um caminho entre a e b.

  • Base: Se n = 1, então p(x,y) = x, y, que já é um caminho.
  • Passo de Indução: Seja p(x,y) um passeio de tamanho n. Podemos escrevê-lo como p = p'(x,v), y, onde p'(x,v) é um sub-passeio de tamanho n-1. Como |p'| = n-1 < n, pela hipótese indutiva existe um caminho c'(x,v).
    • Se y \notin (c' - \{x\}), então a sequência c = c', y não possui vértices repetidos, logo é um caminho de x até y.
    • Se y \in (c' - \{x\}), então existe uma primeira ocorrência de y em c'. Escrevendo c' = x, \ldots, y, \ldots, v, o prefixo de c' até essa primeira ocorrência de y define um caminho de x até y. \blacksquare

Conectividade

Conectividade de Nós

  • Podemos estender a noção de adjacência (nodos ligados por arestas) para conectividade (nodos ligados por rotas).

Definição: Dois nós a e b estão conectados (denotado a \leftrightsquigarrow b) sss:

  • a = b, ou
  • existe um caminho entre a e b.

Definição: A relação de conectividade determina que dois vértices estão relacionados sss estão conectados.

Lema: Em grafos simples, a relação de conectividade é uma relação de equivalência sobre o conjunto de vértices.

Demonstração: Exercício!

Conectividade de Nós: Exercício

Seja G = (V, E) um grafo simples. Defina a relação \sim em V por: u \sim v \iff \text{existe um caminho em } G \text{ ligando } u \text{ a } v.

Mostre que \sim é uma relação de equivalência em V, isto é, prove que:

  1. (Reflexividade) Para todo v \in V, vale v \sim v.
  2. (Simetria) Se u \sim v, então v \sim u.
  3. (Transitividade) Se u \sim v e v \sim w, então u \sim w.

Conclua que as classes de equivalência dessa relação são exatamente as componentes conexas de G.

  • Para a reflexividade, considere o caminho trivial.
  • Para a simetria, observe que caminhos podem ser percorridos no sentido inverso.
  • Para a transitividade, concatene caminhos.

Distância entre Nodos

Seja G = (V,E) um grafo simples.

Definição: A distância entre dois nós a e b, denotada d(a,b), é definida por: d : V \times V \to \mathbb{N} \cup \{\infty\} d(a,b) = \begin{cases} 0 & \text{se } a = b \\ \text{menor comprimento de caminho entre } a \text{ e } b & \text{se } (a \neq b) \land (a \leftrightsquigarrow b) \\ \infty & \text{se } a \not\leftrightsquigarrow b \end{cases}

Conectividade e Distância: Exemplo

Exemplo:

Conectividade:

  • A e A são conectados (iguais).
  • A e F são conectados (caminhos A-B-D-E-F e A-B-E-F).
  • E e C não são conectados.

Distância:

  • d(A,A) = 0
  • d(A,B) = 1
  • d(A,C) = \infty
  • d(B,F) = 2

Componentes Conexos

Grafos Conexos e Desconexos

Definição: Um grafo é conexo quando temos a \leftrightsquigarrow b para todos os vértices a e b.

Definição: Um grafo é desconexo quando existem dois vértices a e b tais que a \not\leftrightsquigarrow b.

Definição: H é um componente conexo de G sss:

  • H é subgrafo conexo de G
  • H não está propriamente contido em nenhum outro subgrafo conexo de G

Em outras palavras, um componente conexo é um subgrafo conexo maximal.

Componentes Conexos: Exercício

Exercício: Para o grafo abaixo, determine todos os componentes conexos.

Resposta: Os subgrafos induzidos pelos conjuntos de vértices \{C\} e \{A, B, D, E, F\}.

Pseudografos

Pseudografos e Multigrafos

Definição: Um pseudografo é uma tripla (V,E,conn) onde:

  • V é um conjunto de vértices
  • E é um conjunto de arestas
  • conn : E \to 2^V associa cada aresta a um subconjunto de V com cardinalidade 2 ou 1.


Definição: Uma aresta e \in E é endoaresta (ou laço) sss |conn(e)| = 1.


Definição: Um multigrafo é um pseudografo (V,E,conn) sem laços (para todo e \in E, |conn(e)| = 2).

Pseudografos: Exemplo

Exemplo:

\begin{aligned} V &= \{ A, B, C, D \} \\ E &= \{ 1, 2, 3, 4 \} \\ conn &= \begin{cases} 1 \mapsto \{A, C\} \\ 2 \mapsto \{A, C\} \\ 3 \mapsto \{A, B\} \\ 4 \mapsto \{D\} \end{cases} \end{aligned}

Nota: Ao contrário de grafos simples, pseudografos admitem arestas paralelas e laços. Multigrafos admitem arestas paralelas mas não admitem laços.

Pseudografos: Ciclos

Definição: Um pseudografo G = (V,E) é cíclico se houver um caminho c(v,v) para algum nodo v \in V. Caso contrário, G é acíclico.


Em pseudografos há mais possibilidades de haver ciclos do que em grafos simples:


Exemplo: (pseudografos cíclicos)


Ciclo de tamanho 2:
Ciclo de tamanho 1:

?