Teoria de grafos

Teoria dos Grafos

A teoria dos grafos é um dos ramos da matemática discreta, assim como a lógica, a teoria dos números, a recursão entre outras. Todas se caracterizam pelo fato de não requererem ou suportarem a noção de continuidade. Especificamente, a teoria dos grafos é o estudo dos grafos, elementos matemáticos usados para modelar uma série de problemas práticos, e as relações entre eles.

História A primeira publicação sobre a teoria dos Grafos foi realizada pelo matemático Leonhard Euler, em 1736. Euler foi um importante matemático responsável também pelo sistema de notação utilizado na matemática atual e contribuiu para importantes avanços na Teoria dos Números e na Análise Numérica, entre outros campos. Após eles, outros matemáticos como Cauchy e L’Huillier continuaram o trabalho na área. Euler resolveu em 1736, o problema das Sete Pontes de Könisberg, estabelecendo assim os primeiros conceitos da Teoria dos Grafos, os conceitos de vértice.

O problema consistia em passar por todos os pontos da cidade utilizando cada ponte apenas uma vez. Euler esquematizou o problema de forma que cada caminho fosse representado por uma reta e cada intersecção por um ponto, criando assim o primeiro grafo da história. Euler ainda observou que, só seria possível atravessar o caminho inteiro passando uma única vez em cada ponte se houvesse exatamente zero ou dois pontos de onde saísse um número ímpar de caminhos. O problema das pontes de Könisberg representa um problema do tipo combinatório e sua resolução estilizada por Euler abriu as portas para o surgimento posterior da topologia.

Conceituações
Um grafo é uma estrutura formada por dois tipos de objetos: vértices e arestas. Cada aresta é um par não ordenado de vértices, ou seja, um conjunto com exatamente dois vértices.

Uma aresta é a linha única que une 2 vértices. Assim, na figura abaixo temos 6 vértices e 7 arestas:

Em ciência da computação, o grafo é uma