Teoria dos grafos

of 7

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
7 pages
0 downs
5 views
Share
Description
Teoria dos grafos
Tags
Transcript
  Prof. Bruno Holanda - Semana Ol´ımpica 2011 -  N´ıvel 1 Teoria dos Grafos O que ´e um grafo?   Se vocˆe nunca ouviu falar nisso antes, esta ´e certamente uma pergunta que vocˆe deveestar se fazendo. Vamos tentar matar sua curiosidade contando como foi que a teoria dos grafos surgiu.Figura 1.1: Mapa de K¨onigsbergA Literatura afirma que a teoria dos grafos come¸cou na cidade de K¨onigsberg em 1736 pelo grandematem´atico su´ı¸co Leonhard Euler (1707-1783). A cidade era cortada pelo rio Pregel, que possu´ıa duas ilhas(figura 1.1). Como era muito complicado fazer o transporte de cargas e pessoas atrav´es de barcos, algumaspontes foram constru´ıdas para auxiliar neste deslocamento entre as ilhas e as duas margens. Ap´os algumtempo as pessoas come¸caram a se perguntar se era poss´ıvel sair de sua casa, passar por cada ponte exata-mente uma vez e voltar para a seguran¸ca de seu lar.Para resolver o problema, Euler montou um diagrama que representasse o mapa da cidade. Ele o fez daseguinte maneira: A cada ilha e margem ele associou a um ponto que chamaremos de  v´ertice   e a cada ponteuma liga¸c˜ao que chamaremos de  aresta  . Com isso, ele obteve a figura 1.2:Essa figura com v´arios pontos (v´ertices) e algumas liga¸c˜oes (arestas) que denominamos um  grafo . Parafinalizar seu racioc´ınio, Euler percebeu que existiam v´ertices com exatamente trˆes arestas incidentes. Poroutro lado, como os moradores queriam atravessar cada ponte apenas uma vez, cada v´ertice deveria ter1  2  Prof. Bruno Holanda Figura 1.2: Diagrama de Eulerum n´umero par arestas. Logo, se tornaria imposs´ıvel fazer um percurso seguindo as regras impostas pelosmoradores. 1.1 Conseitos B´asicos Como em toda teoria matem´atica, a teoria dos grafos est´a repleta de nomeclaturas e termos t´ecnicos. Nestase¸c˜ao vamos aprender algumas defini¸c˜oes importantes para o entendimento completo deste cap´ıtulo. A seguir damos um exemplo de um grafo que representa um mapa de estradas e cidades. ABCDEFG Vamos aproveitar o grafo acima para abordar algumas defini¸c˜oes. Por exemplo, o grafo acima ´e  conexo ,pois ´e poss´ıvel ir de um v´ertice a qualquer outro passando usando algumas de suas arestas. Por exemplo,para ir de  A  at´e  G  basta fazer a seguinte seq¨uˆencia  A  →  C   →  E   →  F   →  G . Dizemos ent˜ao, que estaseq¨uˆencia ´e um  caminho  de  A  at´e  G . Agora, um caminho fechado ´e chamado de  ciclo . Por exemplo, ocaminho  A → B  → E   → A  ´e um ciclo de tamanho 3 (ou seja um  C  3 ). J´a o ciclo  B  → E   → G → F   → B  ´eum  C  4 .Outra nota¸c˜ao muito importante ´e o  grau  . Vamos definir o grau de um v´ertice  v  como a quantidade dearestas que incidem nele. E vamos denotar essa quantidade como  d ( v ). Por exemplo,  d ( A ) = 4,  d ( B ) = 3 e d ( C  ) = 2. Os pr´oximos exerc´ıcios servir˜ao para fixarmos as defini¸c˜oes que acabamos de aprender. Exerc´ıcios: 1. Sabemos que o grafo anterior era conexo. Por´em, existe uma aresta que, se retirada, o grafo passar´a aser  desconexo . Que aresta ´e essa? Explique porque n˜ao pode ser outra.  PROBLEMAS DE TREINAMENTO  3 2. Qual ´e o menor caminho de  D  at´e  C  ? E o maior? (n˜ao se pode repetir arestas)3. Quantos ciclos de tamanho trˆes existem? E de tamanho quatro?4. Determine o ciclo que possui o maior tamanho.5. Qual o v´ertice que tem o maior grau?6. Calcule a soma dos graus de todos os v´ertices do grafo.Vocˆe deve ter notado que o grafo de Euler possui uma particularidade: entre o mesmo par de v´erticesexistem duas arestas que os liga. Por´em, a maioria dos grafos que estudamos s˜ao  grafos simples  . Ou seja,grafos que n˜ao admitem la¸cos (arestas que come¸cam e terminam no mesmo v´ertice) e  arestas m´ ultiplas   (comono grafo de Euler).O pr´oximo problema ´e um dos mais famosos problemas de toda a olimp´ıada de matem´atica. Pode tercerteza que vocˆe ainda vai ouvir falar desse problema muitas vezes. Problema 1.  ´E poss´ıvel que os cavalos da figura 1 fiquem na posi¸c˜ao da figura 2? Figura 1 Figura 2 Solu¸c˜ao.  Vamos enumerar as casas do tabuleiro da seguinte forma: 7 8 94 5 61 2 3 Agora vamos construir um grafo com v´ertices 1 , 2 ,..., 9 onde vamos ligar dois v´ertice  i  e  j  se ´e poss´ıvel ocavalo ir da casa  i  at´e a casa  j  usando apenas um movimento. Dessa forma, obtemos o seguinte grafo:  4  Prof. Bruno Holanda 5 3179862 4 Agora colocamos os cavalos de acordo com os tabuleiros mostrados anteriormente. 5 3179862 45 3179862 4 Dessa forma fica f´acil ver que ´e imposs´ıvel ir de uma configura¸c˜ao a outra, pois a ordem c´ıclica dos cavalos n˜ao pode mudar. 1.2 Grafos SimplesTeorema.  Em um grafo simples   G  = ( V,A ) , a soma dos graus de todos os seus v´ertices ´e igual ao dobro don´ umero de arestas. Ou seja;  v ∈ V   d ( v ) = 2 | A | Prova.  De cada v´ertice  v  partem  d ( v ) arestas. Por´em, cada aresta possui dois v´ertices. Desse modo, sesomarmos os graus de todos os v´ertices obteremos o dobro do n´umero de arestas. Problema 2.  (USAMO 1989) Um torneio de xadrez re´une 20 jogadores. Foram jogadas 14 partidas, comcada jogador jogando pelo menos uma vez. prove que nesse campeonato deve haver um conjunto de 6 jogoscom 12 jogadores diferentes. Solu¸c˜ao.  Vamos montar um grafo  G  com 20 v´ertices a 14 arestas, onde os v´ertices representam os jogadorese as arestas os jogos. Como cada jogador jogou pelo menos uma vez, cada v´ertice do grafo tem pelo menosgrau 1. Agora, usando o teorema temos que a soma dos graus dos v´ertices ´e 28. Da´ı, pelo princ´ıpio da casados pombos, devem existir pelo menos 12 v´ertices com grau exatamente 1. Esses 12 v´ertices representam os  PROBLEMAS DE TREINAMENTO  5 12 jogadores solicitados pelo problema. Problemas Propostos 1. Considere um grupo de 1997 pessoas. ´E poss´ıvel que cada uma delas conhe¸ca exatamente:a) 3 pessoas?b) 4 pessoas?2. Considere um grupo de 1998 pessoas. ´E poss´ıvel que cada uma delas conhe¸ca exatamente 101 pessoasdo grupo?3. Cada um dos 102 estudantes ´e amigo de pelo menos 68 outros alunos. Prove que existem quatroestudantes com o mesmo n´umero de amigos.4. Todos os v´ertices de um grafo tˆem grau 3. Prove que o grafo possui um ciclo.5. Em um conjunto de  n  pessoas, em qualquer grupo de quatro delas existe uma que conhece as outrastrˆes. Prove que existe uma pessoa que conhece todas as outras.6. A figura abaixo representa as liga¸c˜oes rodovi´arias entre 14 cidades. Existe um caminho passando por cada cidade exatamente uma vez?7. Em um conjunto de 2 n  pessoas, cada uma delas possui um n´umero par de amigos. Prove que existemduas pessoas que possuem um n´umero par de amigos em comum.8. (R´usssia 2000) Em um grafo  G  cada v´ertice possui grau pelo menos 3. Prove que nesse grafo h´a umciclo com o n´umero de arestas n˜ao divis´ıvel por 3. 1.3 Grafos Orientados e Torneios 1. Na Bruzundanga, quaisquer duas cidades s˜ao ligadas por uma estrada. Um imperador tirano decidiutransformar todas essas estradas em estradas de m˜ao ´unica de tal forma que se uma pessoa sair de suacidade n˜ao poder´a mais voltar. ´E poss´ıvel fazer tal crueldade?2. (R´ussia 1970) Em um torneio completo de tennis haviam 12 jogadores. Prove que podemos encontrartrˆes jogadores  A ,  B  e  C   tais que  A  ganhou de  B ,  B  ganhou de  C   e  C   ganhou de  A .3. (Torneio das Cidades 1982) Em certo pa´ıs existem mais do que 101 cidades. A capital deste pa´ıs ´econectada por linhas a´ereas a outras 100 cidades, e cada cidade, exceto pela capital, ´e conectada aoutras 10 cidades (se  A  est´a conectado a  B ,  B  est´a conectado a  A ). Al´em disso, todas as linhas a´ereass˜ao de uma ´unica dire¸c˜ao. Sabe-se que de qualquer cidade ´e poss´ıvel chegar a qualquer outra usando essas rotas. Prove que ´e poss´ıvel fechar metade das linhas a´ereas conectadas `a capital, e preservar acapacidade de viajar de uma cidade a qualquer outra.
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks