Grafos 4 Dummies (Cheat Sheet)

Informação mais detalhada sobre o Princípio de Pombal
Informação mais detalhada sobre Relacionamentos Estáveis
Informação mais detalhada sobre Grafos Planares
Informação mais detalhada sobre o Algoritmo de Kuratowski
Informação mais detalhada sobre Autómatos

Grafos

Informação mais detalhada sobre Grafos

Um grafo é um par g=(V,E)g = (V,E), onde:

  • VV √© um conjunto de v√©rtices finito e n√£o vazio

  • EE √© o conjunto dos dos pares de v√©rtices que est√£o ligados por uma aresta

  • Ordem do grafo, pp, √© o n√ļmero de v√©rtices do grafo.

  • Tamanho do grafo, qq, √© o n√ļmero de arestas do grafo

Seja g=(V,E)g = (V,E),

p=#Vq=#Ep = \#V\\ q = \#E

Grau de um vértice

g=(V,E)g = (V,E). Para um v√©rtice v‚ąąVv\in V, o seu grau em gg corresponde ao n√ļmero de arestas de gg que incidem em vv.

deg‚Ā°g(v)\operatorname{deg}_g(v)

Teoremas de Grafos

Teorema Fundamental da Teoria dos Grafos

Num grafo g=(V,E)g=(V,E), a soma dos graus dos seus vértices é igual ao dobro do Tamanho do grafo.

Teorema 2

Num grafo g=(V,E)g = (V,E), o n√ļmero dos seus v√©rtices √≠mpares √© par.

Teorema 3 - Lei de Euler

Seja gg um Grafo Planar, existe a seguinte relação:

Arestas+2=Veňärtices+Regioňúes\text{Arestas}+2=\text{V√©rtices}+\text{Regi√Ķes}

Teorema 4

Num grafo de pp v√©rtices e kk componentes, o n¬ļ de arestas (q)(q) √© tal que:

p‚ąík‚ȧq‚ȧ(p‚ąík+1)(p‚ąík)2p-k\leq q \leq \frac{(p-k+1)(p-k)}{2}

Teorema 5

Se um grafo de pp v√©rtices tem mais de (p‚ąí1)(p‚ąí2)2\frac{(p-1)(p-2)}{2} arestas, ent√£o √© conexo.

Defini√ß√Ķes

Grafo Regular

Um grafo diz-se regular se todos os seus vértices têm o mesmo grau.

Grafo Completo

Um grafo diz-se completo quando cada par de vértices constitui uma aresta (está tudo ligado).

  • Todo o grafo completo de kk v√©rtices √© kk-1 regular
  • (p2)=p(p‚ąí1)2\binom{p}{2} = \frac{p(p-1)}{2} √© o n√ļmero m√°ximo de arestas que um grafo pode ter
  • Kn‚ÜíK_n \rightarrow grafo completo de nn v√©rtices

Rede

Uma Rede é um grafo onde as arestas têm valores reais associados.

Multigrafo

√Č uma rede com arestas com apenas n√ļmeros naturais.

Aberto e Fechado

Um atalho, caminho, trajet√≥ria √© fechado se o primeiro e o √ļltimo v√©rtice coincidirem. Se n√£o coincidirem √© aberto.

Caminho

Caminho é uma seguimento alternado de vértices e arestas.

Atalho

Caminho que n√£o repete arestas.

Trajetória

Caminho que não repete vértices.

Ciclo

Atalho (caminho que não repete vértices) fechado com pelo menos 3 arestas.

Vértice Conectados

2 vértices em que existe um caminho entre eles.
Também se considera se os vértices forem iguais.

Grafo Conexo

√Č conexo se quaisquer dois v√©rtices do grafo estiverem conectados.

Ponte

Aresta de um grafo, que, se for removida, aumenta o n√ļmero de componentes.

Componente

hh é uma componente de um grafo gg, se hh for um grafo conexo de gg e não for subgrafo de nenhum outro subgrafo conexo de gg.

Grafo Planar

Grafo que é possível desenhar sem cruzar arestas.

Grafos Eulerianos

Informação mais detalhada sobre Grafos Eulerianos

Defini√ß√Ķes

Atalho Euleriano

Percorre todos os vértices e arestas sem repetir arestas.

Multigrafo Euleriano

Tem um circuito euleriano (atalho euleriano fechado).

Multigrafo Atravess√°vel

Tem uma travessia euleriana (atalho euleriano aberto).

Teoremas Eulerianos

Teorema 1 - Teorema de Euler-Hierholzer

Um multigrafo é euleriano se e só se é conexo e todo o seu vértice é par.

Teorema 2

Um multigrafo é atravessável se e só se tem apenas dois vértices ímpares.
Para al√©m disso, o atalho Euleriano aberto come√ßa e acaba nos v√©rtices √≠mpares, onde o primeiro √© diferente do √ļltimo.

Teorema 3 - Teorema de Euler

Se tivermos um grafo que não seja Euleriano, podemos duplicar cada aresta e dessa maneira todos os vértices terão grau par, assim já é Euleriano.
NOTA: Outra solução é percorrer cada aresta duas vezes, em vez de duplicar.

Teorema 4 - Teorema de Lucas

Um multigrafo G\mathcal G conexo com 2n2n vértices ímpares pode ser descrito por exatamente nn atalhos abertos que não partilham arestas.

