TEORIA DE GRÁFICOS E APLICAÇÕES

UNIVERSIDADE PAULISTA

UNIP

TEORIA DOS GRAFOS E APLICAÇÕES

SANTANA DE PARNAÍBA

2014

• PROPOSTA DO TRABALHO:

Pesquisa sobre o conceito de grafos e fazer um programa para ser apresentado.

Alunos: RA:

Allan Aparecido de M Sabino B555hb-9

Rodrigo Cruz dos Santos B36599-4 Genisson Silva B511931

Igor Boas B507764

Thomaz Gomez B38HEH

Índice

TEORIA DOS GRAFOS E APLICAÇÕES Pagina 4

1. INTRODUÇÃO Pagina 5

2. HISTÓRIA Pagina 6

3.Conceitos Pagina 8

4.Planaridade e Coloração Pagina 10

5.Aplicação Pagina 12

6.Conclusão Pagina 22

TEORIA DOS GRAFOS E APLICAÇÕES

Resumo - A teoria dos grafos é um ramo da Matemática que vem crescendo ao longo dos anos. Inicialmente surgiu como um desafio, no problema conhecido como “as pontes de Konigsberg”, mas com a invenção dos computadores foi ganhando espaço e atualmente é considerada uma ferramenta eficiente para resolver problemas em diferentes áreas como na Matemática, nas Engenharias, na Indústria e no Comércio. Dentre as classes de problemas abordados por esta teoria, pode-se destacar a utilização ao do modelo conhecido como o “problema de coloração”, que busca colorir os vértices de um grafo, de modo que vértices adjacentes apresentem cores distintas, utilizando para isto o menor número possível de cores. Através do problema de coloração, consegue-se modelar um grande número de situações práticas, pois ele consiste em particionar os vértices de um grafo em conjuntos, onde seus elementos apresentam características comuns, que podem ser a cor, a numeração, ou outras.

1. INTRODUÇÃO

A teoria dos grafos é um ramo da Matemática Discreta (estuda estruturas matemáticas que não necessitam da noção de continuidade) que estuda objetos denominados grafos. Conforme informações retiradas de Boaventura Netto (2006, p.02), o pioneiro desta teoria foi o matemático suíço Leonhard Euler que formulou e resolveu o problema das pontes de Konigsberg, o qual inicialmente se apresentou como uma charada matemática. Além de Euler, Gustav Robert Kirchhoff, Arthur Cayley e William Rowan Hamilton foram alguns dos nomes que utilizaram conceitos de grafos para res ao de problemas e acabaram por contribuir para o desenvolvimento teórico e prático acerca da teoria dos grafos. Um grafo G = G(V, E) pode ser definido como uma estrutura onde V e um conjunto discreto e ordenado de pontos chamados vértices, e E um conjunto de linhas chamadas arestas, e cada aresta esta conectada em pelo menos um vértice.

Com a ideia de pontos interligados por linhas, a representação por grafos pode facilitar o entendimento e a resolução¸ ao de problemas. Desta forma, mapas que representam a estrutura organizacional de uma empresa, rotas de transporte, redes de comunicação, distribuição de produtos, assim como a estrutura química de moléculas, podem ser expressos através de grafos. De modo geral, o estudo sobre grafos vem crescendo nas ultimas décadas, devido ao avanço de novas tecnologias computacionais, que permitem a resolução de problemas via algoritmos, com maior eficiência, rapidez e confiança. Assim, a crescente aplicabilidade desta teoria é um fator positivo para o desenvolvimento social, e um dos modelos práticos que merece destaque e o problema conhecido como coloração, o qual pode ser utilizado em situações que exigem a seleção de elementos em conjuntos independentes e com características comuns.

2. HISTÓRIA

A teoria dos grafos teve seu surgimento no ano de 1736, quando Leonhard Euler se depara com o problema das pontes de Konigsberg. Konigsberg era uma cidade da antiga Prússia do século XVIII, atual Kaliningrado (Rússia), onde havia duas ilhas que, juntas com a parte continental eram ligadas por sete (7) pontes. Na cidade, discutia-se a possibilidade de atravessar todas as pontes, sem repeti-las. No entanto Euler, em 1736, mostrou a solução para esta problemática, usando para isto, um raciocínio simples: transformou os caminhos das pontes em retas e suas interseções em pontos, criando possivelmente o primeiro grafo da história. A partir de então Euler percebeu que só seria possível atravessar o caminho inteiro passando uma única vez em cada ponte se houvesse no máximo dois pontos de onde saía um número ímpar de caminhos. A razão de tal ideia estava baseada no fato de que em cada ponto deveria haver um número par de caminhos, os quais representariam a chegada e a saída. Os dois pontos com caminhos ímpares, seriam referentes ao início e ao final do percurso, pois estes não precisariam de um caminho para chegar e um caminho para sair, respectivamente.

A resolução do problema das pontes, por Euler, acabou sendo visto pela comunidade científica na época sem maior importância, simplesmente como uma charada matemática. Por isso esta