Grafos

Trabalho Algoritmos sobre grafos 1 Ciência da Computação

Algoritmo de Warshall

Elton Januario de Sousa – CA 21405238 – [e-mail] Fernando Oliveira Mendes - CA 21362059 - [e-mail] Lucas de Medeiros Ferrero - CA 21360512 - [e-mail] Marcelo Gomes Feitosa - CA 21410060 - [e-mail] Sérgio Kiyoshi Miyagi - CA 21323131 - [e-mail]

São Paulo, 24 de maio de 2013

Introdução Grafos é uma representação de um conjunto de pontos ligados por arestas (setas). Muito utilizado nos dias de hoje, é possível representar um mapa de estrada através dos grafos e usar o algoritmo para determinar o caminho mais curto entre dois pontos. Outro exemplo é o caso das redes de computadores, sendo cada terminal representado por um vértice através de um cabo de rede. Grafos têm sido utilizados para representar várias formas de redes complexas, onde o número de nós e suas conexões são muito altos.

Grafos Direcionados e Relações Binárias Em um grafo direcionado, dois arcos do nó a para o nó b seriam paralelos, mas um arco do nó a para b e outro do nó b para a não são paralelos. Considere a matriz de adjacência do grafo, essa é uma matriz N x N, não necessariamente simétrica. Por não ter arcos paralelos, a matriz de adjacência será uma matriz booleana, onde todos os elementos são iguais 0 ou a 1. Matriz Booleana

Matriz Simétrica

Exemplo: Suponha que G é um grafo direcionando com N nós e sem arcos paralelos. Seja N o conjunto de nós. Se (Ni, Nj) é um par ordenado de nós,

então, ou existe ou não existe um arco de N i para Nj. Podemos usar essa propriedade para definir uma relação binária no conjunto N.

Para o grafo abaixo, a relação de adjacência é {(1,2), (1,3), (3,3), (4,1), (4,2), (4,3)}.

Para o conjunto N= {1, 2, 3, 4} e a relação binária {(1,4), (2,3), (2,4), (4,1)} em N, obtemos o grafo direcionado associado.

Grafo Simétrico e Anti Simétrico

Simétrico: Qualquer par de vértices ligado pode ser