Teorema 5 - Teorema de Tarry

Iniciando um caminho num grafo conexo qualquer, e seguindo as regras do Algoritmo de Tarry, regressaremos ao vértice inicial, depois de ter percorrido cada aresta do grafo 22 vezes em sentidos opostos.

Algoritmos

Algoritmo de Fleury

Com este Algoritmo consegue-se percorrer um atalho euleriano fechado num multigrafo euleriano.

  1. Começa-se num vértice qualquer
  2. Se houver mais que 11 aresta possível a percorrer, escolhe-se uma que não seja ponte
    (n√£o interessa qual, desde que n√£o seja uma ponte)
  3. S√≥ se atravessam as pontes em √ļltimo caso (quando j√° n√£o h√° mais arestas dispon√≠veis).

Algoritmo Fleury - Multigrafo Atravess√°vel

O Algoritmo de Fleury foi concebido para multigrafos eulerianos.
Mas, também o podemos aplicar, informalmente, em multigrafos atravessáveis.

Para isso, basta come√ßar num v√©rtice √≠mpar, √© a √ļnica mudan√ßa no Algoritmo.
Mas, neste caso, não vamos acabar no mesmo vértice, mas sim no outro vértice ímpar.
Reparem que, se, num multigrafo atravessável, ligarmos os dois vértices ímpares com uma aresta, ficamos com um multigrafo euleriano.
Nesse caso, já poderíamos acabar no vértice inicial.

Desvantagens

Não funciona em Labirintos se não os conhecermos, uma vez que nesses caso não sabemos se uma aresta (caminho do Labirinto) é ponte ou não.

Algoritmo de Trémaux

Com as regras deste Algoritmo, qualquer um pode sair de qualquer labirinto.

Passamos agora à descrição do Algoritmo:

  1. Sempre que chegamos a um vértice não visitado anteriormente, seguimos por uma aresta também não percorrida, qualquer.

  2. Sempre que chegarmos a um vértice através de uma aresta ainda não percorrida anteriormente, se chegarmos a um vértice já visitado ou a um beco sem saída, voltamos para o vértice de onde viemos pela aresta.

  3. Sempre que chegarmos a um vértice através de uma aresta que já tinha sido percorrida anteriormente e chegarmos a um vértice já visitado, escolhemos a aresta ainda não percorrida que incide no vértice. Se não existir, escolhemos percorrer uma aresta que já tenha sido percorrida apenas uma vez.

Algoritmo de Tarry

Se chegarmos a um vértice, escolhemos continuar por qualquer aresta que não tenha sido percorrida 22 vezes, com exceção da aresta onde chegamos pela primeira vez ao vértice atual.

S√≥ percorremos essa aresta em √ļltimo caso, ou seja,
se for um beco sem saída, ou se as outras arestas já tiverem sido percorridas 22 vezes.

√Ārvores

Informa√ß√£o mais detalhada sobre √Ārvores

√Ārvore

Grafo conexo que n√£o tem ciclos.

Teoremas de √Ārvores

Teorema 1

Se TT é uma árvore de ordem pp e tamanho qq, então

q=p‚ąí1q = p-1

Teorema 2

Um grafo gg de ordem pp √© uma √°rvore, se e s√≥ se √© conexo e tem tamanho q=p‚ąí1q=p-1.

Defini√ß√Ķes

√Ārvore de cobertura

Seja gg um grafo, TT √© a sua √Ārvore de Cobertura se:

  • √Č uma √°rvore
  • √Č um subgrafo de gg que cont√©m todos os v√©rtices

Custo de √°rvore

Dada uma rede (V,E,c)(V,E,c), o custo de uma árvore de cobertura TT da rede é
o somatório de todos os valores das arestas de TT.

√Ārvore de cobertura m√≠nima

√Ārvore de cobertura de uma rede RR, cujo custo √© menor ou igual ao
custo de qualquer outra √Ārvore de cobertura de RR.

√Ārvore Econ√≥mica

√Ārvore de cobertura constru√≠da atrav√©s do Algoritmo de Kruskal.

Algoritmos

Algoritmo de Kruskal

O resultado final √© uma √Ārvore Econ√≥mica, que tamb√©m ser√° uma √Ārvore de Custo m√≠nimo.

Tamb√©m se pode usar o Algoritmos de Kruskal para encontrar uma √°rvore de cobertura m√°xima, basta ir assinalando as arestas pela ordem inversa (1¬ļ as que t√™m valor m√°ximo).

Exemplo 1
Exemplo 2

Algoritmo de Dijkstra

O resultado final ser√° uma √Ārvore de Cobertura, onde para cada viv_i, F‚Ā°(i)\operatorname{F}(i) √© o custo m√≠nimo poss√≠vel.

Exemplo 1
Exemplo 2
Exemplo 3

Fluxos

Informação mais detalhada sobre Fluxos

Defini√ß√Ķes

Fonte

Uma fonte num digrafo conexo GG é um vértice com grau de entrada nulo.

Sumidoro

Um subidouro num digrafo conexo G é um vértice com grau de saída nulo

Digrafo

Grafo dirigido, todas as arestas têm orientação.
Um digrafo-ss-tt é um digrafo com fonte ss e semidouro tt

ponteeuclidiana