Teoria de grafos

TERORIA DE GRAFOS

1. INTRODUÇÃO Na teoria de Grafos, como visto temos várias aplicações facilitando a resolução de alguns problemas.
Estaremos nesse artigo explanando sobre algumas das propriedades de Árvores, e na aplicação dos algoritmos Prim e Kruskal.

2. CONCEITO DE ÁRVORES Na teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos). Caso o grafo seja acíclico mas não conexo, ele é dito uma floresta. Uma floresta também é definida como uma união disjunta de árvores.
Toda árvore é um grafo, mas nem todo grafo é uma árvore.
2.1. ÁRVORE GERADORA

Podemos dizer que uma árvore denominada árvore geradora de um grafo conexo G se T é um sub-grafo de G e contém todos os vértices de G.
Figura 1
Na figura 1, o sub-grafo indicado em linhas grossas é uma árvore geradora do grafo representado

Para um grafo desconexo, não podemos identificar nenhuma árvore geradora, mas podemos identificar no mínimo uma floresta de árvores geradoras, uma para cada componente do grafo. Segundo seu algoritmo, se G não contém nenhum circuito ele já é a sua própria árvore geradora. Suponhamos agora que ele contém um circuito. Tirando uma aresta desse circuito resulta em um grafo ainda conexo. Continuando assim até que não tenha nenhum circuito, o grafo obtido é um grafo conexo que é uma árvore. Portanto obtemos o seguinte teorema: “Todo grafo conexo contém no mínimo uma árvore geradora.”
Seja G = (V,E) um grafo conexo e T = (V,F) uma árvore geradora de G. Uma aresta que pertence a E e não a F é chamada um elo de T. Seja n o número de vértices em G, m o número de arestas em E . O número total de elos em G é igual a m - n + 1. Note que um elo é definido em relação a uma árvore geradora específica de G.
Seja T uma árvore geradora de G. Se chamamos T' o complemento de T em G (isto é, todos os elos), podemos escrever G = T U T.

2.1. ÁRVORE GERADORA MÍNIMA
Podemos definir como árvore geradora