Grafos e kruskal

UNIVERSIDADE ESTADUAL DO NORTE DO PARANÁ UENP – CAMPUS LUIZ MENEGHEL CURSO SISTEMAS DE INFORMAÇÃO

CAIO VINICIUS BENEDITO – 797
MARIO SHIGUEO ISHIKAWA – 811
ROBSON ALVES NOGUEIRA – 789

GRAFOS – CAMINOS MINIMOS ALGORITMO DE KRUSKAL

BANDEIRANTES-PR
NOVEMBRO / 2012 1. GRAFOS

1.1 Definição
Em matemática e ciência da computação, grafo é o objeto básico de estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas".
Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais econômico. Outro exemplo é o caso das redes de computadores, sendo cada terminal representado por um vértice, o cabo de rede pelas arestas e o custo associado à latência, por exemplo, ou o número de máquinas que a comunicação atravessa entre os nós. É nestes princípios que assenta todo o protocolo IP que torna possível a Internet ser uma realidade.

Figura: Um grafo com 6 vértices e 7 arestas.

1.2 Spanning Tree
Uma árvore é um grafo conexo e acíclico (não possui ciclos). Toda arvore é um grafo, todo grafo conexo possui pelo menos uma árvore de extensão associada, composta de todos os seus vértices e algumas de suas arestas.
Suponha-se que G é um grafo, então G é uma árvore se satisfazer as seguintes condições: * G é conexo e apenas um caminho entre dois vértices quaisquer. * G é acíclico, e simples ciclo é formado se qualquer aresta for adicionada a G. * G é conexo, e deixará de ser conexo se qualquer aresta for removida de G. * G é conexo, acíclico e tem n – 1 arestas.

Figura: Árvore
Um grafo G, conexo, admite varias Árvores, uma árvore com