ÁRVORE

• Uma árvore é um grafo conexo sem ciclos
• Seja G(V,A) um grafo com ordem n≥2. As propriedades seguintes são equivalentes e suficientes para caracterizar G como uma árvore:
• G é conexo e sem ciclos;
• G é sem ciclos e tem n-1 arestas;
• G é conexo e tem n-1 arestas;
• G é sem ciclos e por adição de uma aresta se cria um ciclo e somente um;
• G é conexo, mas deixa de sê-lo se uma aresta é suprimida (todas as arestas são pontes);
• Todo par de vértices de G é unido por uma e somente uma cadeia simples.

Arborescência

• Uma arborescência é uma árvore que possui uma raiz. Aplica-se, portanto, somente a grafos orientados.

Floresta

• Uma floresta é um grafo cujas componentes conexas são árvores.

• Nessa parte do curso vamos estudar duas técnicas para identificar, entre dois vértices de um grafo valorado, o caminho de menor peso (Caminho Mínimo). Essa abordagem utiliza um algoritmo guloso, o algoritmo de Dijkstra.

Algoritmo de Dijkstra

Descrição do algoritmo

• O algoritmo de Dijkstra identifica, a partir de um vértice do grafo, qual é o custo mínimo entre esse vértice e todos os outros do grafo. No início, o conjunto S contém somente esse vértice, chamado origem. A cada passo, selecionamos no conjunto de vértices sobrando, o que é o mais perto da origem. Depois atualizamos, para cada vértice sobrando, a sua distância em relação à origem. Se passando pelo novo vértice acrescentando, a distância fica menor, é essa nova distância que será memorizada.
• Suponhamos que o grafo é representado por uma matriz de adjacência onde temos o valor se não existe aresta entre dois vértices. Suponhamos também que os vértices do grafo são enumerados de 1 até n, isto é, o conjunto de vértices é N = {1,2,...,n}. Utilizaremos também um vetor D[2...n] que conterá a distância que separa todo vértice do vértice 1 (o vértice do grafo que é o vértice 1 é escolhido arbitrariamente). Eis o algoritmo:
• Função Dijkstra (L = [1...n, 1...n]:grafo): vetor[2...n];
• C:={2,3,...,n} {Implicitamente S = N - C};
• Para i:=2 até n:
• D[i] := L[1,i].
• Repetir n-2 vezes:
• v:= Elemento de C que minimiza D[v]
• C:= C - {v}
•  Para cada elemento w de C:
• D[w]:= min(D[w],D[v]+L[v,w])
• Retornar D
• Para entender melhor o algoritmo, considere o grafo direcionado ilustrado na figura 1.

• As etapas da execução do algoritmo são as seguintes:

• Da maneira que o algoritmo foi apresentado, obtemos o custo do caminho mínimo para quaisquer vértices, mas não obtemos o caminho mínimo. Para identificar esse caminho mínimo, é só acrescentar mais um vetor P[2..n], onde P[v] indica o vértice que precede v no caminho mais curto. A modificação do algoritmo para obter esse vetor é simples. Primeiro devemos iniciar esse vetor. Segundo, no mesmo momento que o vetor D é atualizado, atualizamos também o vetor P. O algoritmo modificado é o seguinte:
• Função Dijkstra (L = [1..n, 1..n]:grafo): vetor [2..n]
• C:= {2,3,...,n}
• Para i:=2 até n:
• D[i]:= L[1,i]
• P[i]:= 1
• Repetir n-2 vezes:
• v:= Elemento de C que minimiza D[v]
• C:= C - {v}
• Para cada elemento w de C:
• Se D[w] > D[v] + L[v,w] então
• D[w]:= D[v] + L[v,w]
• P[w]:= v
• Retornar P
• Com esse algoritmo modificado, as etapas da execução são as seguintes:

