Teoria de grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (786 palavras )
  • Download(s) : 0
  • Publicado : 22 de setembro de 2011
Ler documento completo
Amostra do texto
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 daspropriedades 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 nemtodo 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
Nafigura 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 nomí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 eleconté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. Portantoobtemos 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 é chamadaum 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 deG.
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...
tracking img