Teoria Dos Grafos

Teoria dos Grafos

Da onde surgiram os grafos? O que são?

Historia

A Literatura afirma que a teoria dos grafos começou na cidade de Konigsberg em 1736 pelo grande matemático suíço Leonhard Euler (1707-1783). A cidade era cortada pelo rio Pregel, que possuía duas ilhas.

Como era muito complicado fazer o transporte de cargas e pessoas através de barcos, algumas.

Pontes foram construídas para auxiliar neste deslocamento entre as ilhas e as duas margens. Após algum tempo as pessoas começaram a se perguntar se era possível sair de sua casa, passar por cada ponte exatamente uma vez e voltar para a segurança de seu lar.

Para resolver o problema, Euler montou um diagrama que representasse o mapa da cidade. Ele o fez da seguinte maneira: 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.

Essa figura com vários pontos (vértices) e algumas ligações (arestas) que denominamos um grafo. Para finalizar seu raciocínio, Euler percebeu que existiam vértices com exatamente três arestas incidentes. Por outro lado, como os moradores queriam atravessar cada ponte apenas uma vez, cada vértice deveria ter.

Conceitos básicos da teoria de grafos.

Grafo- Grafo é definido pelo par de conjuntos V e A, aonde:

V- Conjunto não vazio: os vértices ou “nodos”.

A- Conjunto de pares ordenados a= (V, W) V e W ∈ V= as aresta do Grafo.

Como em toda teoria matemática, a teoria dos grafos esta repleta de nomenclaturas e termos técnicos. Nesta seção podem-se aprender algumas definições muito importantes para o entendimento completo deste modelo.

Grafo que representa um mapa de estradas e cidades:

A=1 D=4

B=2 E=5

C=3 F=6

Aproveitando o gráfico acima para poder abordar algumas definições. Por exemplo, o grafo acima e conexo, pois e possível ir de um vértice a qualquer outro passando e usando algumas de suas arestas.

Exemplo.

Para ir de A até F basta fazer a seguinte sequencia A → C → E → F.

Dizemos então, que esta sequencia é um caminho de A até F. Agora, um caminho fechado é chamado de ciclo; Por exemplo, o caminho A → B → E → A é um ciclo de tamanho 3 (ou seja, um C3). Já o ciclo B → E → G → F → B é um C4.

Uma aresta conecta dois vértices; esses dois vértices são ditos como incidentes à aresta. A valência (ou grau) de um vértice é o número de arestas incidentes a ele, com loops contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1. Se E é finito, então a valência total dos vértices é o dobro do número de arestas. Em um dígrafo, distingue-se o grau de saída (o número de arestas saindo de um vértice) e o grau de entrada (o número de arestas entrando em um vértice). O grau de um vértice é igual à soma dos graus de saída e de entrada.

Grafo orientado.

Quando a família de arestas é formada por pares ordenados dizemos que o grafo é orientado ou direcionado.

Nesse caso, ao desenhar o grafo, devemos