Glossário de Teoria dos Grafos#

Definições#

grafo#

Um par ordenado G = (V(G), E(G)), onde V(G) e E(G) são conjuntos disjuntos, V(G) um conjunto de vértices, E(G) um conjunto de arestas juntamente com uma função de incidência ψ _G que a associa cada aresta de G um par não ordenado de vértices de G.

ψ(e) = {u, v}, se a aresta e liga os vértices u e v - u e v são extremos de e.

incidência#

Os extremos de uma aresta incidem na aresta e a aresta incide em seus extremos.

adjacência#

Dois vértices são adjacentes se incidem numa mesma aresta.

Duas arestas são adjacentes se incidem num mesmo vértice.

vizinhança#

Dois vértices distintos adjacentes são chamados de vizinhos.

N _G (v) é o conjunto de vizinhos do vértice v.

finito#

Grafo onde ambos V(G) e E(G) são finitos.

ordem#

De um grafo G, é o seu número de vértices. Denotado por: v(G), |V(G)| ou n (simplificado).

tamanho#

De um grafo G, é o seu número de arestas. Denotado por: e(G), |E(G)| ou m (simplificado).

laço#

Aresta com extremos idênticos.

ligações#

Aresta com extremos distintos.

arestas paralelas#

Duas ou mais ligações de um mesmo par de vértices.

grafo simples#

Grafo que não tem laços nem arestas paralelas.

grafo completo#

Grafo simples em que todo par de vértices é adjacente. Denotado por K _n.

caminho#

Grafo simples cujos vértices podem ser listados numa sequeência linear, tal que dois vértices são adjacentes se, e só se, são consecutivos na sequência. Denotado por P _n.

ciclo#

Grafo simples com três ou mais vértices, cujos vértices podem ser listados numa sequência cíclica tal que dois vértices são adjacentes se, e só se, são consecutivos na sequência. Denotado por C _n.

C ₁ é um vértice com um laço.

C ₂ é um par de vértices ligados por um par de arestas paralelas.

comprimento (de um caminho ou de um ciclo)#

Número de arestas no caminho/ciclo.

k-caminho/k-ciclo é o caminho/ciclo de comprimento k.

3-ciclo também é chamado de triângulo, assim como o 4-ciclo de quadrilátero e assim por diante.

Teorema: Seja G um grafo tal que δ(G) ≥ 2. Então G contém um ciclo.

grafo conexo#

Grafo em que toda partição de V em dois conjuntos não vazios X e Y, existe uma aresta com um extremo em X e o outro em Y.

O grafo é desconexo se é possível achar uma partição de V em dois conjuntos não vazios X e Y, em que não há arestas com um extremo em X e outro em Y.

grafos disjuntos#

Dois grafos que não têm vértices em comum.

Ver grafos aresta-disjuntos.

grafos aresta-disjuntos#

Dois grafos que não têm arestas em comum.

Ver grafos disjuntos.

união#

De dois grafos simples G e H, denotada G ∪ H tem como vétices V(G) ∪ V(H) e arestas E(G) ∪ E (H).

componente conexo#

Cada grafo resultante da união disjunta de um ou mais grafos.

c(G) é o número de componentes conexas de um grafo.

interseção#

De dois grafos simples G e H, denotada G ∩ H tem como vétices V(G) ∩ V(H) e arestas E(G) ∩ E (H).

grafo nulo#

Grafo sem vértices.

grafo bipartido#

Grafo cujo conjunto de vértices V pode ser particionado em dois conjuntos X e Y tais que cada aresta de G tem um extremo em X e o outro em Y. (X, Y) é uma bipartição do grafo G[X, Y] e X e Y são suas partes.

Se G[X, Y] é simples e todo vértice em X é adjacente a todo vértice em Y, G[X, Y] é bipartido completo.

K _x,y é o grafo bipartido completo em que x = |X| e y = |Y|.

K _1,y ou K _x,1 é chamado estrela.

