Grafos

Resumo Neste trabalho iremos falar sobre a aplicação da álgebra linear, mas especificamente a utilização de matrizes e suas propriedades a fim de formular problemas e simplificar suas resoluções além de poder implementar computacionalmente em casos de maior complexidade. Com essa ferramenta podemos atuar em áreas como análise de estruturas organizacionais, estatísticas, ciências físicas dentre outras.
Introdução
A teoria de grafos, área recente da matemática é utilizada para formulações de modelos em problemas de áreas como ciências sociais, negócios, ciências físicas entre outras e tem aplicações como comunicação, estudo de estruturas organizacionais e sociais. Uma maneira de traduzir os grafos é utilizando matrizes e suas propriedades para obter resultados úteis na resolução e análise de problemas nas áreas citadas. O primeiro problema envolvendo grafos foi “As pontes de Königsberg”, que foi resolvido por Leonhard Euler em 1735. O problema envolvia o rio Pregelarme que cortava Königsberg que ficava na Prússia e dividia a região em quatro “ilhas” e existiam 7 pontes.O problema era saber se existia uma forma de passar por todas as pontes atravessando-as apenas uma vez.

Euler simplificou o problema em um simples conjunto de quatro pontos (vértices) e sete caminhos (arestas).

Outras utilizações
1852 - “O Problema das 4-Cores” (Francis Guthris / De Morgan) O teorema das quatro cores pode ser resolvido graças a implementação computacional de grafos.

1856 -“O Problema dos Ciclo Hamiltoniano” (William R. Hamilton)

É possível um cavalo fazer uma rota pelo tabuleiro de xadrez, isto é, visitar cada quadrado exatamente uma vez e retornar para o seu quadrado inicial?

Século XX - Grande interesse pela Teoria dos Grafos
1930 - Resultados teóricos fundamentais (Kuratiwski, König, Minger)
1971 - PROBLEMA DE STEINER EM GRAFOS (Hakimi et. al.) Daí por diante utilizamos grafos para reolusão de uma infinidade de problemas matemáticos,