Aula 09 - Cliques. Conjuntos Independentes. Árvores. Grafos Bipartidos e k-Partidos. Dígrafos.
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.
Definição: Um clique de G é um subgrafo induzido H \subseteq G tal que H \cong K_n (para algum n \geq 1).
Definição: Um clique de G é maximal sss não está contido propriamente em nenhum outro clique de G.
Exercício: Para o grafo abaixo, determine os componentes conexos, os cliques e os cliques maximais:
Definição: Um conjunto independente de G = (V,E) é um subconjunto de V onde nenhum par de vértices é adjacente.
Definição: Um conjunto independente de G é maximal se não pudermos adicionar nenhum vértice a ele sem introduzir uma aresta.
Exercício: Para o grafo abaixo, determine os conjuntos independentes e os conjuntos independentes maximais:
Nota: Como C é isolado, todo conjunto independente maximal de G obrigatoriamente contém C.
Definição: Um grafo G é cíclico sss existe um subgrafo G' \subseteq G tal que G' \cong C_k (para algum k \geq 3).
Definição: Um grafo é acíclico se não for cíclico.
Exemplo:
Grafo Cíclico (G_1):
Grafo Acíclico (G_2):
Definição: Um grafo simples é chamado floresta se é acíclico.
Exemplo:
Definição: Um grafo simples é chamado árvore se é conexo e acíclico.
Exemplo:
Definição: Uma árvore enraizada é uma tupla (G,v) onde G = (V,E) é uma árvore e v \in V é um nó especial chamado raiz.
Exemplo:
Nota: Distintas escolhas de raiz caracterizam diferentes árvores enraizadas.
Def. As quatro definições abaixo são equivalentes e determinam que um grafo G=(V,E) com n vértices é uma árvore:
- G é conexo e acíclico
- G é conexo e possui n-1 arestas
- G possui n-1 arestas e não há ciclos
- Para dois vértices a,b \in V, há um único caminho c(a,b) os conectando
Demonstração:
- (1) \Rightarrow (2) \land (3)
- (2) \Rightarrow (1) \land (3)
- (3) \Rightarrow (1) \land (2)
- (1) \Rightarrow (4)
- (4) \Rightarrow (1)
Def. Um grafo simples G = (V,E) é bipartido sss V = V_1 \cup V_2 onde:
- V_1 \cap V_2 = \varnothing (conjuntos disjuntos)
- V_1 e V_2 são ambos conjuntos independentes de vértices de G (não há arestas internas a V_1 ou a V_2)
Intuição: toda aresta conecta um vértice de V_1 a um vértice de V_2.
Exemplo:
\begin{aligned} V &= \{A,B,C,D,E,F\} \\ V_1 &= \{A,B,C\} \quad \text{(azul)} \\ V_2 &= \{D,E,F\} \quad \text{(vermelho)} \end{aligned}
Definição: Um grafo bipartido é bipartido completo quando possui todas as arestas possíveis entre V_1 e V_2.
Notação: K_{m,n} (onde m = |V_1| e n = |V_2| são as cardinalidades das partes).
Exemplo: K_{2,3}
Def. Um grafo simples G = (V,E) é k-partido sss V = V_1 \cup V_2 \cup \dots \cup V_k onde:
- V_1, \dots, V_k são todos mutuamente disjuntos par a par (V_i \cap V_j = \varnothing para i \neq j)
- V_1, \dots, V_k são todos conjuntos independentes de vértices de G
Intuição: extensão da noção de grafo bipartido para k classes de vértices.
Exemplo: (Grafo Tripartido)
\begin{aligned} V &= \{A,B,C,D,E,F\} \\ V_1 &= \{A,B\} \quad \text{(azul)} \\ V_2 &= \{D,E\} \quad \text{(vermelho)} \\ V_3 &= \{C,F\} \quad \text{(verde)} \end{aligned}
Exercício: Verifique se os grafos com as seguintes topologias são bipartidos ou não:
Lema: Todo passeio fechado p de tamanho ímpar contém um ciclo c de tamanho ímpar.
Demonstração: Por indução no tamanho de p, n=|p|:
Caso base: Tamanho 3 em grafos simples. O próprio passeio p é um ciclo ímpar c.
Passo indutivo: Pela hipótese indutiva, a propriedade vale para todo passeio fechado p' com |p'| < |p|. Duas possibilidades para p:
Se p não contém repetição de vértices (além do início e fim), então p é diretamente o ciclo ímpar c.
Se p contém repetição de um vértice v, então v divide p em dois subpasseios fechados q e q'. Como |p| = |q| + |q'| é ímpar, um dos subpasseios (digamos q) tem tamanho ímpar com |q| < |p|. Pela hipótese indutiva, q contém um ciclo ímpar. \blacksquare
Passeio original p (u \to u): |p| = 7 (ímpar)
Divisão no vértice repetido v:
Propriedade da paridade: |p| = |q'| + |q| = \text{ímpar} \implies \text{um deles é ímpar}
Redução indutiva: Como |q| = 3 < |p| é ímpar, pela H.I. ele contém um ciclo ímpar (no exemplo, o próprio triângulo v, w_1, w_2, v).
Teorema: (König, 1936) Um grafo é bipartido sss não contém nenhum ciclo de tamanho ímpar.
Demonstração: (\Rightarrow) (Suponha que G é bipartido.)
Teorema: (König, 1936) Um grafo é bipartido sss não contém nenhum ciclo de tamanho ímpar.
Demonstração: (\Leftarrow) (Suponha que G não contenha ciclos de tamanho ímpar.)
Seja H um componente conexo de G e fixe u \in V(H). Classificamos os vértices de H em: X = \{ v \in V(H) \mid d(u,v) \text{ é par} \}, \qquad Y = \{ v \in V(H) \mid d(u,v) \text{ é ímpar} \}
Se houvesse aresta \{a,b\} interna a X (ou a Y), os menores caminhos de u até a e de u até b formariam, junto com \{a,b\}, um passeio fechado de tamanho ímpar u \dots a - b \dots u.
Pelo lema anterior, haveria um ciclo ímpar (contradição).
Portanto, X e Y são conjuntos independentes e X \cup Y = V(H). \blacksquare
Definição: Um dígrafo (ou grafo dirigido) é uma tripla (V, E, conn) onde:
- V é um conjunto de vértices
- E é um conjunto de arestas
- conn: E \to V \times V associa cada aresta e a um par ordenado (a,b) de vértices incidentes, onde:
- a representa a origem de e. Notação: src(e) = a.
- b representa o destino de e. Notação: tgt(e) = b.
Desenhamos uma aresta e na qual conn(e) = (a,b) como uma seta de a para b:
a \xrightarrow{\ \ e\ \ } b
Exemplo:
\begin{aligned} V &= \{ A, B, C, D \} \\ E &= \{ 1, 2, 3, 4, 5, 6 \} \\ conn &= \begin{cases} 1 \mapsto (A,C) \\ 2 \mapsto (C,A) \\ 3 \mapsto (B,A) \\ 4 \mapsto (D,B) \\ 5 \mapsto (D,B) \\ 6 \mapsto (D,D) \end{cases} \end{aligned}
Nota: Dígrafos não impõem restrições sobre os pares de nodos, permitindo laços e múltiplas arestas.
Preenchimento da matriz de incidência de um dígrafo:
Exemplo:
| A | B | C | D | |
|---|---|---|---|---|
| 1 | 1 | 0 | -1 | 0 |
| 2 | -1 | 0 | 1 | 0 |
| 3 | -1 | 1 | 0 | 0 |
| 4 | 0 | -1 | 0 | 1 |
| 5 | 0 | -1 | 0 | 1 |
| 6 | 0 | 0 | 0 | 2 |
Nota: Varia de autor associar (1/-1) ou (-1/1) à origem/destino das setas. Nesta disciplina usaremos (1/-1).
Preenchimento da matriz de adjacência de um dígrafo:
Exemplo:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 0 | 1 | 0 |
| B | 1 | 0 | 0 | 0 |
| C | 1 | 0 | 0 | 0 |
| D | 0 | 2 | 0 | 1 |
Nota: A matriz de adjacência não possui nenhuma restrição de simetria (apenas que todos os valores sejam inteiros não-negativos).
Definição: Cada vértice v em um dígrafo (V,E,conn) possui dois graus:
Grau de entrada deg^-(v): deg^-(v) = |\{ e \mid e \in E \land tgt(e) = v \}| (número de arestas com destino v)
Grau de saída deg^+(v): deg^+(v) = |\{ e \mid e \in E \land src(e) = v \}| (número de arestas com origem v)
Lema: Em todo dígrafo D = (V,E,conn):
\sum_{v \in V} deg^-(v) = \sum_{v \in V} deg^+(v) = |E|
Noções relativas a passeios em dígrafos são as mesmas que em pseudografos, levando-se em consideração a direcionalidade.
Nota: A diferença entre um dígrafo cíclico e acíclico pode ser somente a direcionalidade das setas.
Exemplo:
Grafos direcionados acíclicos (GDAs ou DAGs, Directed Acyclic Graphs) são amplamente utilizados para descrever conjuntos de tarefas e suas dependências (workflow).
Definição: O grafo subjacente de um dígrafo é o pseudografo obtido ao ignorarmos a direcionalidade das arestas.
Exemplo:
Definição: Um dígrafo é fracamente conexo quando seu grafo subjacente é conexo.
Definição: Um dígrafo é fortemente conexo se entre qualquer par ordenado de nodos existe um caminho direcionado.
Existem muitos cenários onde é interessante anotar vértices ou arestas de um grafo (ou dígrafo) com valores:
Exemplo:
Tipos de valores:
A associação é formalizada por funções de valoração.
Definição: Um dígrafo com pesos nas arestas é uma tupla (V, E, conn, w) onde:
- (V, E, conn) é um dígrafo
- w : E \to \mathbb{R} é uma função que associa a cada aresta um número real.
Nota: Pode-se definir grafos e dígrafos com pesos em vértices de forma similar, através de uma função w_V : V \to \mathbb{R}.
Definição: O peso de um passeio em um grafo com pesos nas arestas é a soma dos pesos de todas as arestas do passeio.
Definição: A distância entre dois vértices a e b, denotada d(a,b), é definida por:
d : V \times V \to \mathbb{R} \cup \{\infty, -\infty\}
d(a,b) = \begin{cases} 0 & \text{se } a = b \text{ (sem ciclo negativo em } a\text{)} \\ \text{menor peso de passeio de } a \text{ a } b \\ -\infty & \text{se há passeios sem limite inferior} \\ \infty & \text{se não há passeio de } a \text{ para } b \end{cases}
Exemplo:
\begin{aligned} V &= \{ A, B, C, D, E \} \\ E &= \{ a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8 \} \end{aligned}
\begin{array}{l} conn: \\ a_1 \mapsto (A,B) \\ a_2 \mapsto (A,C) \\ a_3 \mapsto (B,D) \\ a_4 \mapsto (B,E) \\ a_5 \mapsto (C,C) \\ a_6 \mapsto (C,D) \\ a_7 \mapsto (D,B) \\ a_8 \mapsto (D,E) \end{array} \qquad \begin{array}{l} w: \\ a_1 \mapsto 7 \\ a_2 \mapsto 5 \\ a_3 \mapsto 1 \\ a_4 \mapsto 1 \\ a_5 \mapsto 2 \\ a_6 \mapsto 3 \\ a_7 \mapsto 2 \\ a_8 \mapsto 6 \end{array}
Nota: É comum omitir os identificadores internos das arestas na representação gráfica e apresentar diretamente seus pesos.
Representamos dígrafos com pesos nas arestas através de um dicionário de listas de tuplas (destino, peso):
Nota: Vértices sem arestas de saída (como
'E') são mapeados para a lista vazia[]para constarem explicitamente em V(G).
Iteração e manipulação com listas de tuplas:
?