• Vemos que o estado final do vetor P é [3,1,5,1]. Para saber qual é o caminho mais curto entre os vértices 1 e 2, procuramos o valor na posição 2 desse vetor (não esqueça que P e D são indexados a partir de 2). O vetor indica que o último vértice antes do vértice 2 é o vértice 3. Repetimos de novo o mesmo processo para ver o caminho mais curto entre 1 e 3. No vetor, na posição 3, temos o valor 1, que é a origem. Então, o caminho mais curto é 1,3,2.
• Prova que o algoritmo funciona corretamente
• Para efetuar a prova, vamos primeiro definir o conceito de caminho especial mais curto. Seja v¹ a origem. Para qualquer vértice v𝒊 que não faz parte do conjunto S, o caminho espacial mais curto para alcançar v𝒊 a partir de v¹ e que passa somente por vértices do conjunto S.
• Para provar que o algoritmo funciona corretamente, é só provar o seguinte:
• Se um vértice i pertence ao conjunto S, então D[i] contém o comprimento do caminho mais curto entre a origem e i.
• Se um vértice i não faz parte do conjunto S, então D[i] contém o comprimento do caminho especial mais curto entre a origem e i.
• A prova é por indução. Inicialmente os valores no vetor D contêm o valor da aresta que liga cada vértice ao vértice 1 (valor infinito se não tem aresta). Nenhum dos vértices, com a exceção do vértice 1, faz parte de S. Portanto, é trivial conferir que as duas propriedade são verdadeiras nesse caso. Isso é a base da indução. A hipótese de indução supõe que as duas condições são verdadeiras imediatamente antes de acrescentar um novo vértice v no conjunto S. Vamos ver agora o que acontece quando acrescentamos v no conjunto S.
• Para cada vértice que já estava no conjunto S antes de acrescentar v, a primeira propriedade continua verdadeira. Por hipótese de indução, já sabemos que D[v] é a distância do caminho especial mais curto até v. Se conseguirmos provar que o caminho mais curto até v passa somente por vértices do conjunto S, teremos a prova que D[v] é o valor do caminho mais curto e que acrescentando v no conjunto S respeitamos a primeira propriedade. Vamos supor então que existe um outro caminho mais curto até v. Consideramos agora x, o primeiro vértice desse caminho alternativo que não pertence a S. Isso é ilustrado na figura 2, onde em vermelho é indicado o caminho mais curto, e em preto o caminho especial mais curto.

• Nesse caso, supondo que o grafo não contém nenhum peso negativo, a distância até v passando por x é maior ou igual à distância até x. Como esse caminho começa com um caminho especial até x e que por indução o comprimento D[x] dessa parte do caminho é miníma, sabemos que a distância total até v passando por x é maior ou igual a D[x]. Como v foi selecionado antes de x, devemos ter também D[x] D[v]. Isso implica que o caminho em vermelho, que é supostamente mais curto, deve possuir um comprimento maior ou igual ao comprimento do caminho especial indicado em preto, o que contradiz a hipótese. Portanto o caminho especial até v é o mais curto.
• Consideramos agora o que aconteceu com os outros vértices diferentes de v que ficam fora do conjunto S. Seja w tal vértice. Quando v é acrescentado no conjunto S tem duas possibilidades no que concerne o caminho especial mais curto até w: ou ele fica igual, ou ele passa agora por v. Vamos então considerar o segundo caso.
• Parece que ainda tem duas possibilidades: ou o vértice v é o último no caminho até w ou ele não é. Vamos mostrar que o primeiro caso nunca vai acontecer. Suponhamos que o último vértice antes de chegar a w é um vértice x diferente de v, como ilustrado na figura 3.

• Esse caminho não pode ser mais curto, pois já existe um caminho mais curto (ou igual) até x que não inclui v (isso porque x já estava em S antes da adição de v e por indução já tínhamos um caminho mais curto). Então, o caminho especial mais curto é o menor entre o que passa por v antes de chegar a w e o que tínhamos antes de acrescentar v. E isso é exatamente o que o algoritmo verifica.

Algoritmo de Floyd - Warshall

• Foi desenvolvido independentemente três vezes por Bernard Roy, Stephen Warshall e Robert Floyd em 1958, ele encontra o menor caminho entre todos i soares de vértices de um grafo valorado. Vale ressaltar que ele apenas encontra os valores de tais caminhos, e não a sequência de arestas a ser percorrida.
• Exemplo: Em uma situação prática, poderíamos pensar, em como avaliar o melhor local para instalarmos uma loja.
• De fato, podemos definir como melhor local aquele que diminui a distância entre as lojas e locais estratégicos e importantes para ela.
• Exemplos em um centro urbano.
• Um bairro onde o consumo dos produtos vendidos por ela é alto;
• Estabelecimentos que prestarão serviços para a loja;
• Um local onde se tenha uma grande concentração de um público alvo para a loja.
• É fácil notar que este lugar será um ponto "central", ou seja, um lugar que minimiza a distância máxima ou média de todos os outros pontos considerados até ele.

