Teoria dos Grafos

·         Bibliografia

o   Fundamentos Matemáticos para a Ciência da Computação – Judith L. Gershng – 5ed – LTC –Capitulos 5 e 6

o   Introdução à Teoria dos Grafos – Marcia Aguiar Robuske – Ed da UFSC

o   Grafos e Algoritmos Computacionais – 2 edição – Ed Campus – Jayme Luiz Swarcfiter

 

·         Critérios de Avaliação

o   Avaliação Teórica

o   Avaliação Prática

§  Implementação de algoritmos

§  Entrega do Trabalho Escrito (latex)

§  Entrega da apresentação

§  Apresentação do trabalho (grupo)

·         Motivação

o   Problema da Ponte de Konigsber (1736)

§  No Rio Pregel, junto à cidade de Konigsberg (atual Leningrado) na então Prussia, existem duas ilhas formando quatro regiões distintas formando portanto quatro regiões distinguiveis de terra A,B,C e D.

§  O problema consiste em, partindo de uma dessas regiões, determinar um trajeto pelas pontes segundo o qual se possa retornar à região de partida, após atravessar cada ponte somente uma vez.

o   Século XIX

§  Problema das 4 cores

§  Problema do ciclo Hamiltoniano

§  Teoria das Árvores

o   Surgimento do computador aumentou o panorama de estudos

·         Definição do Grafo

o   Informal – um grafo é um conjunto não-vazio de nós (vértices) eum conjunto de arcos(arestas) taisque cada arco conecta dois nós.

o   Formal – um grafo é uma tripla ordenada (N,A,g) onde:

§  N = conjunto não-vazio de nós (vértices)

§  A = conjunto de arcos (aretas)

§  g = função que associa a cada arco a um par não-ordenado x-y de nós, chamada de extremidade de a.

·         Representação Gráfica

o   Forma visual – ex: rotas áreas

o   g(a1) =1-2

o   g(a2)= 1-2

o   g(a3)=2-2

o   g(a4)=2-3

o   g(a5) =1-3

o   g(a6)=3-4

 

·         Exercicio

o   Esboce um grafo com nós {1,2,3,4,5}, arcos (a1,a2,a3,a4,a5,a6) e função g dada por g(a1) = 1-2, g(a2)=1-3, g(a3)=3-4, g(a4)=4-5 e g(a5)=5-5.

·         Definição de Grafo Direcionado (“Digrafo”)

o   É uma tripla ordenada (N,A,g) onde

§  N = conjunto não vazio de nós

§  A = conjunto de arcos

§  g = função que associa a cada arco um par ordenado (x,y) de nós, onde x é o ponto inicial e Y é o ponto final.

o   Em um grafo direcionado, cada arco tem sentido ou orientação.

§  Obs: São também conhecidos por grafo rotulado ou grafo com peso.

·         Exercicio

o   Apresentar um grafo contendo a nterligação das cidade no norte do estado de SC, as distâncias devem ser apresentadas no grafo.