Teorema: Um grafo é bipartido se e somente se não tem ciclo ımpar.

grau (de um vértice)#

Número de arestas incidentes em v, cada laço contado duas vezes. Denotado por d _G(v).

Um vértice de grau zero é chamado vértice isolado.

Grau mínimo de G é o grau do vértice de menor grau de G, denotado por δ(G). Grau máximo é o grau do vértice de maior grau de G, denotado por ∆(G).

grafo regular#

Grafo k-regular, onde d(v) = k para todo v em V, para algum valor de k.

Grafos 3-regulares são chamados grafos cúbicos.

grafo direcionado#

Grafo D formado por um conjunto de vértices V e outro de arcos A, além de uma função de incidência que associa cada arco de A com um par ordenado de vértices.

Se ψ _{D`(a) = uv, dizemos que ``a`} liga u a v; ou u domina v. u é sua origem (tail) e v o destino (head)

Vértices que dominam v são chamados vizinhos de entrada, N _D ^- (v). Vértices dominados por v são chamados vizinhos de saída, N _D ⁺ (v).

Grafos direcionados estritos, são aqueles que não possuem laços nem arcos paralelos.

grafo direcionado acíclico#

Grafo dirigido sem ciclo; isto é, para qualquer vértice v, não há nenhuma ligação dirigida começando e acabando em v.

orientação#

Grafo D resultante da substituição das arestas de um grafo G por arcos correspondentes.

grafo orientado#

Orientação de um grafo simples.

ordem (de um grafo)#

Número de vértices de um grafo.

tamanho (de um grafo)#

Número arestas de um grafo.

torneio#

Qualquer orientação de um grafo completo.

Isomorfismo#

isomorfismo#

Função que mapeia os vértices e aresta de dois grafos que têm a mesma estrutura, diferindo apenas nos rótulos dos vértices e das arestas.

complemento#

Grafo simples G’ cujo conjunto de vértices é V e o conjunto de arestas é dado pelos pares de vértices não adjacentes em G.

autocomplementar#

Grafo isomorfo ao seu complemento.

automorfismo#

Isomorfismo do grafo consigo mesmo.

Aut(G) conjunto de automorfismos de G.

similaridade#

Dois vértices u e v de um grafo simples são similares se existe automorfismo que mapeia u em v.

Duas arestas uv e xy são similares se existe automorfismo que mapeia uv em xy.

grafo vértice-transitivo#

Grafo em que todo par de vértices é similar.

grafo aresta-transitivo#

Grafo em que todo par de vértices é similar

Subgrafos#

remoções#

Remoção de uma aresta e de um grafo G resulta no grafo denotado G e.

Remoção de um vértice v de um grafo G resulta no grafo denotado G − v.

subgrafo#

Um grafo F é subgrafo de G se V(F) ⊆ V(G), E(F) ⊆ E(G) e ψ _F é a restrição de ψ _G a E(F).

G contém F e F está contido em G, denotado G ⊇ F e F ⊆ G respectivamente.

F pode ser obtido a partir de operações de remoção de vértices e arestas.

supergrafo#

Um grafo H é supergrafo de G se contém G, H ⊇ G.

Todo grafo é supergrafo de si mesmo.

subgrafo ou supergrafo próprio#

Subgrafos F e supergrafos H de G, denotados por F ⊂ G e G ⊃ H, respectivamente.

subgrafo gerador#

Subgrafo F obtido a partir de um grafo G pela remoção de arestas.

Se S é o conjunto de arestas removidas F é o grafo G S.

V(F) = V(G).

hamiltoniano#

Um caminho hamiltoniano - ou ciclo hamiltoniano - é aquele que é gerador de um dado grafo.

O grafo hamiltoniano possui um ciclo hamiltoniano.

Teorema de Rédei: Todo torneio tem um caminho hamiltoniano direcionado.

Problema do Caixeiro Viajante#

