TEORIA DOS GRAFOS

                                                                                                                                      

INSTITUTO FEDERAL, EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO PARÁ-IFPA  CAMPUS SANTARÉM
            LICENCIATURA PLENA EM INFORMÁTICA – PARFOR
MATEMÁTICA PARA COMPUTAÇÃO
PROFESSOR: FRANCISCO ROBSON ALVES

Teoria dos Grafos

Equipe: 07

Adriana Christina Macêdo da Silva, Lindalva da Silva Ferreira, Maria Silvana Ferreira Chaves, Raimunda Cristiane Lira da Silva

Como Surgiu a Teoria dos Grafos?

A teoria dos Grafos surgiu com os trabalhos de L. Euler, G. Kirchhoff e A. Cayley.

¬ Esta teoria tem sido utilizada largamente em diferentes áreas da biologia, química e na matemática aplicada.

¬ O problema das pontes de Königsberg é o primeiro e mais famoso problema em teoria dos grafos resolvido por Euler em 1736.

O problema consiste em determinar se é possível ou não fazer um passeio pela cidade começando e terminando no mesmo lugar, cruzando cada ponte exatamente uma única vez.

1736: Euler foi o primeiro a representar esse problema usando grafos depois desta época pouca coisa foi investigada em teoria dos grafos por quase um século.

• O interesse ressurgiu na década de 20 com os estudos de D. Konig que se transformaram em um livro, publicado em 1936.

O que é um grafo?

“Um grafo é um conjunto de pontos, chamados vértices, conectados por linhas, chamadas de arestas”

Formação dos Grafos

• Os grafos são formados por:

– Vértices - conjunto V;

– Arestas – conjunto A;

• Formalmente descrito como:

– G=(V,A)

Grafo Direcionado ou Dígrafos

     Um dígrafo (= um grafo direcionado) consiste em dois conjuntos: um conjunto vértices e outro de arcos. Cada arco é um par ordenado de vértices. O primeiro vértice é o início e o segundo é o fim do arco.
     Um arco com início em v e final em w será denotado por v-w (isto não é uma subtração). Existir um arco que liga o vértice v ao vértice w não significa que existe um arco que liga o vértice w ao vértice v.

     Se v-w existe então dizemos que w é vizinho (ou adjacente) de v.

Um dígrafo é simétrico se cada um de seus arcos é anti-paralelo* a algum outro arco.
*arcos anti-paralelos: Para um arco v-w temos também um arco w-v, estes dois arcos são anti-paralelos.

Grau de entrada e de saída
O grau de saída de um vértice v em um dígrafo é o número de arcos que começam em v. O grau de entrada de um vértice v em um dígrafo é o número de arcos que terminam em v.
Uma fonte é um vértice que tem grau de entrada nulo (= 0) e um sorvedouro é um vértice que tem grau de saída nulo (= 0).
Um vértice é isolado se seu grau de entrada e seu grau de saída são ambos nulos.

Grau de entrada e de saída
O grau de saída de um vértice v em um dígrafo é o número de arcos que começam em v. O grau de entrada de um vértice v em um dígrafo é o número de arcos que terminam em v.
Uma fonte é um vértice que tem grau de entrada nulo (= 0) e um sorvedouro é um vértice que tem grau de saída nulo (= 0).

Um vértice é isolado se seu grau de entrada e seu grau de saída são ambos nulos.

Grafos valorados (Redes ≡ Networks)

Em grafos valorados, a cada arco (ou nó) de G é associado um valor numérico, ou peso.

               Uma Rede é um grafo não-direcionado (ou um dígrafo) no qual um número real é associado os vértices e/ou ligações. Este número é freqüentemente referido como o peso da ligação. Essa classificação é dada de acordo com a necessidade, ou não, da indicação do fluxo entre os vértices.

Em grafos valorados, a cada arco (ou nó) de G é associado um valor numérico, ou peso.

               GRAFO VALORADO

Um grafo  G(V,A) é dito ser valorado quando existe uma ou mais funções relacionando V e/ou A com um conjunto de números. Para exemplificar (ver o grafo G₇), seja G(V,A) onde:

•        V = {v | v é uma cidade com aeroporto}

•        A = {(v,w,t) | <há linha aérea ligando v a w, sendo t o tempo esperado de voo>}