Grafos

Teoria dos Grafos

O que é um grafo?
Um grafo é uma que representação abstrata de um conjunto de objetos e das relações existentes entre eles. É definido por um conjunto de nós ou vértices, e pelas ligações ou arestas, que ligam pares de nós. Uma grande variedade de estruturas do mundo real podem ser representadas abstratamente através de grafos.

A figura seguinte ilustra um grafo com 5 nós.

Surgimento dos Grafos
A Teoria dos Grafos surgiu em 1736, na cidade de Konigsberg pelo matemático
Leonhard Euler. A cidade era cortada pelo rio Pregel, que possuia duas ilhas e para facilitar o transporte entre elas foram construídas sete pontes.

Com o tempo, as pessoas começaram a se perguntar se era possível sair de suas casas, passar por cada ponte exatamente uma vez e voltar para suas residências. Para solucionar essa questão,
Euler criou um diagrama da cidade.

A cada ilha e margem ele associou a um ponto que chamaremos de vértice e a cada ponte uma ligação que chamaremos de aresta. Esse conjunto formado por vértice e aresta denominamos Grafo. Euler percebeu então que para ser possível realizar o circuito sem repeticões, cada vértice deveria ter um número par de arestas, mostrando ser impossível fazer o percurso sugerido pelos moradores. Para que serve os grafos?
Grafos são um conjunto de vértices e arestas, ou seja, servem como modelo matemático para representar o mundo real. São usados para modelar redes e relacionamentos. O estudo sobre sua teoria é importante, pois qualquer relação binária pode ser representada num grafo. Existem diversas aplicações como a logística de transporte, fluxo de um jogo, conexões de comunicação, linhas de metrô, árvore genealógica, dados sociológicos, investigação operacional, química dentre outras.

EXEMPLO:
 Rede de computadores: sendo cada terminal representado por um vértice, o cabo de rede pelas arestas e o custo associado a latência ou o número de maquinas que a