Dado um grafo ponderado (G , w ), encontre um ciclo hamiltoniano de G de peso mínimo.

k-fator#

Subgrafo gerador k-regular. 1-fator também é chamado emparelhamento perfeito.

subgrafo induzido#

Subgrafo induzido/gerado F obtido a partir de G pela remoção de vértices.

Toda aresta de E(G) com ambos os extremos em V(F) também é aresta de E(F).

Se X é o conjunto de vértices removidos F é o grafo G − X.

grafo ponderado#

Grafo no qual cada aresta tem um número real denominado peso w(e) associado à ela.

peso#

De um grafo G, d(G), é a somatória dos pesos de suas arestas.

De uma aresta é o número real associado à ela.

identificação#

Operação de substituição de dois vértices - x e y - por um único vértice incidente em todas as arestas em que x e y incidiam. O grafo resultante é denotado por G/{x, y}.

contração#

Operação de remoção de uma aresta e seguida da contração de seus extremos. O grafo resultante é denotado por G/e.

decomposição#

Família de subgrafos aresta-disjuntos de G tais que a união do conjunto de arestas de cada subgrafo da família resulta no conjnto de arestas do grafo original G.

grafo par#

Grafo em que todo vértice tem grau par.

Teorema de Veblen: Um grafo admite uma decomposição em ciclos se e somente se é par.

Teorema: Um grafo é par se e somente se |∂(X)| é par para todo subconjunto X de V.

cobertura#

Família de subgrafos não necessariamente aresta-disjuntos de G tais que a união do conjunto de arestas de cada subgrafo da família resulta no conjunto de arestas do grafo original G.

É chamada uniforme se cobre cada aresta de G o mesmo número de vezes. Se k é o número de vezes, a cobertura é denominada k-cobertura.

corte#

Seja E[X, Y] o conjunto de arestas de G com um extremo em X e o outro em Y.

Quando Y = V − X, E[X, Y] ́é chamado de corte (cut) de X em G e denotado por ∂(X).

Um corte ∂(X) respeita um conjunto de arestas A se A ∩ ∂(X) = ⦰.

aresta leve#

Em um corte ∂(S) se w _uv := min _{(x,y) ∊ ∂(S)} {w _xy } - (u,v) é a aresta de menor peso no corte ∂(S).

corte trivial#

É dado por todas as arestas incidentes em v e denotado por ∂(v).

Conexidade#

passeio#

Sequência W = v ₀ e ₁ v ₁ … e _l v _l cujos elementos são vértices e arestas **não necessariamente* distintos, tal que para todo 1 ≤ i ≤ l, v _i-1 e v _i são extremos de e.

Se v ₀ = x e v _l = y, W conecta x a y e é um passeio de x a y.

Qualquer subsequência com vértice de início u e vértice de término v é chamada segmento de W e denotada por uWv.

Um passeio é fechado (closed) se os vértices de início e término coincidem.

trilha#

Passeio em que não existe repetiçào de arestas.

caminho#

Passeio em que não existe repetição de vértices, nem arestas.

conexidade#

Dois vértices u e v estão conectados se existe um passeio de u a v no grafo.

O grafo é conexo se todo par de vértices está conectado.

distância#

Comprimento do menor caminho de u a v em G, denotado por d _{G(u, v)} .

aresta de corte#

Aresta e que quando removida aumenta o número de componentes conexas de G, ou seja, c(G e) = c(G) + 1.

Preposição: Uma aresta e de um grafo G é uma aresta de corte se e somente se e não pertence a um ciclo de G.

trilha euleriana#

Trilha que passa por cada aresta do grafo exatamente uma vez.

circuito euleriano#

Trilha Euleriana fechada.

grafo euleriano#

Grafo conexo e que possui um circuito Euleriano.

Teorema: Um grafo conexo é euleriano se e somente se é par.

Árvores#

árvore#

Grafo T conexo e acíclico.

Preposição: Em uma árvore, quaisquer dois vértices são conectados por precisamente um caminho.

Teorema: Se T é uma árvore, então e(T) = v (T) − 1.

floresta#

Grafo acíclico não necessariamente conexo.

folha#

Vértice de grau um em uma árvore.

Preposição: Toda árvore nào trivial tem pelo menos duas folhas.

árvore geradora#

Árvore subgrafo gerador de um grafo.

Teorema: Um grafo é conexo se e somente se tem uma árvore geradora.

áarrvore com raiz#

Árvore com um vértice x chamado de raiz, denotado por T(x).

arborescência#

Orientação de uma árvore com raiz em que todo vértice exceto a raiz tem grau de entrada 1.

Buscas em Grafos#

alcance#

Um vértice u é alcançável a partir de um vértice v de um grafo G se existe um caminho de v para u em G.

distância#

Um vértice u está a uma distância k de um vértice v se k é o comprimento do menor caminho que começa em v e termina em u.

Se u não é alcançável a partir de v, determina-se que a distância entre eles é infinita.

busca em largura#

Busca em largura ou BFS (Breadth First Search) em um grafo G = (V, E).

Método em que, partindo-se de um vértice especial u, denominado raiz da busca, percorre-se G visitando todos os vértices alcançáveis a partir de u em ordem crescente de distância.

Complexidade: O(|V| + |E|)

busca em profundidade#

Busca em profundidade ou DFS (Depth First Search) em um grafo G = (V, E).

Método em que, partindo-se de um vértice especial u, denominado raiz da busca, percorre-se G visitando todos os vértices alcançáveis a partir de u tendo como meta atingir primeiramente as folhas, retornando quando isso acontecer. Generalização do percurso em pré-ordem.

Variáveis podem ser usadas para a marcação de tempo como instante de descoberta d e de exploração f.

Complexidade: O(|V| + |E|)

Classificação de arestas

Dada uma floresta G _pred construída pela DFS:

aresta da floresta

Toda aresta em G _pred .

aresta de retorno

É uma aresta (u, v) onde v é ancestral de u em G _pred .

aresta direta

É uma aresta (u, v) que não está em G _pred onde v é descendente de u em uma árvore contruída pela DFS.

aresta cruzada

Todas as arestas que não podem ser classificadas como de retorno ou diretas.

Teorema: Em uma DFS de um grafo não direcionado G = (V, E) toda aresta é da árvore ou é de retorno.

ordenação topológica#

Em um grafo direcionado acíclico G = (V, E), é uma ordem linear dos vértices tal que, para todo arco (u, v) em E, u _antecede_ v na ordem.

Lema: Um grafo direcionado G é acíclico se e somente se uma bisca em peofundidade em G não classifica nenhum arco como sendo de retorno.

Teorema: Rotular os vértices do grafo em ordem decrescente dos valores f obtidos em uma DFS resulta em uma ordenação topológica correta de um grafo direcionado acíclico G.

Componentes Fortemente Conexas#

componentes fortemente conexas#

Uma componente fortemente conexa (CFC) H de um grafo G = (V, E) é um subconjunto de vértices tal que, para todo par de vértices u e v de H, existe um caminho de u para v e vice-versa. H também é maximal com relação a inclusão de vértices.

grafo transposto#

É o grafo G ^T = (V, E ^T ) de um grafo direcionado G = (V, E) onde:

E ^T = {(u, v) ∊ V x V: (v, u) ∊ E}

o grafo obtido invertendo-se a orientação de seus arcos.

G e G ^T têm as mesmas componentes fortemente conexas.

Árvore Geradora Mínima#

árvore geradora mínima#

Árvore gerada pelo problema da Árvore Geradora Mínima:

Dado um grafo não orientado ponderado G = (V, E), onde w: E → ℝ ⁺ define os custos das arestas, encontrar um subgrafo gerador conexo T de G tal que, para todo subgrafo gerador conexo T’ de G