• Exemplo: A entrada para o algoritmo é a matriz k0, obtida a partir da matriz de custos do grafo, efetuando-se a mudança de trocar ZERO por INFINITO. A cada passo do algoritmo, uma nova matriz kn (n = 1,2,...) é calculada. A última matriz é a resposta dos caminhos mínimos. Então, indicando que os caminhos mínimos estão indicados por linha - coluna, ou seja, referenciando as linhas e colunas como 1,2,3,4 e 5, assim o valor do caminho mínimo de 1-5 é 2, 2-1 é 3 e assim por diante. Esses resultados são de sentido único, ou seja, não passam pelo mesmo caminho para voltar. Os valores ZERO (0) significam que não há rota possível entre os dois pontos.

Grafos Eulerianos

Definição

• Um grafo conexo G é Euleriano se existir uma trilha fechada que inclua todas as arestas de G.
• Esta trilha é chamada de Trilha Euleriana

• Trilha Euleriana: {A,B,C,D,E,C,G,F,E,G,B,F,A}
• Portanto G é um Grafo Euleriano.
• Teorema 1: Um grafo conexo G é Euleriano se cada vértice de G possui grau par.
• *Ou seja, se o grafo é euleriano todos os vértices tem grau par, e além disto, se todos os vértices do grafo tem grau par então o grafo é Euleriano. Lembre-se que A se B é equivalente a Se A então B e Se B então A.
• **Dizemos também que o teorema oferece uma condição necessária e suficiente para que um grafo seja Euleriano. Este tipo de condição costuma ser bastante útil na produção de algoritmos de reconhecimento (no caso, para reconhecer se um grafo é Euleriano ou não basta verificar a paridade dos graus de seus vértices).

Prova:

• Parte I (→). {"A ida": Se um grafo conexo G é Euleriano então cada vértice de G possui grau par}
• // G é Euleriano → ∀  v ∈ VG, Gr(v) é par.
• Tomemos um grafo euleriano G.
• Seja T uma trilha euleriana de G com origem em u.
• Seja v um vértice qualquer de T.
• Caso 1: v ≠ u {Todos os vértices internos da trilha tem grau par}
• Em cada ocorrência de v em T, duas arestas distintas incidem em v.
• Logo, contribuem com 2 para o grau de v.
• Como todas as arestas de G, estão em T, Gr(v) é par.
• Caso 2: v = u
• Como todos os outros vértices de G tem grau par, e a quantidade de vértices com grau ímpar em um grafo qualquer não pode ser ímpar, temos que Gr(v) é par.
• Temos então que ∀  v ∈ VG, Gr(v) é par.
• Parte II (←). {"A volta": Se cada vértice de um grafo conexo G possui grau par então G é Euleriano}
• // ∀  v ∈ VG, Gr(v) é par → G é euleriano
• Provemos por Indução no número de arestas (m).
• Base: (m=0)
• G é grafo trivial, e portanto, a trilha degenerada, que começa e termina no único vértice v de G, é uma trilha euleriana. {Ela passa por todas as arestas 0 arestas de G}
• Hipóteses de Indução:
• Para todo grafo G conexo com k<m arestas, onde todos os vértices tem grau par, temos que G é euleriano. {Assumo que "a volta do teorema" vale para todos os grafos onde a quantidade de arestas é menor que um m qualquer. (Indução Forte)}
• Passo: (m>0) {Aqui eu provo que quando o teorema vale para todos os grafos com menos de m então ele vale para m}
• Como todo vértice tem grau par, temos que G não é uma árvore e portanto possui um ciclo induzido C.
• Seja H = G\{Arestas de C} {"Imaginar" G sem as arestas do ciclo C}
• O grafo H pode ser eventualmente desconexo.
• Seja H' um componente conexo de H.
• Observando que cada vértice de H' tem grau par*, [AH] < m** e H' é conexo, podemos aplicar a Hipótese de Indução, e concluir que existe uma trilha euleriana em H'. {H' satisfaz todas as 3 condições da hipótese de indução}
• Portanto, existe uma trilha euleriana em G, que pode ser encontrada aplicando-se o seguinte algoritmo:
• Inicie em algum vértice u de C.
• Caminhe em C até encontrar algum vértice v pertencente a algum componente H'
• Caminhe pela Trilha Euleriana de H' até voltar a v
• Repita 2 e 3 até encontrar o vértice inicial u.
• *Retirando as arestas do ciclo eu retiro de cada vértice duas arestas diferentes, como antes o grau do vértice era par ele continua sendo par.
• **O ciclo tem pelo menos uma aresta.

