Grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (902 palavras )
  • Download(s) : 0
  • Publicado : 16 de abril de 2012
Ler documento completo
Amostra do texto
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 KAUFMANNGRAFOS






















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

Este trabalho tem por finalidade introduzir o conceito e teoria dos Grafos, trazendo ostipos 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 deobjetos 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 elementoschamados 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 arepresentaçã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 doplano 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 arestade 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...
tracking img