UNIVERSIDADE FEDERAL DE UBERLNDIA
FACULDADE DE MATEMTICA
Giselle Moraes Resende Pereira (PET Matemtica SESu-MEC) [email protected]
Marcos Antnio da Cmara (Tutor do PET Matemtica) [email protected]
Algumas Aplicaes da Teoria dos Grafos 1. INTRODUO Ao contrrio de muitos ramos da matemtica, nascidos de especulaes puramente tericas, a teoria dos grafos tem sua origem no confronto de problemas prticos. A teoria dos grafos estuda objetos combinatrios -os grafos- que so um bom modelo para muitos problemas em vrios ramos da matemtica, da informtica, da engenharia, da qumica, da psicologia e da indstria. Muitos dos problemas sobre grafos tornaram-se clebres porque so um interessante desafio intelectual e porque tm importantes aplicaes prticas. inevitvel esbarrar em questes de complexidade computacional, pois muitos dos problemas da teoria dos grafos tm motivao algortmica. 2. BREVE HISTRICO Enquanto outros temas de matemtica tm uma longa e gloriosa histria, isto no acontece com a Teoria de Grafos. O primeiro problema cuja soluo envolveu conceitos do que veio a ser a teoria dos grafos (sc. XVII) foi resolvido por Euler e no passava de uma especulao matemtica. Acredita-se que um dos primeiros exemplos da utilizao de grafos teria surgido devido as Pontes de Knigsberg. Na cidade de Knigsberg (atual Kaliningrado), antiga capital da Prssia Oriental, o rio Pregel circunda uma ilha e separa a cidade em quatro zonas que, no sc. XVII estavam ligadas por sete pontes como na figura 1:
Figura 1
Edson
EdsonFAMAT em Revista - Nmero 11 - Outubro de 2008 67
3. CONCEITOS PRELIMINARES Um Grafo G(V, E) uma estrutura matemtica constituda pelos conjuntos:
V, finito e no vazio de n vrtices, e E, de m arestas, que so pares no ordenados de elementos de V.
Graficamente representado por uma figura com Ns ou vrtices, unidos por um trao denominado Aresta configurando a relao imaginria, vejam figura 2.
Figura 2: Esta figura um desenho do grafo cujos vrtices so e cujas arestas so { z ,y x, w,, vu, ,t =V } { } xyyz, xu, xw,uv, vw,=E e o grafos trivial.
Embora seja conveniente a representao de grafos atravs de diagramas de pontos ligados por linhas, tal representao inadequada se desejamos armazenar grandes grafos em um computador. 3.1 Matriz de adjacncia: Se G um grafo com vrtices {1,2,3,...,n}, sua matriz de adjacncia a matriz n X n cujo elemento ij o nmero de arestas ligando o vrtice i ao vrtice j.
0000002002010011
4
3
2
1
4321
vvvv
vvvv
3.2 Matriz de incidncia: Se G um grafo com vrtices {1,2,3,...,n} e arestas {1,2,3,...,m}, sua matriz de incidncia a matriz n X m cujo elemento ij o nmero de vezes em que o vrtice i incidente aresta j.
0000011001112001
4
3
2
1
4321
vvvv
eeee
3.3 Adjacncias de vrtices e arestas: 3.3.1 Dois vrtices x e y so ditos adjacentes ou vizinhos se existe uma aresta unindo-os.
Edson
Claiton68 FAMAT em Revista - Nmero 11 - Outubro de 2008
3.3.2 Duas arestas so adjacentes se elas tm ao menos um vrtice em comum. 3.4 Incidncias: Os vrtices x e y so ditos incidentes na aresta, se eles so extremos da aresta. 3.5 Vrtices isolados: Qualquer vrtice de grau zero um vrtice isolado. 3.6 Laos: Lao uma aresta que une um par de vrtices idnticos. 3.7 Arestas paralelas: Quando existe mais de uma aresta entre o mesmo par de vrtices. Exemplificando, na figura 3 est representado um grafo de e
. { }6,5,4,3,2,1=V
{ }(5,2)(6,5),(6,1),(1,5),(2,2),(3,2),(1,2),=E
5
2 1
6 4
3
Vrtices adjacentes
Lao
Vrtice isolado
Arestas paralelas
Arestas adjacentes
Figura 3
3.8 Passeio entre ns: a seqncia alternantes de ns e arestas. 3.9 Caminho: Um caminho qualquer grafo da forma ({ }nvvv ...,,, 21 { }nivv ii
3.12 Dgrafo: Um Grafo Direcionado ou Dgrafo D(V,E) uma estrutura matemtica constituda pelos conjuntos:
V, finito e no vazio de n vrtices, e E, de m arestas, que so pares ordenados de elementos de V.
3.13 Conexidade: Um grafo conexo se, para qualquer par {v,w} de seus vrtices, existe um caminho com extremos v e w. E um grafo no conexo se existir ao menos um par de vrtices que no unido por nenhum caminho.
Figura 5: a) grafo conexo; b) e c) grafos no conexos 3.14 Grafo Bipartido: Um grafo dito ser bipartido quando seu conjunto de vrtices V puder ser particionado em dois subconjuntos V1 e V2, tais que toda aresta de G une um vrtice de V1 a outro de V2 (figura 6).
Figura 6
3.15 Grafo Rotulado: Um grafo G(V,E) dito ser rotulado em vrtices (ou arestas) quando a cada vrtice (ou aresta) estiver associado um rtulo (figura 7).
Figura 7
3.16 Grafo valorado: Um grafo G(V, E) dito ser valorado quando existe uma ou mais funes relacionando V e/ou E com um conjunto de nmeros (figura 8).
Figura 8
Edson
Claiton70 FAMAT em Revista - Nmero 11 - Outubro de 2008
Teorema 1: Em todo grafo, a soma dos graus dos vrtices igual ao dobro do nmero de arestas. Ou seja, todo G(V, E) satisfaz a identidade = AvgVv 2)(
Demonstrao: Uma aresta com vrtices x e y contribui uma unidade para g(x) e uma unidade
orolrio 1: O nmero de ns de grau mpar de um grafo par.
para g(y). Portanto, cada aresta contribui exatamente duas unidades para a soma )(vgVv . CDemonstrao: Como a soma dos graus igual a A2 , considere o grafo G(N, A).
Denotando por d o grau do n i, temos:
i
A2 = iii
ddd
Como
+= mpard
ipard
ii
A2 par ento a soma das duas parcelas tambm ser par. ero par, devemos
. OPERAES DE ARESTAS E VRTICES
eja G(V, E) um grafo constitudo de um conjunto V, finito e no vazio de n vrtices, e um
.1 Incluso da aresta (v,w)em pertencer a V.
Observe que para ter uma soma de parcelas mpares resultando em um nmter um nmero par de parcelas, o que conclui a demonstrao. 4 Sconjunto E de m arestas. 4 Exigncia: os vrtices v e w devGrafo resultante: ),( wvG + definido por V e E { }).(v w .
ena a G, er pelo menos um par de arestas paralelas. Se
.2 Excluso da aresta (v,w) pertencer a E.
(v,w)}
.2.1 Situao Problema I: Rede viria com mo direcional do trnsito
ato:
Caso (v,w) j pert o grafo resultante tv = w, h o surgimento de um lao. 4Exigncia: a aresta (v,w) deve Grafo resultante: G-(v,w) definido por V e E-{ 4 F Houve um rompimento na rede de fornecimento de gua em uma regio da cidade impedindo o trnsito nessa regio. Ao: Interrupo do trnsito no trecho de rua.
Edson
EdsonFAMAT em Revista - Nmero 11 - Outubro de 2008 71
Solucionando o problema do trnsito:
Acionar o Departamento de Trnsito para alterar o trfego local. Divulgar aos interessados as aes em andamento. Reparar a pavimentao da rua. Restabelecer o trnsito da regio.
A interrupo do trnsito no trecho de rua implica na excluso da aresta associada. Dgrafo resultante da excluso da aresta associada 4.3 Incluso do vrtice v Exigncia: o vrtice v no deve pertencer a V.
{ }vV e E. Grafo resultante: G+v definido por 4.4 Excluses do vrtice v Exigncia: o vrtice v deve pertencer a V e . 1>nGrafo resultante: G-v definido por V-{v} e E-{(v,u), u adjacente a v}. A restrio garante que, mesmo aps a excluso do vrtice, a estrutura remanescente continue sendo um grafo.
1>n
Figura 9. Exemplos de incluso e excluso de vrtices e arestas. 4.5 Fuso dos vrtices v e w Exigncia: os vrtices v e w devem pertencer a V.
Edson
Claiton72 FAMAT em Revista - Nmero 11 - Outubro de 2008
{ } { }vwwvV ,( { } ,,(( uvEGrafo resultante: definido por vwG e u adjacente a v}) {(w, u) u adjacente a w}) {(vw, u), u adjacente a v ou w em G}. 4.6 Exploso do vrtice v Exigncia: o vrtice v deve pertencer a V e grau(v)>0. Grafo resultante : Para obter o grafo deve-se quebrar o vrtice v em grau(v) pedaos de modo que as arestas que o tm como extremo tambm pertenam ao novo grafo, embora no sejam mais adjacentes.
vG*
Figura 10. Exemplos de Fuso e Exploso de vrtices.
4.6.1 Situao Problema II: Rede de gua de uma regio. Fato: Houve um rompimento na rede de fornecimento de gua em uma regio da cidade. Ao: Recompor o funcionamento da rede de gua da regio.
Fechar registro significa: Explodir vrtices
Figura 11. rea atendida x rea Atingida
Edson
EdsonFAMAT em Revista - Nmero 11 - Outubro de 2008 73
5. GRAFOS EULERIANOS Ciclo euleriano aquele que possui todas as arestas do grafo exatamente uma vez. Um Grafo euleriano aquele que possui um ciclo euleriano, em outras palavras, um grafo euleriano se pudermos desenh-lo sem tirar o lpis do papel e voltar ao ponto de partida, sem passar mais de uma vez por nenhuma aresta. 5.1 As pontes de Knigsberg Na cidade de Knigsberg (atual Kaliningrado), antiga capital da Prssia Oriental, o rio Pregel circunda uma ilha e separa a cidade em quatro zonas que, no sc. XVII estavam ligadas por sete pontes como na figura 12:
Figura 1
