Teoria dos Grafos

Estudo de Grafos e Aplicações

A teoria de grafos surgiu no século XVIII, um dos primeiros cientistas a trabalharem com nesta linha foram, L. Euler, G. Kirchhoff e A. Cayley, essa teoria é aplicada principalmente na área da matemática, principalmente na modelagem da matemática, que permite interpretar e analisar várias situações em diversas áreas como Física, Química, Biologia, Teoria da Computação, entre outras.
Com o desenvolvimento da ciências da computação a teoria de grafos tem contribuído de forma muito positiva a resolução de problemas e simulações reais.
Um gafo é um conjunto de pontos no plano ligado por seguimentos de reta ou flecha. Para desenhar um grafo, representa-se cada nó por um círculo e os arcos por linha ligando estes círculos. Um arco é incidente nos nó aos quais associados. No isolado é aquele que não está ligado a nenhum outro. Arcos adjacentes são dois arcos incidentes num mesmo nó. Multigrafos são grafos nos quais são permitidos dois ou mais arcos associados ao mesmo par de nó, pode-se representar multigrafos por meio de matrizes. Grau de um nó é o número de arcos incidentes nele. Um circuito de Euler do grafo G é um circuito que contém todos os nós e todas as arestas de G, um dos resultados estabelecidos por Euler diz que um multigrafo conexo é eureliano se, somente se, cada nó tiver grau par. O conceito de planaridade de um grafo está ligado ao traçado de mapas de cidades, em um mapa de uma cidade podemos considerar que cada esquina é um nó e o trecho entre duas esquinas é o arco, apenas isso não é o bastante, tendo em vista nem todas ruas serem de mão-dupla, por este motivo surge o conceito de arco direcionado e dígrafo. Seguindo a teoria de grafos, da mesma forma, a definição de dígrafos não prevê a existência de laços e arcos repetidos, ou seja, dois arcos associados ao mesmo par ordenado de nós, a direção do arco é indicado por meio de uma setano nó para o qual o arco é incidente. Quando um multigrafo é de grau ímpar não é