Problema do Dominó

• É possível com as pedras de um Jogo de Dominó formar um anel (Seguindo as regras do Jogo).
• Representação do Problema usando Teoria dos Grafos:
• Seja G um grafo onde:
• VG = {0,1,2,3,4,5,6} // Números que aparecem nas pedras do dominó.
• AG = {(0,0), (0,1),...,(0,6),(1,1),(1,2),...,(1,6),(2,2),...,(6,6)} // Peças do dominó
• Problema: G é Euleriano?
• Resposta: O grafo G é um grafo completo, com 7 vértices, acrescido de um laço em cada vértice, e portanto, todos os vértices de G tem grau 8 (Par). Logo, pelo teorema 1, G é Euleriano.

Grafos Hamiltonianos

Definição

• Um grafo G conexo é Hamiltoniano se existir um ciclo que inclui todo vértice de G. Tal ciclo é dito Ciclo Hamiltoniano.

• O Dodecaedro é Hamiltoniano pois existe um ciclo que passa por todos os vértices (Lembre-se que num ciclo apenas o primeiro vértice se repete).
• Outros exemplos: Grafos Ciclo, Kn, Platônicos (Cubo, Tetraedro, Octaedro, Dodecaedro, Icosaedro).
• Condições suficientes para G ser Hamiltoniano (Não se conhece ainda condições, não triviais, necessárias e suficientes, que caracterize um grafo Hamiltoniano)
• Condição de Dirac - 1952
• Seja G um grafo simples com n≥3 vértices.
• Se gr(v) ≥ n/2, ∀ v ∈ VG então G é Hamiltoniano
• Exemplos:

• {O número de vértices tem que ser maior ou igual a 3, e os graus maiores ou iguais a n/2}

Condição de Ore - 1960

• Se gr(u) + gr(v) ≥ n para todo u,v não adjacente, então G é Hamiltoniano.
• Exemplo:

• {Para cada par não adjacente a soma dos graus deve ser maior ou igual a n}
• Note que o grafo acima não satisfaz a condição de Dirac.
• Exercício: Provar que a condição de Ore engloba a condição de Dirac (A condição de Dirac é uma consequência da condição de Ore)

Condição de Bondy e Chvata - 1974
Definição Auxiliar

• O Fecho de G,F(G), é o grafo obtido acrescentando-se arestas entre pares de vértices não adjacentes cuja soma dos graus é ≥ n, até que tais pares de vértices não mais existam.

 

• n = 6
• Exceção: O Grafo abaixo não satisfaz as condições de Bondy e Chvata, Ore, Dirack, mas é um grafo hamiltoniano, porque possui um ciclo hamiltoniano.

• Considerações:
• Pela condição de Dirac, ele seria hamiltoniano se Gr(v) ≥ n/2, com n ≥ 3, o exemplo acima não satisfaz esta condição, visto que n = 6, o grau dos vértices teria de ser ≥ 3, o que não acontece no exemplo acima pois todos os vértices possuem grau 2.
• Pela condição de Ore, a soma dos graus de vértices não adjacentes deveria ser ≥ número de vértices, o que não acontece no exemplo acima, todos os pares de vértices não adjacentes possuem a soma de seus vértices não adjacentes possuem a soma de seus graus igual a 4, e o grafo possui 6 vértices, o que não respeita a condição.
• Pela condição de Bondy e Chvata o fecho do grafo teria de ser um grafo completo, o que não acontece no grafo acima.
• Embora todas estas considerações não podemos afirmar que o grafo não é hamiltoniano, porque não satisfaz nenhuma destas condições.
• O grafo é hamiltoniano, pois possui um ciclo hamiltoniano.
• Teorema: Um grafo simples é Hamiltoniano se F(G) é Hamiltoniano
• Corolário: (Condição de Bondy)
• Se F(G) é completo então G é Hamiltoniano.