Grafos

UNIJUI – UNIVERSIDADE REGIONAL DO NOROESTE DO ESTADO DO RIO GRANDE DO SUL

DETEC - DEPARTAMENTO DE TECNOLOGIA

CURSO CIÊNCIA DA COMPUTAÇÃO
ESTRUTURA DE DADOS I

KASSIANO KAUFMANN

GRAFOS

IJUÍ - RS
1º SEM. 2011
Introdução

Este trabalho tem por finalidade introduzir o conceito e teoria dos Grafos, trazendo os tipos diferentes de grafos e exemplos de sua utilização voltados para a área da Ciência da Computação.

Definição

Grafo é um tipo abstrato de estrutura de dados onde dado um numero de objetos há um conjunto de conexões entre pares destes objetos. Um grafo G é um par ordenado G = (V, E) que está sujeito as seguintes condições: • V é um conjunto não-vazio de elementos chamados de vértices ou nodos. Vértice é a unidade fundamental da composição de um grafo sendo este indivisível.Como exemplo temos o conjunto V, onde, V = {v0, v1, v2, v3, v4,v5} e v0..vn são vértices. • E é um conjunto de arestas que por sua vez são pares de vértices distintos e não ordenados. Como exemplo temos o conjunto E, onde, E = {e0, e1, e2, e3, e4} e e0..en são arestas. Cada aresta de E é um par não ordenado e distinto de vértices sendo: e0 = (v0, v2) , e1 = (v0, v3) , e2 = (v1,v2) , e3 = (v2, v3) , e4 = (v3,v4) .

Representação Gráfica

A figura 1.0 traz a representação gráfica do grafo G acima, onde, G = ( {v0, v1, v2, v3, v4, v5} , { (v0, v3) , (v0, v2) , (v0, v3) , (v1, v2) ,(v2, v3) , (v3, v4) } ) .
Os seus vértices cor respondem a pontos distintos do plano em posição aleatória e suas arestas cor respondem a retas ou curvas que unem estes pontos.

Figura 1.0

Arestas incidentes e adjacentes

Cada aresta de um grafo é denotada por e = (v, w) e é composta pelo par de vértices que a forma. Neste caso, os vértices v e w são os extremos da aresta e. Uma aresta se diz incidente em um vértice v se v Ø um de