Σ _{e ∊ T} w _e ≤ Σ _{e ∊ T’} w _e .

Características

Só tem solução se G é conexo. + Resulta em uma árvore - a Árvore Geradora Mínima (AGM) - dado que tal subgrafo não conterá ciclos.

Algoritmos

Algoritmo genérico: estratégia gulosa.

Invariante: Antes de cada iteração A é um subconjunto de arestas de uma AGM. A cada iteração A ∪ {(u, v)}, (u, v) é chamada aresta segura.

AGM-Generico(G, w)

A ← 0; enquanto A não forma uma árvore geradora faça encontre aresta segura (u, v); A ← A ∪ {(u, v)}; retorne A.

Teorema: Seja G = (V, E) um grafo conexo não orientado ponderado nas arestas por uma função w: E → ℝ. Seja A um subconjunto de E que está contido em alguma AGM de G, seja ainda ∂(S) um corte de G que respeita A e (u, v) uma aresta leve de ∂(S). Então, (u, v) é uma aresta segura para A.

Corolário: Seja G = (V, E) um grafo conexo não orientado ponderado nas arestas por uma função w: E → ℝ ⁺ . Seja A um subconjunto de E que está contido em alguma AGM de G, e seja C = (V _C , E _C ) uma componente conexa (árvore) da floresta G _A = (V, A). Se (u, v) uma aresta leve de ∂(C), então (u, v) é segura para A.

Os algoritmos de Prim e de Kruskal especializam o algoritmo genérico usando o Colorário.

Prim#

Dado o colorário.

A é sempre uma árvore. A aresta segura adicionada a A é sempre uma aresta leve do corte ∂(C), onde C é o conjunto de vértices que sÃo extremidades de arestas em A.

Kruskal#

Dado o colorário.

A é sempre uma floresta. A aresta segura adicionada a A é sempre uma aresta de menor peso dentre todas as arestas ligando dois vértices de componentes distintas de G _A .

Caminhos Mínimos#

caminhos mínimos#

Caminhos que se deseja encontrar no problema de Caminhos Mínimos:

Dados um grafo conexo ponderado G = (V, E), direcionado ou não, onde d: E → ℝ ⁺ define as distâncias entre os extremos das arestas, e um vértice r de G, queremos encontrar, para todo vértice u de G um caminho C de distância mínima de r a u, ou seja, o caminho C deve ser tal que, para todo caminho C de r a u em G :

∑ _{e ∊ C} d _e ≤ ∑ _{e ∊ C’} d _e .

Algoritmos

Dijkstra

Grafos direcionados ou não direcionados sem arestas de peso negativo.

Bellman-Ford

Grafos direcionados com arestas de peso negativo e sem ciclos negativos.

Ordenação topológica

Para DAGs, basta calcular os caminhos mínimos analisando os vértices segundo a ordenação topológica. Funciona mesmo com arestas de peso negativo.

Caminhos mínimos entre todos os pares de vértices

Dijkstra

Entre todos os vértices quando o grafo é esparso.

Floyd-Warshall

Quando o grafo é denso.

Dijkstra#

Algoritmo para encontrar caminhos mínimos a partir de um vértice r. Resulta numa árvore geradora com raiz em r - árvore de caminhos mínimos para r: ACM(r).

Características

Funciona para grafos direcionados e não direcionados desde que não haja arestas de peso negativo.

Ver Algoritmo de Prim.

Bellman-Ford#

Algoritmo para encontrar caminhos mínimos a partir de um vértice r.

Características

Funciona para grafos direcionados não haja ciclos negativos.
Detecta a existência de ciclos negativos.

Floyd-Warshall#

Algoritmo para encontrar caminhos mínimos entre todos os pares de vértices de um grafo.

Características

Usado quando o grafo é denso
Funciona mesmo na presença de arestas de peso negativo, desde que não haja ciclos negativos
É possível detectar a existência de ciclo negativo analisando a matriz resultado do algoritmo.