0
CENTRO UNIVERSITÁRIO ADVENTISTA DE SÃO PAULO
CAMPUS SÃO PAULO
CURSO DE MATEMÁTICA
GRAFOS E SUAS APLICAÇÕES
FABIANA NASCIMENTO SANTOS CAVALCANTE
SEVERINO DOMINGOS DA SILVA
SÃO PAULO
2009
1
FABIANA NASCIMENTO SANTOS CAVALCANTE
SEVERINO DOMINGOS DA SILVA
GRAFOS E SUAS APLICAÇÕES
Trabalho de conclusão de curso apresentado
para obtenção do título de licenciando em
matemática pelo Centro Universitário Adventista
de São Paulo, campus São Paulo.
Orientador: Prof. Dra. Elba Bravo Asenjo.
SÃO PAULO
2009
2
A Eliane
3
A Silas
4
AGRADECIMENTOS
Nós, elaboradores deste trabalho, agradecemos primeiramente a Deus, que
nos capacitou dos conhecimentos necessários para realizarmos este e tantos outros
trabalhos que ocorreram durante o curso.
Agradecemos, ainda, a nossa família, pelas horas de convívio que fomos
obrigados a subtrair para que fosse possível chegar a este final; agradecemos,
também, a professora Dra Elba, pelo tempo que nos concedeu orientando neste
projeto; a doutora Rita, por toda a paciência, por todos os dias, tardes e noites em
que dispôs de seus momentos, corrigindo e adequando tudo o quanto digitávamos,
ao André, pelas figuras, pois sem sua colaboração seríamos incapazes de executar
essa tarefa. Agradecemos, ainda, a Silas e Eliane, por seu desprendimento e boa
vontade, colaborando, mesmo que indiretamente, para que esta idéia fosse hoje
uma realidade. Por último, e não menos importante, agradecemos a todos aqueles
que, de alguma forma, contribuíram para o êxito deste TCC.
5
Grafos, você pode não conhecer,
mas a sua vida depende deles..
( Fabiana e Severino)
6
RESUMO
O TCC em foco apresenta um trabalho sobre grafos, onde se procurou
demonstrar através de definições e exemplos a importância do mesmo na
matemática e no cotidiano das pessoas. Foram apresentados os fundamentos
teóricos dos Grafos, os quais introduzem alguns conceitos básicos dessa teoria
como grau de vértice, caminho, circuito, corte, subgrafo, conexão, componente,
árvore, grafo aleatório etc. O conceito dos Grafos foi definido como sendo estruturas
muito usadas para representar a existência ou não de relações entre elementos de
um dado conjunto. Assim, redes de comunicação, fluxos em rede de transporte,
mapas geográficos e relações binárias em geral podem ser representadas por
grafos, e nesse caso várias questões de interesse foram investigadas. No estudo
dos Grafos destacou-se a figura mais importante na sua elaboração, o qual foi
destacado de forma eloqüente neste trabalho - Leonardo de Euler -, o matemático
mais produtivo do mundo, que não se contentou apenas em descobrir equações ou
em demonstrar novos teoremas, mas procurou, por sua vez, pesquisar sobre os
trabalhos de seus antecessores como Newton, Descarte e Leibniz. Constatou-se
que Euler ainda ajudou a criar um novo ramo totalmente inédito da matemática, a
topologia, que para ficar mais fácil de entender foi utilizado o exemplo das setes
pontes de Königsberg. Através do exemplo citado foi possível saber se era possível
entrar e sair da referida cidade, situada numa ilha, atravessando apenas uma vez
todas as setes pontes que a mesma tinha; situação esta observada como impossível
por Euler, dando inicio ao raciocínio topológico, que é o marco da teoria dos grafos,
objeto de estudo neste trabalho. Este, pois, é um breve resumo de todo conteúdo
apresentado no TCC, sendo que a demonstração minuciosa dos grafos ocorreu ao
longo do mesmo.
Palavras Chaves: Grafos – topologia – Leonardo Euler
7
LISTA DE FIGURAS
1.1 CASINHA ........................................................................................................................12
1.2 O ESBOÇO DO PROBLEMA DO GÁS LUZ E TELEFONE...........................................12
1.3 O PROBLEMA DO TRAJETO ........................................................................................13
2.1 MAPA AÉREO ................................................................................................................19
2.2 GRAFO COM CINCO NÓS E CINCO ARCOS...............................................................21
2.3 TORNEIO DE VÔLEI ......................................................................................................22
2.5 NÓS ADJACENTES........................................................................................................24
2.6 GRAFO COM LAÇO .......................................................................................................25
2.7 GRAFO COM CINCO NÓS E SEIS ARCOS ................................................................25
2.8 O GRAFO DO CAMPEONATO COMPLETO .................................................................27
2.9 GRAFO SIMPLES E COMPLETO ..................................................................................27
2.10 GRAFO SIMPLES IMCOMPLETO ...............................................................................28
2.11 GRAFOS COMPLEMENTARES ..................................................................................28
2.12 GRAFOS NULO OU VAZIO ..........................................................................................29
2.13 SUBGRAFOS.................................................................................................................29
2.14 SUBGRAFO INDUZIDO.................................................................................................30
2.15 GRAFO DE QUATRO NÓS ...........................................................................................30
2.16 COMPRIMENTO DE UM CAMINHO .............................................................................32
2.17 CAMINHO: SIMPLES E TRILHA ..................................................................................32
2.18 UM OU DOIS GRAFOS? ...............................................................................................32
2.19 CONEXIDADE ...............................................................................................................33
2.20 CICLO ............................................................................................................................34
2.21 UM DOS POSSÍVEIS GRAFOS DA REVISÃO ............................................................34
2.22 GRAFOS EULERIANOS ...............................................................................................36
2.23 GRAFOS PLANARES....................................................................................................39
8
2.24 GRAFO PLANAR SIMPLES E CONEXO .....................................................................40
2.25 GRAFO CONEXO .........................................................................................................40
2.26 REGIAO LIMITADA .......................................................................................................42
3.1 CIDADE DE KÖNIGSBERG.............................................................................................46
3.2 O PROBLEMA DAS SETE PONTES...............................................................................46
3.3 PRIMEIRO ESBOÇO DE UM GRAFO.............................................................................47
4.1 RESOLUÇÃO DO PROBLEMA DA CASINHA...............................................................49
4.2 PROBLEMA GÁS, LUZ E TELEFONE ...........................................................................49
4.3 SITUAÇÀO REPRESENTADA GEOMETRICAMENTE.................................................50
4.4 GRAFOS COM DUAS REGIÕES LIMITADAS ..............................................................51
4.5 O GRAFO DO GÁS LUZ E TELEFONE..........................................................................51
4.6 GRAFO DO TRAJETO ....................................................................................................52
4.7 O PROBLEMA DO RECOLHIMENTO DE LIXO .............................................................53
4.8 RESOLUÇÃO PARA O RECOLHIMENTO DE LIXO......................................................54
4.9 CAIXEIRO VIAJANTE .....................................................................................................56
4.10 CALIFA PÉRCIO ...........................................................................................................57
4.11 FILHAS CASADOURAS................................................................................................58
4.12 CASAMENTO TOPOLOGICAMENTE IMPEDIDO.......................................................58
4.13 PERCURSOS EULERIANOS .......................................................................................59
4.14 CAMINHO EULERIANO ...............................................................................................60
9
SUMÁRIO
1 INTRODUÇÃO ...................................................................................... 11
1.2 OBJETIVO GERAL ................................................................................................................ 14
1.3 OBJETIVOS ESPECÍFICOS ................................................................................................. 14
1.4 JUSTIFICATIVA ..................................................................................................................... 14
1.5 METODOLOGIA ..................................................................................................................... 16
1.6 MOTIVAÇÃO ........................................................................................................................... 17
1.7 ESTRUTURA .......................................................................................................................... 18
2 FUNDAMENTOS TEÓRICOS .............................................................. 19
2.1 DEFINIÇÃO (INFORMAL) DE GRAFOS ............................................................................ 20
2.2 DEFINIÇÃO (FORMAL) DE GRAFOS ................................................................................ 21
2.3 GRAFOS DIRECIONADOS .................................................................................................. 23
2.4 NÓS ADJACENTES E NÓ ISOLADO ................................................................................. 24
2.5 LAÇO........................................................................................................................................ 25
2.6 ARCOS PARALELOS ........................................................................................................... 25
2.7 GRAFOS SIMPLES................................................................................................................ 26
2.8 GRAU DE UM NÓ .................................................................................................................. 26
2.9 GRAFO COMPLETO ............................................................................................................. 26
2.9.1 Grafo Complementar .................................................................................................... 28
2.9.2 Grafo Nulo ou Vazio ...................................................................................................... 29
2.10 SUBGRAFO .......................................................................................................................... 29
2.11 CAMINHO .............................................................................................................................. 30
2.12 COMPRIMENTO DE UM CAMINHO ................................................................................. 31
2.12.1 Caminho Simples, Trilha. .......................................................................................... 31
2.13 GRAFO CONEXO ................................................................................................................ 32
2.15.1 REVISÃO DOS CONCEITOS VISTOS ...................................................................... 34
2.16 GRAFOS EULERIANOS ..................................................................................................... 35
10
2.17. TEOREMA SOBRE OS NÓS IMPARES DE UM GRAFO ........................................... 36
2.18 TEOREMA SOBRE CAMINHOS DE EULER ................................................................. 38
2.19 GRAFOS PLANARES ........................................................................................................ 39
3 BREVE HISTÓRICO E EXEMPLOS DE APLICAÇÕES ..................... 43
3.1 BIOGRAFIA DE LEONHARD EULER ................................................................................ 44
3.2 EULER E AS PONTES DE KÖNIGSBERG. ...................................................................... 45
3.3 CIDADE DE KÖNIGSBERG ................................................................................................. 46
4 ALGUNS PROBLEMAS CLÁSSICOS SOBRE GRAFOS.................. 48
4.1 PROBLEMA DA CASINHA ................................................................................................. 48
4.2 O PROBLEMA DO GÁS,LUZ E TELEFONE. ................................................................... 49
4.3 O PROBLEMA DO TRAJETO DA TRANSPORTADORA ............................................... 52
4.4 O PROBLEMA DO RECOLHIMENTO DE LIXO. .............................................................. 53
4.5 O PROBLEMA DO CAIXEIRO VIAJANTE ........................................................................ 55
4.6 CASAMENTO TOPOLOGICAMENTE IMPEDIDO ............................................................ 57
4.7 GRAFO EULERIANO ........................................................................................................... 59
4.8 ENCONTRE UM CAMINHO EULERIANO ......................................................................... 59
5 CONSIDERAÇÕES FINAIS ................................................................. 61
BIBLIOGRAFIA........................................................................................ 62
11
1 INTRODUÇÃO
A teoria dos grafos é um assunto antigo com muitas aplicações modernas. As
idéias básicas de grafos foram introduzidas no século
, pelo famoso
matemático suíço Leonhard Euler. Ele usou grafos para resolver o problema hoje
conhecido como As sete pontes de Königsberg. Este foi o ponto de partida para se
dar início à teoria dos grafos e um novo ramo da matemática chamado topologia.
Grafos são usados para resolver problemas em muitos campos, tais como na
representação de qualquer rede de rotas de transporte (um mapa de estradas, por
exemplo), rede de comunicação (como em uma rede de computadores), ou rotas de
distribuição de produtos ou serviços, como dutos de gás ou água, etc. A estrutura
química de uma molécula também pode ser representada por um grafo [1].
Até há pouco tempo, a teoria dos grafos era apreciada mais como um
entretenimento matemático do que uma teoria. Devido ao aparecimento dos
computadores e o grande avanço tecnológico houve a necessidade de encontrar
caminhos mais curtos para ser ter respostas mais rápidas. Em um computador, por
exemplo, pode ser armazenado vários dados em “arquivos”. Comumente, se
organizam esses arquivos de forma sistemática, utilizando-se de certo critério
(exemplo disto é: se o arquivo for uma lista de nomes de pessoas com seus
endereços, ele poderá ser ordenado “indexado”, na nomenclatura da linguagem
computacional através do nome da pessoa, seu endereço, seu CEP, etc.). Este
arquivo tem uma “estrutura de árvore”, isto é, uma estrutura que é certo tipo de
grafo. O enigma é determinar qual o “caminho” mais breve para chegar a um dos
dados armazenados neste arquivo. Pensando numa pesquisa operacional, um
exemplo claro de grafo é o da rede de distribuição de energia de uma região
qualquer do Brasil, como também a rede de ruas de uma cidade, sempre visando
viabilizar percursos.
É importante ressaltar que a teoria dos grafos, independentemente das
aplicações importantes e variadas, é fonte de um grande número de problemas
atraentes, complexos e de simples enunciados.
Observe-se o exemplo de uma cidade com pequeno orçamento. O serviço de
recolhimento de lixo é feito por um caminhão de diminuto porte. Pretende-se evitar o
desperdício; uma boa idéia seria fazer o caminhão passar uma única vez por cada
12
rua e retornar ao ponto de partida. Esse exemplo tem a mesma situação problema
que o exemplo a seguir conhecido como o problema da casinha.
É possível desenhar a Figura1.1 abaixo sem tirar o lápis do papel? Tem que
passar de ponto a ponto e não pode passar pela mesma linha duas vezes.
Figura 1.1 Casinha
Foi fácil? Experimente agora começar pelo ponto B?
Um outro problema que pode ser proposto é tentar ligar: Luz, Gás e Telefone
à três casas, sem que as linhas se cruzem, (supondo que todas as ligações, fios e
canos estejam situados em um mesmo plano),[2].como mostra a Figura 1.2 .
Figura 1.2 O esboço do problema do gás, luz e telefone
Um dos problemas muito importante em matemática aplicada é o de encontrar
trajetos mais curtos ligando dois vértices de um grafo. Por exemplo, o grafo da
(Figura 1.3) representa as estradas ligando 5 cidades diferentes. As distâncias
são todas em quilômetros. Uma transportadora deseja sair de
as cidades e retornando a
passando por todas
, de maneira que o trajeto seja o mais curto possível.
13
Figura 1.3 O problema do trajeto,[3]
É possível fazer um trajeto saindo de
, passando por todas as arestas uma
única vez, e retornado ao ponto de partida ?
Tente obter um trajeto para a transportadora saindo e retornando a , passando por
todas as outras cidades, de modo que a distância percorrida seja a menor
possível,[3].
Observando esses exemplos cabe a pergunta: esses problemas são
importantes? Analise-se o caso de uma fábrica de placas de circuito integrado.
Encontrar esquemas de ligação que evitem cruzamento é crucial para baratear os
custos de manufatura; quanto menos camadas, mais rápido e rentável se torna o
serviço. Em todos os casos só interessa considerar um conjunto de pontos e um
conjunto de ligações entre eles. É a essa estrutura que chama-se grafo.
O presente trabalho trata das informações e esclarecimentos, relevantes e
necessários, para que a monografia em foco seja bem compreendida. Para tanto o
mesmo encontra-se dividido em cinco capítulos, sendo o primeiro uma concisa
apresentação do todo e, nos demais capítulos, encontram-se inseridos o
desenvolvimento do tema, suas definições (informal e formal); o conceito geral; um
breve histórico sobre a vida de Leonardo de Euler; a forma como se deu inicio a
teoria dos grafos; as aplicações e relação dos grafos com os acontecimentos do
cotidiano, e toda uma elaboração visando uma completa assimilação e clareza dos
tópicos explanados.
14
1.2 OBJETIVO GERAL
O objetivo principal deste trabalho é apresentar, explicar e esclarecer os
pontos relevantes acerca dos Grafos, apresentando desde seus conceitos e
espécies até uma síntese da vida de seu criador, o matemático Leonhard Euler.
Mostrar a existência ou não de relações entre elementos de um dado
conjunto, como redes de comunicação, fluxos em rede de transporte, mapas
geográficos e relações envolvidas em nosso dia-dia em geral.
1.3 OBJETIVOS ESPECÍFICOS
-
Estudo da teoria dos Grafos, tendo como resultado a solução do problema
das sete pontes.
-
Conhecer a definição de um grafo.
Introduzir o estudante, aos problemas, aos métodos, à linguagem da teoria
dos grafos e seus aspectos históricos.
Utilizar os conceitos dos grafos, agora já conhecidos, para viabilizar alguns
problemas que envolvam a topologia com a facilidade dos conceitos de grafos.
1.4 JUSTIFICATIVA
O intuito dos elaboradores deste trabalho foi realizar pesquisas para entender
o significado dos Grafos na ciência da matemática. Todo o estudo foi direcionado no
sentido de uma completa elucidação acerca do assunto, visando dirimir qualquer
dúvida sobre a importância do conhecimento dos Grafos e sua aplicação dentro do
contexto matemático.
15
Buscou-se exemplos e conceitos para explicar a relevância dos Grafos diante
dos variados problemas enfrentados no dia a dia; onde é imprescindível que se
tenha conhecimento e se entenda o porquê dos mesmos.
A intenção dos pesquisadores foi, e de fato é, contribuir para o despertar dos
estudantes da matemática sobre a necessidade de um aprendizado profundo
referente ao tema; para tanto elaborou-se um trabalho onde se procurou discutir
exaustivamente o assunto, esclarecendo e pontuando as principais idéias e os
principais tópicos dos Grafos, inseridos no estudo da ciência dos números.
O estudo apresentado, obviamente, não esgotou o tema, entretanto, foi
profundamente no âmago da questão, visando deixar sua pequena contribuição para
que, no futuro, o mesmo, sem medo de cair na falsa modéstia, sirva de subsídio para
aqueles que pretendam entender o assunto, prestando-se, ainda, como fonte de
pesquisa para quem quer entender o que, e para que, servem os grafos.
16
1.5 METODOLOGIA
Como metodologia que conduz o estudo apresentam-se:
1. Levantamento bibliográfico atualizado de forma a compreender a utilização da
teoria dos grafos tanto na computação como também na matemática.
2. Pesquisa feita em todo material selecionado, no qual continha informações
sobre grafos.
3. Análise e elaboração de problemas alguns resolvidos, envolvendo o objeto de
pesquisa, (grafos). Como também suas aplicações.
De forma a contemplar a plena execução desse trabalho, utilizamos como meios
de pesquisa bibliográfica o material referenciado na bibliografia.
17
1.6 MOTIVAÇÃO
Leonhard Euler, foi percussor desta teoria, ajudando a criar um novo ramo
totalmente inédito da matemática - a topologia -, que, para ficar mais fácil de
entender, utilizou-se do exemplo das setes pontes de konigsberg, onde se buscava
conhecer a possibilidade de entrar e sair da citada cidade, atravessando apenas
uma vez todas as sete pontes. O objetivo de Euler era demonstrar que tal feito era
impossível, e o fez dando início ao raciocínio topológico, que é o marco da teoria dos
grafos.
A motivação na realização do presente trabalho foi demonstrar que os Grafos
estão inseridos na ciência da matemática; foi à descoberta de que estes são
utilizados não apenas para computação, mas também, e de forma preponderante,
no estudo dos números – a matemática.
O ponto de maior interesse dos pesquisadores, que passou de mera
curiosidade para completo esclarecimento, foi saber que utilizam-se os grafos nas
mais diversas situações cotidianas, entendendo que os mesmos são objeto do
trabalho dos portos, da via aérea e demais realidades onde se faz necessário o
traçar de pontos imaginários.
O que se espera é que ao final o leitor tenha se convencido da utilidade dos
conceitos e processos apresentados, mas guarda-se o secreto desejo de que os
aspectos lúdicos dos grafos o contaminem com o que costuma-se chamar de
”graphical desease”,[2] ou melhor, traduzindo, a febre dos grafos.
18
1.7 ESTRUTURA
A estrutura do trabalho foi desenvolvida em cinco capítulos, onde os dois
primeiros são meramente teóricos, tratando das definições e bases necessárias à
proposta, o terceiro enfatiza sobre a vida de seu descobridor,(Euler).apresenta e
define por completo
o conhecido problema que é o percussor desta teoria, os
demais apresentam os resultados do trabalho; a saber:
Capítulo 1: Introdução.
Capítulo 2: Toda fundamentação teórica: definição de grafos,(vértices, grafos
simples e completo, grafos Eulerianos,grafos convexos, etc.)
Capítulo 3: Biografia de Leonhard Euler e o problema das sete pontes.
Capítulo 4: Aplicações e exemplos resolvidos.
Capítulo 5:Considerações finais.
19
2 FUNDAMENTOS TEÓRICOS
Este capítulo introduz alguns conceitos básicos da teoria dos grafos
(definição, nós, laços, grau de vértice, caminho, circuito, subgrafo, conexão, etc.).
Esses conceitos são necessários para estudar os grandes problemas de que
trataremos nos capítulos 3 e 4. Sugere-se que o leitor faça uma primeira leitura
superficial deste capítulo e avance imediatamente para o capítulo 3. Mais tarde,
quando houver necessidade, o leitor poderá voltar a este capítulo para rever
conceitos e examinar as sutilezas de algumas definições.
Grafos são estruturas muito usadas para representar a existência ou não de
relações entre elementos de um dado conjunto. Assim, redes de comunicação,
fluxos em rede de transporte, mapas geográficos e relações binárias em geral
podem ser representadas por grafos, e nesse caso várias questões de interesse
podem ser investigadas.
Acredita-se que muitos para passar a hora em uma viagem de avião utilizamse de livreto nos bolsos do assento e nesse material quase sempre inclui uma rota
da companhia de viagem, proprietária do avião,[1] como na Figura 2.1.
Figura 2.1 Mapa aéreo,[4]
Toda essa informação sobre rotas poderia ser expressa em forma de texto, por
exemplo, existe uma rota direta entre Belo Horizonte e Rio de Janeiro, mas não
existe uma rota direta entre o Rio de Janeiro e Brasília. Portanto esse texto seria
20
bastante longo e complicado e não seríamos capazes de assimilar as informações
tão rápidas e claras como vemos no mapa, existe muitos casos em que uma figura
fala mais que mil palavras.
Utilizam-se duas definições de grafos: uma é baseada na representação visual
como na Figura 2.1 e a outra é uma definição mais formal que não fala nada sobre
uma representação visual.
2.1 DEFINIÇÃO (INFORMAL) DE GRAFOS
Um grafo é o conjunto não vazio de nós (vértices) e um conjunto de arcos
(arestas) tais que cada arco conecta-se a dois nós.
Nota: Neste trabalho os grafos sempre terão um numero finito de nós e de
arcos.
Exemplo 1
O conjunto de nós no mapa das rotas aéreas na Figura 2.1 é {Porto Alegre,
Brasília, Belo Horizonte, Rio de Janeiro e São Paulo}. O grafo tem
arcos; Porto
Alegre – Brasília é um arco (denomina-se, aqui, os arcos pelos nós que ele
conecta),
Brasília – Belo Horizonte é outro arco,e assim sucessivamente.
Exemplo 2
O grafo da Figura 2.2 tem cinco nós e cinco arcos. O arco
e
,
3
conecta aos nós 1 e , e assim sucessivamente.
1, conecta
aos nós
21
Figura 2.2 Grafos de cinco nós e cinco arcos [1]
A definição informal de um grafo funciona muito bem se existir a representação
visual do grafo. Sem uma figura, no entanto, será necessário uma forma concisa de
mostrar essa informação, isso conduz a segunda definição de grafos.
2.2 DEFINIÇÃO (FORMAL) DE GRAFOS
Um grafo é uma tripla ordenada (
), onde:
= um conjunto não vazios de nós ( vértices)
= Um conjunto de arcos (arestas)
= uma função que associa cada arco
a um par não ordenado
de nós,
chamados as extremidades de .
Para o grafo da Figura 2.2, a função
seguinte,[1]:
que associa arcos e suas extremidades é a
22
Exemplo 3 Grafo Do Campeonato
Numa escola algumas turmas resolveram realizar um torneio de vôlei.
Participam do torneio as turmas 6A, 6B, 7A, 7B, 8A e 8B. Alguns jogos foram
realizados até agora:
6A jogou com 7A, 7B, 8B
6B jogou com 7A, 8A, 8B
7A jogou com 6A, 6B
7B jogou com 6A, 8A, 8B
8A jogou com 6B, 7B, 8B
8B jogou com 6A, 6B, 7B, 8A
O exemplo pode não estar correto. Pode ter havido um erro na listagem.
Representa-se esta situação através de uma figura. Às turmas serão representadas
por pontos e os jogos serão representados por linhas como na Figura 2.3.
Figura 2.3 Torneio de volei,[2]
Não é difícil agora constatar a certeza das informações. O que se passa a
conhecer é um grafo. Apresentam-se duas formas de representá-lo:
a) Por uma lista, dizendo quem se relaciona com quem.
b) Por um desenho, isto é, uma representação gráfica.
23
Os dois exemplos citados são corretos, pois o Grafo admite várias maneiras
de ser representado:
a palavra “dois”e o símbolo “ ” representa o mesmo conceito matemático.
Para que um grafo fique bem definido temos que ter dois conjuntos:
• O conjunto
, dos vértices, no exemplo citado, o conjunto das turmas.
• O conjunto , das arestas, no exemplo acima, os jogos realizados.
Em outras palavras, o que interessa num grafo é:
• Quem são os vértices.
• Que pares de vértices estão ligados e quais não estão (isto é, quem são as arestas
se houver, pois também pode-se ter um grafo nulo),[2].
Se os arcos de um grafo comecem em um nó e terminem em outro, neste
caso tem-se um grafo direcionado.
2.3 GRAFOS DIRECIONADOS
Um grafo direcionado (dígrafo) é uma tripla ordenada (
), onde
= um conjunto não vazio de nós
= um conjunto de arcos
= uma função que associa a cada arco um par ordenado (
ponto inicial e
) de nós, onde
éo
é o ponto final de a,em um grafo direcionado, cada arco tem um
sentido ou orientação.
Exemplo 4:
A Figura 2.4 mostra um grafo direcionado, com
que associa a cada arco suas extremidades satisfaz
que o arco
começa no nó
e termina no nó
nós e
arcos. A função
o que significa
. Temos também,
24
Figura 2.4 Grafo direcionado,[1]
Além de impor orientação aos arcos de um grafo, pode-se também querer
modificar a definição básica de um grafo de outras maneiras, muitas vezes, o que se
quer é que os nós de um grafo contenham informações identificadoras, ou rótulos,
como os nomes de cidades no mapa de rotas áreas. Esse seria um grafo rotulado.
Pode-se querer usar um grafo com pesos, onde cada arco tem um valor numérico,
ou peso, associado. Por exemplo, pode-se querer indicar as distâncias nas várias
rotas no mapa da companhia aérea como mostra a Figura 2.1.
Neste trabalho a palavra “grafo” sempre indicará um grafo não direcionado, se
por algum motivo se fizer referência a grafo direcionado, sempre usar-se-à a palavra
“grafo direcionado”.
Outros artigos, no entanto, podem ter nomes ligeiramente diferentes de
alguns desses termos.
2.4 NÓS ADJACENTES E NÓ ISOLADO
Dois nós em um grafo são ditos adjacentes se ambas são as extremidades
de algum arco. Por exemplo, no grafo da Figura 2.5,
e 3 não. O nó
e 2 são nós adjacentes, mas
é adjacente a si mesmo, 4 e 3 são nós adjacentes, porém 4 e 6
não são adjacentes. Um nó isolado é um nó que não é adjacente a nenhum outro;
Na Figura 2.5, o nó
é um nó isolado.
Figura2.5 Nós adjacentes
25
2.5 LAÇO
Algumas dúvidas podem surgir acerca das definições, veja-se:
Uma aresta pode ligar um vértice a ele mesmo?. Pode!. É o que se chama de
laço (veja Figura 2.6). Assim, um laço em um grafo é um arco com extremidades
para algum nó
extremidades
. Na Figura 2.5 tem-se que o arco
o arco
é um laço com extremidades
é um laço com
, etc.
Fig 2.6 Grafo com laço
2.6 ARCOS PARALELOS
Dois arcos com as mesmas extremidades são ditos arcos paralelos; como
exemplo os arcos
e
na Figura 2.5 são paralelos, já os arcos
paralelos.
Fig 2.7 Grafo de cinco nós e seis arcos[1]
e
não são
26
2.7 GRAFOS SIMPLES
Um grafo simples é um grafo que não tem laços nem arcos paralelos. Um
exemplo de grafo simples são todos os grafos da Figura 2.9.
2.8 GRAU DE UM NÓ
O grau de um nó é o número de arcos que incidem naquele nó. Como
exemplo a Figura 2.7, os nós
e o nó
e
têm grau , o nó
tem grau , o nó
tem grau
tem grau .
Como a função
, que associa a cada arco suas extremidades na definição
formal de grafo, é, de fato, uma função, cada arco tem um único par de
extremidades. Se
é uma função injetora, então existe no máximo um arco
associado a cada par de extremidades; tal grafo não tem arcos paralelos, [1].
2.9 GRAFO COMPLETO
Um grafo completo é um grafo no qual dois nós distintos quaisquer são
adjacentes. Nesse caso,
é quase uma função sobrejetora todo par
de nós
distintos é a imagem, sob , de algum arco, mas não há a necessidade de se ter um
laço em cada nó. Portanto, pares da forma
inversa e sim a mesma imagem.
Exemplo 5
podem não ter uma imagem
27
Imagine o grafo do campeonato, [2] (Exemplo 3) quando todos os jogos
tiverem sido jogados. Ele ficaria com o aspecto da Figura 2.8.
Figura 2.8: O grafo do campeonato completo, [2].
Isto é o que chamamos um grafo completo. Um grafo completo é definido
como um grafo onde todo par de vértices é ligado por uma aresta. Um grafo
completo com
vértices é denotado por
(O nosso exemplo é
).
K5
Figura 2.9 Grafos simples e completo[1]
A Figura 2.9 ilustra os grafos simples completos com 1, 2, 3, 4 e
grafo simples completo com
vértices é denotado por
vértices. O
28
Considerando agora o grafo simples da Figura 2.10 abaixo ilustrada, observase que esse grafo não é completo, já que nem todo nó é adjacente a todos os outros
nós.
Figura 2.10 Grafo simples e incompleto, [1]
2.9.1 Grafo Complementar
Temos o grafo do campeonato (Exemplo 3) e se pretende fazer o grafo dos
jogos que faltam. Será feito um grafo com o mesmo conjunto de vértices, mas com
as arestas que faltam no grafo original, [2]. Veja a Figura 2.11
X
Y
Figura 2.11: Grafos complementares, [2]
Denomina-se este grafo de grafo complementar do grafo
quando todas as turmas já jogaram entre si) denotado por
=
( ) e que
,(sendo G o grafo
É fácil perceber que
( ) inclui todas as arestas de , ou seja, com a junção
do grafo X com o grafo Y, teremos um grafo completo como já visto na figura 2.8.
29
2.9.2 Grafo Nulo ou Vazio
Um grafo G é nulo ou vazio quando o conjunto de arestas
é vazio. Por
exemplo, antes de começar o campeonato nenhum jogo havia sido jogado, [2]. O
grafo ficaria como na Figura 2.12:
Figura 2.12: Grafo nulo ou vazio, [2]
2.10 SUBGRAFO
Um subgrafo de um grafo consiste em um conjunto de nós e um conjunto de
arcos que são subconjuntos do conjunto original de nós e arcos, respectivamente,
nos quais as extremidades de um arco têm que ser os mesmos nós que o grafo
original. Em outras palavras, um subgrafo é um grafo obtido apagando-se de parte
do grafo original e deixando o resto sem modificações. A Figura 2.13 mostra os
grafos Y e W como dois subgrafos do grafo X.
X
W
Y
Fig 2.13 Subgrafo, [1]
30
Exemplo 6 (Exemplo de subgrafo)
é dito um subgrafo de
seguir, o grafo
é um subgrafo de
subconjunto
de
em
se
Na figura a
. O grafo
é dito um subgrafo induzido pelo
, pois todas as arestas incidentes aos vértices de
estão presentes em
(veja a Figura 2.14).
Figura 2.14 Subgrafo induzido
2.11 CAMINHO
Um caminho do nó
,
,
,...
do arco
,
são
0
,
para o nó
é uma seqüência
. de nós e arcos onde, para cada , as extremidades
.
No grafo da Figura 2.15 um caminho do nó
seqüência
,
, ,
, 3,
para o nó
, .
Figura 2.15Grafo de quatro nós e quatro arcos,
Figura 2.7 grafos simples completos
consiste na
31
No grafo da figura 2.6, um caminho do nó 2 ao nó 3 consiste na seqüência 2,
, 4,
, 4,
, 6,
, 6,
, 3.
2.12 COMPRIMENTO DE UM CAMINHO
O comprimento de um caminho é o número de arcos que ele contém. Se um
arco for usado mais de uma vez, ele é contado cada vez que é usado.
Na Figura 2.16, o comprimento do caminho do nó 6 para o nó 5 é 2, e o
comprimento da caminho do nó 4 para o nó 2 é 4.
Figura 2.16 comprimento de um caminho
2.12.1 Caminho Simples, Trilha.
Um caminho
é chamado de caminho simples se todos os seus vértices são
distintos, [4]. Uma trilha é um caminho onde todas as arestas são distintas, como na
Figura 2.17
32
Figura 2.17 Caminho: simples e trilha, [4]
Na Figura 2.17 temos o caminho simples
vértices são distintos, e a trilha
repete, porém, alguns vértices como
(esquerda) onde todos os
(à direita) onde nenhuma aresta se
e , se repetem.
2.13 GRAFO CONEXO
Um grafo é conexo se existe um caminho, ligando ou unindo, de qualquer nó
para qualquer outro. Cada um dos grafos na Figura 2.13 é conexo, mas o grafo da
Figura 2.2 não é, pois não existe, por exemplo, nenhum caminho ligando o nó 4 ao
nó 5..
Outra forma de definir a conexidade é observar que um grafo
e só se, existe um caminho entre quaisquer dois vértices de .
A figura 2.18 mostra um grafo ou dois grafos? Depende da situação.
Figura 2.18 Um ou dois grafos? [2]
é conexo se,
33
Em princípio parecem dois grafos distintos, e podemos considerá-los assim.
Mas podemos pensar que esse grafo representa as ligações entre casas de uma
cidade onde passa um rio, [2].
R3
R1
r
r
r
r
R2
r
Figura 2.19 Conexidade[2]
r
r
Se as pontes forem destruídas em umr temporal a cidade ainda é uma só,
apenas foi desconectada. O grafo da Figura r2.18 poderia ser o que se chama de
grafo desconexo. Essa é uma noção importante e volta-se a ela algumas vezes.
Cada parte conexa do grafo (no exemplo o ”quadrado“ e o ”triângulo“) é chamada de
componente conexa do grafo. Tem-se que um grafo é conexo se qualquer par de
pontos é ligado por ao menos um caminho e todo grafo conexo divide o plano em
certo número de regiões, como pode ser vista na Figura 2.19, R1 ,R2 e R3.
Um modo prático de provar que todo grafo completo é conexo seria o de
verificar que em um grafo completo, dois nós distintos quaisquer são adjacentes, de
modo que existe um caminho de comprimento 1 de um nó qualquer para qualquer
outro; portanto o grafo é conexo, [2].
Para demonstrar um grafo conexo que não é completo, utiliza-se a Figura
2.13b
2.15 CICLO
Um ciclo em um grafo é um caminho que começa e termina no mesmo vértice
, tal que nenhum arco ou vértice aparece mais de uma vez no caminho, exceto
Um grafo acíclico é um grafo sem ciclos[4].
.
34
Por exemplo, no grafo da Figura 2.20 temos dois ciclos: um formado pelo
arco
(começando e terminando no vértice
e
) e outro formado pelos arcos
(começando e terminando no vértice ). Similarmente pode-se ter
outros ciclos começando e terminando nos vértices
do grafo. Quando um
grafo é sem ciclos chama-se de grafo acíclico.
Figura 2.20 Ciclo, [4]
Para provar que todo grafo acílico é simples demonstraremos por uma
contraposição, isto é: Se um grafo não for simples, ele tem arcos paralelos ou um
laço. Então os dois arcos paralelos e suas extremidades, ou laço, formam um ciclo e
o grafo então não é acílico.
2.15.1 REVISÃO DOS CONCEITOS VISTOS
No seguinte exemplo revisaremos todos os conceitos estudados até agora.
Considere-se o grafo da Figura 2.21
Figura 2.21 Um dos possíveis grafos da revisão[1]
35
Neste grafo observa-se que:
, é o conjunto dos nós,
=
é o conjunto das arestas e
a função
que associa arcos a suas extremidades é a seguinte:
Além disso, observa-se que:
Os nós 2 e 3 não são adjacentes, o nó 5 é adjacente a si mesmo, o arco
um laço, os arcos
e
é
são paralelos, o grau do nó 3 é 3, um caminho de
comprimento 5 é definido por:
2,
Um ciclo é definido por 3,
, 1,
, 4,
, 3,
, 4,
, 3,
e 4.
, 3.
Este grafo não é completo, pois os nós 2 e 3 não são adjacentes.
Este grafo é conexo, pois qualquer par de nós está ligado por algum caminho,
[1].
2.16 GRAFOS EULERIANOS
Um grafo com
comprimento
em
arestas é dito euleriano se existe uma trilha fechada de
; em outras palavras, se podemos percorrer cada aresta só
uma vez partindo de um vértice e a ele retornando. Se o grafo não é euleriano mas
tem uma trilha aberta de comprimento
, ele é dito semi-euleriano. Em outras
palavras, podemos desenhar um grafo euleriano (ou melhor, uma representação
gráfica dele) sem retirar o lápis do papel e retornando ao ponto inicial 5. Num grafo
36
semi-euleriano começamos num ponto e terminamos em outro, como nas Figura
2.22 abaixo.
Figura 2.22 Grafos eulerianos
Na Figura 2.22 acima, G1 é euleriano (a trilha pode ser a-b-c-d-e-f-a-d-b-e-a),
G2 é semi-euleriano (a trilha pode ser a-e-b-d-c-b-a-d-e) e G3 não é euleriano, nem
semi-euleriano. O problema (e o nome ”euleriano”) se originou com o problema das
pontes de Königsberg, explanaremos melhor as condições necessárias para um
grafo euleriano no capítulo 3.
Teorema de Euler (Euler - 1736). Um grafo conexo (não necessariamente
simples) G é euleriano se e somente se todos os seus vértices tem grau par.
Corolário. Um grafo conexo (não necessariamente simples) G é semi-euleriano
se, e somente se, no máximo, dois vértices têm grau ímpar[2].
2.17. TEOREMA SOBRE OS NÓS IMPARES DE UM GRAFO
O número de nós ímpares em qualquer grafo é par.
Para essa discussão vamos supor que todos os grafos são conexos. Já que,
caso contrario, um caminho de Euler não pode existir. A existência de um caminho
de Euler em um determinado grafo depende dos graus de seus nós. Um nó é par se
tem grau par e é ímpar. Acontece que todo grafo tem um numero par de nós
ímpares. Para ver isso, escolha qualquer grafo e seja
são ímpares,
o número de nós de grau1
o número de seus nós que
37
o número de nós de grau 2,
e assim por diante. Então a soma
de todos os graus de todos os nós do grafo é:
equação 1
Para algum
Essa soma é, de fato, uma contagem do número total de
extremidades de arco no grafo. Como o número de extremidades de arco é o dobro
do número de arcos,
é um número par. vamos reorganizar a equação (1),
agrupando as parcelas correspondentes aos nós ímpares e as correspondentes aos
pares:
nós pares
nós ímpares
A soma das parcelas que representam os nós pares é um número par. Subtraindo
essa quantidade de ambos os lados da equação, obtemos uma nova equação
equação 2
onde
(a diferença entre dois números pares ) é um número par. Reescrevendo a
equação (2) na forma:
+
parcelas
(3) parcelas
38
+(2n+1) + (2n+1)+...+ (2n+1)
parcelas
Vê-se que essa soma tem N parcelas ao todo (o número de nós ímpares) e
que cada parcela é um número ímpar. Para que soma de N números ímpares seja
par é preciso que N seja par. (você pode provar isso?) acabamos, então, de provar o
teorema a cima, [1].
2.18 TEOREMA SOBRE CAMINHOS DE EULER
Existe um caminho de Euler em um grafo conexo se, e somente se, não
existem nós ímpares ou existem exatamente dois nós ímpares. No caso em que não
existem nós ímpares, o caminho pode terminar em qualquer nó e terminar aí; no
caso de dois nós ímpares, o caminho precisa começar em um deles e terminar no
outro.
Suponha, agora, que um grafo tem um nó ímpar n de grau 2k+1 e que existe
um caminho de Euler no grafo que não começa em n. Então, para cada arco que
usamos para chegar em n, existe outro arco ainda não usado para sair de n, até que
tenhamos usado os k pares de arcos. A próxima vez que se chegar em n não haverá
nenhum novo arco para sair. Assim, se o caminho não começa em n, ele tem que
terminar em n. O caminho começa em n ou não e, nesse ultimo caso, ele termina em
n, logo o caminho começa ou termina nesse nó ímpar arbitrário. Portanto, se existem
mais de dois nós ímpares no grafo, não pode existir um caminho. Existem, então,
dois casos possíveis onde um caminho de Euler pode existir em um grafo sem nós
ímpares ou com dois nós ímpares.
Considere o grafo sem nós ímpares. Pegue qualquer nó m e comece um
caminho de Euler. Quando entrar em um nó diferente, sempre vai ter um outro arco
para sair até chegar de volta a m. se tiver usado todos os arcos do grafo, acabou.
Senão existe algum nó m’ de seu caminho com arcos que não foram usados.
39
Construa, então, um caminho de Euler que começa e termina em m’ de maneira
análoga à anterior usando todos os novos arcos. n esse ciclo pode ser adicionado
ao caminho original como uma volta extra. Se tiver usado agora todos os arcos,
acabou. Senão, continue esse processo até usar todos os arcos.
Se existem exatamente dois nós ímpares, pode-se começar um caminho de Euler
em um deles e terminar em outro. Se o caminho não passou por todos os arcos,
pode-se adicionar ciclos extras como no caso anterior.
Temos, agora, a solução completa do problema do caminho de Euler, [1].
2.19 GRAFOS PLANARES
Um grafo planar é um grafo que pode ser representado (em uma folha de
papel, isto é, em um plano) de modo que seus arcos se intersectam apenas em nós.
Os grafos da Figura 2.23 são planares.
Figura 2.23 Grafos planares, [1]
O matemático suíço do século XVIII Leonard Euler (que se lê “oiler”)
descobriu um fato sobre grafos planares. Um grafo simples planar (quando
desenhado em uma representação planar, sem cruzamento de arcos) divide o plano
em um determinado número de regiões, incluindo regiões totalmente limitadas por
arcos e uma região exterior ilimitada. Euler observou uma relação entre o número
de nós e o número
de arcos e o número
de regiões em um tal grafo e essa
relação ficou conhecida como a fórmula de Euler:
40
Verifique a fórmula de Euler para o grafo planar simples e conexo na figura
2.24
Figura 2.24 Grafo planar simples e conexo[1]
Teorema de Euler. Num grafo planar conexo vale
–
Onde
ou
é o número de nós ou vértice,
as arestas e
as faces. Para provar
a fórmula de Euler, vamos fazer uma demonstração por indução no número de arcos
. A base da indução é o caso a = 0, quando temos apenas um nó; a única região é
a região externa (Figura 2.25 a) neste exemplo
e
, logo a
equação (1) é válida.suponhamos agora que a fórmula é válida para uma
representação planar de qualquer grafo planar simples e conexo com
considere um tal grafo com
“caso
arcos e
Como de hábito precisamos relacionar esse
” ao “caso ” de modo a usar a hipótese de indução. Vamos considerar
dois casos para o grafo
arcos[1].
Figura 2.25 Grafo Conexo[1]
41
Caso 1. O grafo tem um nó de grau . Apague, temporariamente, esse nó e o arco
do qual ele é uma das extremidades (Figura 2.25 b); isso nos deixa um grafo planar
simples e conexo com
número de
arcos, e um determinado números
de nós e algum
de regiões tal que pela hipótese de indução
No grafo original temos um arco a mais, um nó a mais e o mesmo número de
regiões , logo a fórmula apropriada é ;
Que pela hipótese de indução, é válida
Caso 2. O grafo não tem nó de grau
.Então apague, temporariamente, um arco
que ajuda a definir uma região limitada ( Figura 2.25 c). e assim temos um grafo
simples e conexo com
arcos, algum número
de nós e um número
de regiões
tal que pela hipótese de indução
No grafo original, tínhamos um arco a mais e uma região a mais, mas o mesmo
número de nós, logo a fórmula apropriada é:
Que é válida pela hipótese de indução.
Na demonstração da fórmula de Euler, explicaremos por que, no caso
o
arco a ser apagado tem que ajudar a definir uma região limitada, [1].
Resposta:
Sem essa condição sobre os arcos, poderíamos obter uma Figura 2.26 como
a que segue então o grafo seria quebrado em dois subgrafos desconexos e a
hipótese de indução não se aplicaria. Além disso, o número de regiões não mudaria.
42
Figura 2.26 Região limitada[1]
A fórmula de Euler tem duas conseqüências se forem colocadas outras
restrições sobre o grafo. Suponha que o grafo não é só planar, simples e conexo,
mas também tem, pelo menos, três nós. Em uma representação planar de um grafo,
pode-se contar o número de arcos que são adjacentes a cada região (formam a
fronteira de cada região ), incluindo a região externa . Arcos inteiramente no interior
de uma região contribuem duas arestas para aquela região; por exemplo, o percorrer
a fronteira da região interior ilustrada na Figura 2.26b, percorremos seis arestas,
incluindo o arco que sai do nó de grau
e depois o mesmo arco de volta. Arcos que
separam duas regiões contribuem uma aresta para cada região. Portanto, se o grafo
tem
arcos, o número de arestas das regiões é
Não existem regiões com exatamente uma aresta adjacente, já que o grafo
não tem laços. Não existem regiões com exatamente duas arestas adjacentes, já
que não há arestas paralelas, e o grafo consistido inteiramente em um arco unindo
dois nós ( que teria duas arestas adjacentes à região exterior ) está excluído.
Portanto, cada região
tem pelo menos três arestas adjacentes, logo
é o número
mínimo de aresta de regiões. Logo,
, ou da equação (1) temos,
–
–
e finalmente,
Se colocarmos uma última restrição sobre o grafo, de que não existem ciclos
de comprimento , então cada região terá, pelo menos, quatro arestas adjacentes,
de modo que
desigualdade,
que fica,
será o número mínimo de arestas das regiões. Isso nos leva à
43
Esses resultados estão resumidos no teorema a seguir.
Teorema sobre o número de
nós e a arcos.
Para um grafo planar simples e conexo com
nós e a arcos.
1. Se a representação planar divide o plano em r regiões, então
2.
, então
–
3. Se
e se não existem ciclos de comprimento , então
Note que a desigualdade (3) coloca uma limitação mais estrita sobre o
número de arcos do que a desigualdade (2),mas foi colocada uma condição
adicional sobre o grafo.
Podemos usar esse teorema para provar que certos grafos não são planares.
Exemplo 7
é um grafo simples e conexo com
nós ( e 10 arcos). Se fosse um grafo
planar, a desigualdade (2) do nosso teorema seria válida, mas
como o nosso argumento construtivo indicou,
Logo,
não é planar.
Mostre que a desigualdade (2) é válida para
o que mostra que essa
desigualdade é uma condição necessária, mas não suficiente, para um grafo com
ser planar, [1].
3 BREVE HISTÓRICO E EXEMPLOS DE APLICAÇÕES
Este capítulo trata de uma síntese de como surgiu a teoria dos grafos, seus
exemplos e suas aplicações. Trata, também, sobre a biografia de Leonhard Euler e a
teoria das sete pontes, como o mesmo provou que não seria possível atravessar as
44
pontes sem passar mais de uma vez por cada uma; dando-se inicio, assim, a teoria
dos grafos.
3.1 BIOGRAFIA DE LEONHARD EULER
Leonhard Euler (1707-1783) o matemático mais produtivo do mundo
Leonhard Euler nasceu na Basiléia, norte da Suíça em 15 de abril de 1707,
seu pai era um pastor protestante Calvinista chamado de Paul Euler, e sua mãe
chama-se Margarete Brucker, sendo seu pai homem de poucos recursos, o mesmo
inicialmente foi educado pelo próprio pai.
Aos treze anos de idade ingressou na universidade de Basiléia aonde logo
iria tornasse o discípulo predileto de
desta forma Euler
mais do que rapidamente tornou-se o que o mestre veio chamar de “incomparável
príncipe da Matemática”. Aos 19 anos foi para a Rússia onde conheceu sua mulher,
Katharina, que também era Suíça juntos tiveram 13 filhos, dos quais morreram oito
na infância. Uma das frases celebre de Euler foi, “A melhor parte da minha obra foi
escrita com uma criança no colo”.
Euler não se contentou apenas em descobrir equações ou em
demonstrar novos teoremas, procurou por sua vez pesquisar sobre os trabalhos de
seus antecessores como; Newton, Descarte e Leibniz. Trabalhou a maior parte de
sua vida na academia de ciência de São Petersburgo na Rússia, onde realizou
metade dos seus escritos, pois o restante foi terminado quando ficou completamente
cego aos 59 anos, com ajuda de alguns assistentes.
Das inúmeras obras deste matemático se pode citar, os problemas
envolvendo trigonometria, os mesmos já existiam dede a época de Cristo e em pleno
século 18 ainda eram resolvidos usando de réguas e compasso sendo este um
processo muito lento e um tanto quanto complicado foi ai que Euler desenvolveu
uma forma de resolução usando somente números, através dos conceitos de seno,
cosseno, tangente e outros, também tornou mais simples o calculo de integral e
45
diferencial. Após sua morte as gráficas da época levaram meio século para publicar
todos os manuscritos ainda inéditos deixados por ele, [6].
3.2 EULER E AS PONTES DE KÖNIGSBERG.
Euler ainda ajudou a criar um novo ramo totalmente inédito da matemática, a
topologia, que para ficar mais fácil de entender será utilizado o exemplos das sete
pontes de Königsberg.
O desafio era saber se era possível entrar e sair dessa cidade situada numa
ilha, atravessando apenas uma vez todas as sete pontes que ela tinha. Euler
mostrou que era impossível, dando inicio ao raciocínio topológico, que é o marco da
teoria dos grafos, objeto de estudo neste trabalho, “percurso Euleriano”.
A contribuição de Euler no desafio acima foi a seguinte, demonstrou que o
problema não tinha solução. Generalizando o resultado e enunciando o seu teorema
em três regras: se há mais de duas áreas às quais leva um número ímpar de pontes,
então tal entrada e saída é impossível, (este era o caso de Königsberg). Se,
entretanto, o numero de pontes for ímpar para exatamente duas áreas, então é
possível se começar em qualquer dessas áreas. Se, finalmente, não existem áreas
às quais levam um número ímpar de pontes, então a jornada requerida pode ser
realizada iniciando-a a partir de qualquer área.
De maneira simplificada pode-se falar que uma rota do tipo especificado
acima (conhecida como um percurso Euleriano) é possível se e somente se o
número de áreas servidas por um número ímpar de pontes é 0 ou 2. Königsberg
tinha quatro áreas servidas por cinco três e três pontes respectivamente, de modo
que nenhum percurso Euleriano era possível. Porem como a guerra destruiu varias
pontes, com a reconstrução e construção de uma nova ponte o problema foi
modificado, mas a solução global de Euler se manteve e este passou a apresentar
um percurso Euleriano. Na conclusão de seu artigo Euler mostrou como após ter
sido estabelecida a existência de uma solução, a rota pode ser determinada, [6].
46
3.3 CIDADE DE KÖNIGSBERG
Figura 3.1 Cidade de Königsberg[1]
Vejamos agora o problema das sete pontes com a ajuda da Figura 3.2.
Imaginemos um rio com duas margens
e
No rio, duas ilhas
e
. A ilha
está
ligada a cada uma das margens por duas pontes. Em cada margem há também uma
ponte para a ilha
. A sétima ponte liga as ilhas entre si.
C
A
D
B
Figura 3.2 O problema das sete pontes
O problema consiste em achar um caminho, ao longo do qual um pedestre,
partindo de uma das margens ou de qualquer das ilhas percorra todas as pontes,
sem passar mais de uma vez por qualquer uma delas.
47
Euler fez a observação fundamental que, para efeito da questão proposta, as
margens e as ilhas são como se fossem pontos
. As pontes são como arcos
que tem esses pontos como extremidades.
Tudo se resume a analisar a Figura 3.3, onde os arcos ligam os pontos, de acordo
com a disposição das pontes dada no enunciado do problema, [7].
C
A
3.3 a
C
D
A
B
B
3.3 b
3.3 b
Figura 3.3 (a) e (b) Primeiro esboço de um grafo
A distancia entre as pontes, e o comprimento de cada uma, e o quanto se
anda não tem importância na solução do problema. Por isso, o grafo da Figura 3.2
sintetiza toda a informação relevante. O desenho da Figura 3.3, é provavelmente, o
primeiro esboço de um grafo a ocorrer como modelo matemático para resolver um
problema, que agora se exprime assim: partindo de um dos vértices
ou
achar um caminho que percorra todo o grafo sem passar mais de uma vez pelo o
mesmo arco.
De modo geral um grafo é isso: um conjunto finito de pontos, chamado de
vértices do grafo, e um conjunto finito de arcos, chamado de arestas do grafo. As
extremidades de cada aresta devem ser vértices. Além disso, duas arestas
quaisquer do grafo não podem ter pontos interiores em comum, ou são disjuntas ou
se tocam apenas numa ou em duas extremidades.
Euler chamou atenção para uma noção muito simples, porém crucial, que é a
ordem de um vértice do grafo. A ordem de um vértice é o número de arcos que
emanam deles. Euler observou que toda vez que um caminho unicursal (percurso
Euleriano) chega a um vértice, deve sair dele por um arco diferente daquele por
onde chegou (a menos que esse vértice seja o fim do caminho); portanto para
48
conseguir passar por todas as sete pontes sem passar mais de uma vez pelo
mesmo caminho, os vértices desse grafo devem ser todos com arestas par, com
exceção ao início e ao fim do caminho. Se o início e o fim do caminho coincidirem
(isto é, se o caminho for fechado), então todos os vértices do grafo, sem exceção,
tem ordem par, como mostrado na Figura 2.22 G1.
Conclui-se então que se um grafo é unicursal (Euleriano), ou todos os seus
vértices têm ordem par (caminho unicursal fechado) ou exatamente dois vértices têm
ordem impar (caminho unicursal), deve começar em um vértice de ordem impar e
terminar em outro.
Segue então que o esboço do grafo da Figura 3.3 das pontes de Königsberg
não é Euleriano, pois, seus quatro vértices têm ordem impar, o vértice
enquanto os demais vértices
e
tem ordem
tem todos ordem . A solução encontrada
para o problema das pontes e a fórmula relacionando o número de faces, vértices e
arestas de um poliedro
foram contribuições importantes de Euler à
um campo da matemática chamado de topologia.
Fica então resolvido o problema das sete pontes: é impossível percorrê-las todas,
sem passar duas vezes pela mesma ponte, [7].
4 ALGUNS PROBLEMAS CLÁSSICOS SOBRE GRAFOS
Este capítulo formaliza o conceito de grafo e examina vários exemplos.
Também faz uma breve lista de problemas célebres sobre grafos, alguns dos quais
já mencionamos nos capítulos anteriores.
4.1 PROBLEMA DA CASINHA
Na introdução, a pergunta foi se você conseguiria desenhar a casinha abaixo
sem tirar o lápis do papel. A Figura mostra uma solução e, na verdade, o problema é
bastante fácil, [2].
49
Figura 4.1 Resolução do problema da casinha[2]
Mas se a pretensão for começar pelo vértice B? (você pode tentar o tempo
que quiser). O fato é que esse outro problema é impossível. Todas as soluções
começam / terminam pelo vértice
. Se começam em
terminam em
, e vice-
versa. Agora que já se tema a definição de um percurso euleriano fica fácil de
verificar que esse grafo tem um percurso semi euleriano, pois, tem 2 vértices com
arestas impares (condição necessária para grafo semi-euleriano) e 3 vértice com
arestas par e obrigatoriamente ele se inicia em um ponto e termina em outro.
4.2 O PROBLEMA DO GÁS,LUZ E TELEFONE.
Outro problema que se propõe às crianças para que se aquietem é o
seguinte: temos que ligar Luz, Gás e Telefone a três casas sem que as linhas se
cruzem (supondo que todas as ligações, fios e canos estejam situados em um
mesmo plano).
Figura 4.2 O problema do gáz, luz e telefone[2]
50
Para esse problema podem ser utilizadas duas teorias dos grafos já vistas
anteriormente para se chegar a uma conclusão:
A primeira é chegar a uma resposta por meio de uma aplicação da Fórmula de Euler
, Onde
é o número de nós ou vértice,
o número das arestas e
o número de regiões.
A situação pode ser representada geometricamente como segue na Figura 4.3:
C1
C2
C3
T
G
L
Figura 4.3 Situação representada geometricamente
O problema é verificar se o grafo de vértices C1 , C2 e C3, T, G, L e arestas
AC1 , AC2, AC3 , LC1, LC2, LC3, TC1, TC2 e TC3 é ou não grafo planar.
Suponhamos que ele seja planar. Pela fórmula de Euler, devemos então, ter:
Onde
, logo
, portanto
, ou seja, devemos ter 5
regiões do plano determinadas pelo grafo. Assim, como uma destas regiões é
ilimitada, deve-se ter exatamente 4 regiões limitadas por aresta do grafo como se vê
na Figura 4.4 (a), (b) e (c) demonstrada abaixo[5].
L
Figura 4.4 a
R1
R2
C2
C1
T
C3
51
L
C2
R1
C3
R2
Figura 4.4 b
C1
G
T
R1
R2
C2
C3
Figura 4.4 c
C1
G
Figura 4.4 (a), (b), (c) Grafos com duas regiões limitadas
Assim, tem-se pelo menos 6 regiões limitadas por arestas do grafo, o que
viola a fórmula de Euler. Logo, o grafo não pode ser planar.
A segunda forma de se verificar a impossibilidade das ligações serem feitas é
fazendo um grafo da situação problema, que ficaria assim como na Figura 4.5:
Figura 4.5 o grafo do gás, luz e telefone
52
De acordo com esse grafo, observa-se uma das possibilidades para que as
ligações ocorram, e como foi demonstrado em grafos planares seus arcos se
intersectam apenas em nós e não em arestas, e como pode ser visto na Figura 4.5
acima as arestas estão se intersectando fica claro a demonstração de
impossibilidade.
4.3 O PROBLEMA DO TRAJETO DA TRANSPORTADORA
O grafo a seguir Figura 4.6 representa as estradas ligando 5 cidades
diferentes. As distancias são todas em quilômetros. Uma transportadora deseja sair
de
passando por todas as cidades e retornando a , de maneira que o trajeto seja
o mais curto possível[3].
Figura 4.6 O grafo do trajeto[3]
É possível fazer um trajeto saindo de
, passando por todas as arestas uma
única vez, e retornado ao ponto de partida ?
Tente obter um trajeto para a transportadora saindo e retornando a , passando por
todas as outras cidades, de modo que a distancia percorrida seja a menor possível.
53
Resolução: De acordo com o que vimos de grafo até o presente momento fica fácil
afirmar que tal trajeto é impossível, esse grafo não é euleriano, ou seja, todos seus
vértices têm arestas impares, tornando o trajeto impossível.
4.4 O PROBLEMA DO RECOLHIMENTO DE LIXO.
Pense numa pequena cidade com um é único caminhão para recolher o lixo
onde o prefeito deseja economizar, o que significa que ele prefere que o caminhão
passe uma única vez por todas as ruas e retorne ao ponto de partida. A cidade que
foi desenhada em grafos fica idêntica ao problema da casinha e, se a cidade tivesse
essa configuração, não teria solução (pois o caminhão não retornaria ao ponto inicial
(como já foi demonstrado no problema da casinha) e mais uma vez na Figura 4.7,
[2].
Figura 4.7 O problema do recolhimento de lixo[2]
Se o mapa da cidade fosse como à figura a seguir, o prefeito ficaria contente
(experimente desenhar esta figura sem tirar o lápis do papel, mas voltando ao ponto
inicial), como na Figura 4.8 representada abaixo.
54
Figura 4.8 Resolução para o recolhimento de lixo
Vamos fazer algumas contas. Temos 8 arestas disponíveis e podemos
numerá-las de 1 a 8. Podemos pensar num procedimento que verifique se uma
determinada seqüência de 8 algarismos do tipo
(1, 2, 3, 4, 5, 6, 7, 8) ou (3, 5, 6, 2, 8, 4, 7, 1)
é ou não uma solução para o problema da casinha. Melhor ainda, essas seqüências
podem ser colocadas em ordem de
(1, 2, 3, 4, 5, 6, 7, 8) até (8, 7, 6, 5, 4, 3, 2, 1).
Quantas seqüência teremos? Pelo método de permutação podemos afirmar que
teremos
8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40320 seqüência.
São as permutações de 8 elementos. Ora, um bom computador pode gerar e
verificar essas seqüências todas em segundos. E isso se chama uma “solução por
forca bruta” e não foi utilizada nenhuma sofisticação matemática, mas lembre-se do
prefeito. Pense-se que a cidade dele não tenha 8 ruas, mas 20. Não é uma grande
cidade e pode-se tentar usar a mesma força bruta do computador para resolver o
problema de percorrer com o caminhão sem repetição de ruas. Se existem 20 ruas,
ter-se-à 20! seqüência. Quanto é isso? 20! = 2432902008176640000 seqüência
São muitas seqüência. Mas será que um bom computador não resolveria este
55
problema? Se o computador verificasse um milhão de seqüência por segundo (e
poucos computadores o fazem hoje em dia) ele demoraria (os cálculos só incluem a
parte inteira):
O prefeito não pode esperar tanto tempo ( ninguém pode esperar). Quem
prestará socorro? Um teorema de Euler, que já foi demonstrado em grafos
eulerianos capítulo 2.16, que garante que esse grafo pode ser percorrido, pois, seus
6 vértices tem arestas par,[2].
4.5 O PROBLEMA DO CAIXEIRO VIAJANTE
Um vendedor ambulante deve visitar
cidades, uma única vez cada uma, e
retornar à cidade de origem. O custo pode ser medido em termos de tempo, dinheiro
etc., e as opções existentes para as diferentes etapas de viagens correspondem às
arestas do grafo abaixo da Figura 4.9 O objetivo é saber se existe tal percurso.
56
O modelo: um grafo, completo de
vértices
Figura 4.9 Caixeiro viajante
Como resolver o problema?
Primeiro como no problema anterior por exaustão: enumerar todas as rotas
possíveis e calcular a distância percorrida em cada uma delas
Número de rotas = (n –1)!
n = 5 cidades => 4! = 24 rotas
n = 20 cidades => 19! = 107 rotas
n = 50 cidades => 49! => ?
O segundo seria usarmos o teorema de Euler: Existe um circuito euleriano em
um grafo se e somente se o grafo é conexo (isto é, existe um caminho ligando
qualquer par de vértices) e cada vértice tem grau par (ou seja, o número de arcos
que nele incidem é par).Portanto já se pode perceber que esse grafo é conexo pois
existe um caminho ligando qualquer par de vértices e seus vértices tem grau par e
se ele é conexo logo é euleriano, portanto é possível sair de uma cidade e passar
por todas as outras e retornar ao nosso ponto de partida, [7].
57
4.6 CASAMENTO TOPOLOGICAMENTE IMPEDIDO
Problemas topológicos vêm desafiando matemáticos e leigos desde a
antiguidade, conta-se que um Califa Percio utilizou um desses problemas para
desencorajar os pretendentes de suas filhas.
A bela princesa só se casaria com o homem que conseguisse reunir esses
seis pontos correspondentes dois á dois com três linhas que não se cruzem, como
mostra a Figura 4.10.
11
33
22
222
33
111
Figura 4.10 Califa pércio
É provável que essa princesa jamais tenha se casado, porque esse problema
da Figura 4.8, parece fácil mas não tem solução, pode tentar!
Se o califa achasse que as filhas fossem casadouras, ele poderia manter
1,2,3 e 1,2,3, como na Figura 4.11. E embora não podendo passar no interior da
figura os pretendentes poderia fazer assim :
58
1
1
2
2
3
3
Figura 4.11 Filhas casadouras
Mas veja o que fez o califa na Figura 4.12, inverteu a ordem, isto é, o califa
topologicamente impediu o casamento das filhas, [8].
1
3
2
2
3
1
Figura 4.12 Casamento topologicamente impedido
impedida
59
4.7 GRAFO EULERIANO
Dentre os grafos abaixo Figura 4.13 descubra quais podem ser percorridos,
sem que se passe mais de uma vez sobre a mesma aresta[3]:
Figura 4.13 Percurssos eulerianos
Fica a cargo do leitor realizar esta tarefa.
4.8 ENCONTRE UM CAMINHO EULERIANO
Um caminho de Euler em um grafo G, é um caminho que usa cada arco em G
exatamente uma vez. Existem caminhos de Euler para um dos grafos na Figura
4.14(use tentativas e erros pra responder. Essa é a velha brincadeira de criança, se
é possível desenhar todo o grafo sem levantar o lápis do papel e sem desenhar duas
vezes qualquer arco.), [1]
60
Figura 4.14 Caminhos eulerianos
Mais uma tarefa que o leitor deve realizar.
61
5 CONSIDERAÇÕES FINAIS
Chega-se ao tópico final deste TCC, entendendo, no mínimo, que nos vários
setores do caminhar da humanidade encontra-se a figura dos grafos; sendo sua
existência de vital importância para que diversos problemas sejam resolvidos,
interferindo nos mais variados ramos da ciência, como na estrutura molecular, na
construção de redes de computadores (ciência da Computação), na topologia
(matemática).
Apesar das diversas dificuldades encontradas, tais como: bibliografia,
conhecimento limitado na área da computação e na matemática descritiva, os
signatários deste elaboraram e apresentaram as definições, exemplos e casos onde
foi provada a necessidade dos Grafos fora do ramo da computação, através de seus
conceitos, suas espécies, seus exemplos e suas análises.
Com a finalidade de apresentar um trabalho o mais completo possível,
procurou-se traçar uma linha desde o descobrimento dos Grafos, seu paralelismo,
definições, e tudo o mais que esclarecesse e elucidasse quaisquer dúvidas acerca
do assunto dentro do campo da matemática, visando e buscando, dentro do que foi
permitido, entender e fazer entender o verdadeiro significado da palavra Grafo.
Espera-se que o objetivo tenha sido atingido e que os estudiosos da matéria,
bem como qualquer pessoa que algum dia leia este trabalho, compreendam e sejam
esclarecido acerca do assunto, tão sabiamente desenvolvido pelo matemático
Leonhard Euler – os Grafos.
O tema, entretanto, não foi esgotado, ficando, assim, aberto o campo para
futuramente estender-se esta pesquisa em programações e simulações dentro ou
fora da ciência da matemática.
62
BIBLIOGRAFIA
GERSTING,J.L.Grafos e árvores. In: GERSTING,J.L.Fundamentos Matemáticos
para a Ciência da Computação.4.ed.New York:LTC,1999.p.229-284.
JURKIEWICZ, Samuel. Grafos –Uma Introdução.Disponível em:
< http://arquivosevt.lncc.br/pdfs/Apostila5-Grafos.pdf> Acesso em: 20, ago,2009.
CARVALHO,A.L.Tde;REIS,L.F.MatemáticaInterativa.Tatuí:CasaPublicadora
Brasileira, 2002.271p.
VERA, Ausberto.S.C.Grafos.2009.Notas de aula da disciplina lógica e matemática
discreta proferida no UNASP.
PITOMBEIRA, J.B. O problema das ligações de água luz e telefone: uma
aplicação da fórmula de Euler. Revista do Professor de Matemática, São
Paulo,v.11,1987, p09-16, out. 2009.
PENHA, Guilherme .M La. Euler e a topologia. Revista do Professor de
Matemática,São Paulo,v.3,1983,p12-14, out. 2009.
LIMA, E.L. Alguns problemas clássicos sobre grafos. Revista do Professor de
Matemática, São Paulo,v.12,1988, p36-42, out. 2009.
PIRES, Luciana;CABRAL,Marilda.Forma que se transforma.São Paulo: Video lar,
1 videodisco 25’16’’:laser, estéreo. 21.
Boaventura Netto, P. O, Grafos: Teoria, Modelos, Algoritmos, 2a.ed.São Paulo:
Edgard Blücher,1996.405p.
GERSTING,J.L. Algoritimos para grafos. In:GERSTING,J.L. Fundamentos
Matemáticos para a Ciência da Computação.4.ed.New York:LTC,1999.p.285-328.
63
VIEIRA, B.L. Detecção de paralelismo através de grafos de dependências em filtros
Convolucionais. Maceió, 2007.40f.Trabalho Acadêmico - ciências da computação,
Instituto de Computação da Universidade Federal de Alagoas.
COSTA, S;SEBASTIANE,E. Onde morar?- O problema de minimizar redes de
comunicação. Revista do Professor de Matemática, São Paulo,v.16,1990, p41-46,
out. 2009.
WAGNER, E.Uma resolução mecânica para o problema onde morar. Revista do
Professor de Matemática, São Paulo,v.16,1990, p47-50, out. 2009.
CARNEIRO, V.C. Colorindo mapas.Revista do Professor de Matemática, São
Paulo,v.29,1995, p31-35, out. 2009.
TUNALA,N.Um Procedimento Geométrico para otimização linear no plano.Revista
do Professor de Matemática, São Paulo,v.31,1996, p16-21, out. 2009.
EOFILOFF,Paulo.Exercícios de teoria dos grafos.Disponível em:
< http://www.ime.usp.br/~pf/grafos-exercicios> Acesso em: 15, set,2009.
FEOFILOFF,Paulo.Exercícios de teoria dos grafos.Notas de aula da disciplina
ciência da computação proferida no IME- USP.