Teoria de Teoria de GrafosGrafos

Tudo começou no século XVIII, Tudo começou no século XVIII, na cidade medieval de na cidade medieval de Königsberg, situada no leste Königsberg, situada no leste europeu.europeu.

Königsberg é banhada pelo rio Königsberg é banhada pelo rio Pregel, que a divide em quatro Pregel, que a divide em quatro áreas de terra ligadas umas às áreas de terra ligadas umas às outras por sete pontes, as outras por sete pontes, as famosas “sete pontes de famosas “sete pontes de Königsberg”.Königsberg”.

Um pouco da história de Um pouco da história de Teoria de GrafosTeoria de Grafos

Durante muito tempo, os habitantes daquela Durante muito tempo, os habitantes daquela cidade perguntavam-se se era possível cidade perguntavam-se se era possível cruzar as sete pontes numa caminhada cruzar as sete pontes numa caminhada contínua, sem que se passasse duas vezes contínua, sem que se passasse duas vezes por qualquer uma delas.por qualquer uma delas.

Leonhard Euler estudou este problema Leonhard Euler estudou este problema em 1736 (como veremos, mais adiante) e a em 1736 (como veremos, mais adiante) e a partir daí, desenvolveu toda a teoria que é partir daí, desenvolveu toda a teoria que é hoje utilizada nas mais diversas áreas que hoje utilizada nas mais diversas áreas que envolvem tarefas: a Teoria de Grafosenvolvem tarefas: a Teoria de Grafos..

Conceitos básicosConceitos básicosUm Um grafo G(V,A)grafo G(V,A) é definido pelo par de conjuntos não é definido pelo par de conjuntos não vazios V e A, onde:vazios V e A, onde:V- conjunto dos V- conjunto dos vérticesvértices do grafo; do grafo;A- conjunto de pares ordenados a= (v,w), v e w A- conjunto de pares ordenados a= (v,w), v e w V: as V: as arestasarestas do grafo. do grafo.

Vértices adjacentes: são aqueles que estão ligados por : são aqueles que estão ligados por uma mesma aresta. uma mesma aresta.

Aresta incidenteAresta incidente: é aquela que liga dois vértices : é aquela que liga dois vértices distintos.distintos.

Grau de um vérticeGrau de um vértice é igual ao número de arestas nele é igual ao número de arestas nele incidentes.incidentes.

Grafo RegularGrafo Regular é aquele em que todos os vértices têm o mesmo é aquele em que todos os vértices têm o mesmo grau.grau.

Grafo CompletoGrafo Completo é aquele em que todos os vértices são é aquele em que todos os vértices são adjacentes.adjacentes.

Um grafo G diz-se um Um grafo G diz-se um Grafo BipartidoGrafo Bipartido se o conjunto dos seus se o conjunto dos seus vértices admitir uma partição {Vvértices admitir uma partição {V11, V, V22 } de tal forma, que toda } de tal forma, que toda a aresta de G une um vértice de Va aresta de G une um vértice de V11 e um vértice de V e um vértice de V22..

Um Um grafo planargrafo planar é um grafo que pode ser desenhado no plano é um grafo que pode ser desenhado no plano de forma a que as arestas não se cruzem.de forma a que as arestas não se cruzem.

CaminhoCaminho é uma sucessão de vértices e arestas tal é uma sucessão de vértices e arestas tal que cada aresta liga o vértice que a precede ao que cada aresta liga o vértice que a precede ao vértice que a segue, não repetindo arestas.vértice que a segue, não repetindo arestas.

PasseioPasseio é um caminho onde pode haver repetição de é um caminho onde pode haver repetição de arestas e de vértices.arestas e de vértices.

Ciclo ou circuito Ciclo ou circuito é um caminho fechado.é um caminho fechado.

Grafo conexoGrafo conexo é aquele onde entre qualquer par de é aquele onde entre qualquer par de vértices existe sempre um caminho que os une.vértices existe sempre um caminho que os une.