Scribd Logo
Carregar

Bem-vindo(a) ao Scribd!

  • 89 visualizações

    Nivel1 Grafos Bruno PDF

    Enviado por

    ricampos08
    A teoria dos grafos surgiu em 1736 quando o matemático Leonhard Euler resolveu o problema dos sete pontes de Königsberg ao modelá-lo como um grafo. O documento introduz conceitos básicos de teoria dos grafos como vértices, arestas, grau e caminhos e apresenta problemas envolvendo grafos.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd

    Nivel1 Grafos Bruno PDF

    Enviado por

    ricampos08
    89 visualizações7 páginas
    A teoria dos grafos surgiu em 1736 quando o matemático Leonhard Euler resolveu o problema dos sete pontes de Königsberg ao modelá-lo como um grafo. O documento introduz conceitos básicos de teoria dos grafos como vértices, arestas, grau e caminhos e apresenta problemas envolvendo grafos.

    Título original

    Nivel1_grafos_bruno.pdf

    Direitos autorais

    © © All Rights Reserved

    Formatos disponíveis

    PDF, TXT ou leia online no Scribd

    Você considera este documento útil?

    Este conteúdo é inapropriado?

    A teoria dos grafos surgiu em 1736 quando o matemático Leonhard Euler resolveu o problema dos sete pontes de Königsberg ao modelá-lo como um grafo. O documento introduz conceitos básicos de teoria dos grafos como vértices, arestas, grau e caminhos e apresenta problemas envolvendo grafos.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    89 visualizações7 páginas

    Nivel1 Grafos Bruno PDF

    Enviado por

    ricampos08
    A teoria dos grafos surgiu em 1736 quando o matemático Leonhard Euler resolveu o problema dos sete pontes de Königsberg ao modelá-lo como um grafo. O documento introduz conceitos básicos de teoria dos grafos como vértices, arestas, grau e caminhos e apresenta problemas envolvendo grafos.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    de 7

    Prof.

    Bruno Holanda - Semana Olmpica 2011 - Nvel 1

    Teoria dos Grafos

    O que e um grafo? Se voce nunca ouviu falar nisso antes, esta e certamente uma pergunta que voce deve
    estar se fazendo. Vamos tentar matar sua curiosidade contando como foi que a teoria dos grafos surgiu.

    Figura 1.1: Mapa de Konigsberg


    A Literatura afirma que a teoria dos grafos comecou na cidade de Konigsberg em 1736 pelo grande
    matem
    atico suco Leonhard Euler (1707-1783). A cidade era cortada pelo rio Pregel, que possua duas ilhas
    (figura 1.1). Como era muito complicado fazer o transporte de cargas e pessoas atraves de barcos, algumas
    pontes foram construdas para auxiliar neste deslocamento entre as ilhas e as duas margens. Ap
    os algum
    tempo as pessoas comecaram a se perguntar se era possvel sair de sua casa, passar por cada ponte exatamente uma vez e voltar para a seguranca 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 vertice e a cada ponte
    uma ligacao que chamaremos de aresta. Com isso, ele obteve a figura 1.2:
    Essa figura com varios pontos (vertices) e algumas ligacoes (arestas) que denominamos um grafo. Para
    finalizar seu raciocnio, Euler percebeu que existiam vertices com exatamente tres arestas incidentes. Por
    outro lado, como os moradores queriam atravessar cada ponte apenas uma vez, cada vertice deveria ter
    1

    Prof. Bruno Holanda

    Figura 1.2: Diagrama de Euler


    um n
    umero par arestas. Logo, se tornaria impossvel fazer um percurso seguindo as regras impostas pelos
    moradores.

    1.1

    Conseitos B
    asicos

    Como em toda teoria matem


    atica, a teoria dos grafos esta repleta de nomeclaturas e termos tecnicos. Nesta
    secao vamos aprender algumas definicoes importantes para o entendimento completo deste captulo. A seguir
    damos um exemplo de um grafo que representa um mapa de estradas e cidades.
    F
    D
    A

    C
    B

    Vamos aproveitar o grafo acima para abordar algumas definicoes. Por exemplo, o grafo acima e conexo,
    pois e possvel ir de um vertice a qualquer outro passando usando algumas de suas arestas. Por exemplo,
    para ir de A ate G basta fazer a seguinte seq
    uencia A C E F G. Dizemos entao, que esta
    seq
    uencia e um caminho de A ate G. Agora, um caminho fechado e chamado de ciclo. Por exemplo, o
    caminho A B E A e um ciclo de tamanho 3 (ou seja um C3 ). Ja o ciclo B E G F B e
    um C4 .
    Outra notacao muito importante e o grau. Vamos definir o grau de um vertice v como a quantidade de
    arestas que incidem nele. E vamos denotar essa quantidade como d(v). Por exemplo, d(A) = 4, d(B) = 3 e
    d(C) = 2. Os proximos exerccios servirao para fixarmos as definicoes que acabamos de aprender.
    Exerccios:
    1. Sabemos que o grafo anterior era conexo. Porem, existe uma aresta que, se retirada, o grafo passara a
    ser desconexo. Que aresta e essa? Explique porque nao pode ser outra.

    PROBLEMAS DE TREINAMENTO

    2. Qual e o menor caminho de D ate C? E o maior? (nao se pode repetir arestas)


    3. Quantos ciclos de tamanho tres existem? E de tamanho quatro?
    4. Determine o ciclo que possui o maior tamanho.
    5. Qual o vertice que tem o maior grau?
    6. Calcule a soma dos graus de todos os vertices do grafo.
    Voce deve ter notado que o grafo de Euler possui uma particularidade: entre o mesmo par de vertices
    existem duas arestas que os liga. Porem, a maioria dos grafos que estudamos s
    ao grafos simples. Ou seja,
    grafos que nao admitem lacos (arestas que comecam e terminam no mesmo vertice) e arestas m
    ultiplas (como
    no grafo de Euler).
    O proximo problema e um dos mais famosos problemas de toda a olimpada de matem
    atica. Pode ter
    certeza que voce ainda vai ouvir falar desse problema muitas vezes.
    possvel que os cavalos da figura 1 fiquem na posicao da figura 2?
    Problema 1. E

    Figura 1

    Figura 2

    Soluc
    ao. Vamos enumerar as casas do tabuleiro da seguinte forma:

    Agora vamos construir um grafo com vertices 1, 2, ..., 9 onde vamos ligar dois vertice i e j se e possvel o
    cavalo ir da casa i ate a casa j usando apenas um movimento. Dessa forma, obtemos o seguinte grafo:

    Prof. Bruno Holanda

    4
    1
    6

    4
    9

    Agora colocamos os cavalos de acordo com os tabuleiros mostrados anteriormente.


    1

    4
    9

    Dessa forma fica facil ver que e impossvel ir de uma configuracao a outra, pois a ordem cclica dos cavalos
    nao pode mudar.

    1.2

    Grafos Simples

    Teorema. Em um grafo simples G = (V, A), a soma dos graus de todos os seus vertices e igual ao dobro do
    n
    umero de arestas. Ou seja;
    X
    d(v) = 2 |A|
    vV

    Prova. De cada vertice v partem d(v) arestas. Porem, cada aresta possui dois vertices. Desse modo, se
    somarmos os graus de todos os vertices obteremos o dobro do n
    umero de arestas.
    Problema 2. (USAMO 1989) Um torneio de xadrez re
    une 20 jogadores. Foram jogadas 14 partidas, com
    cada jogador jogando pelo menos uma vez. prove que nesse campeonato deve haver um conjunto de 6 jogos
    com 12 jogadores diferentes.
    Soluc
    ao. Vamos montar um grafo G com 20 vertices a 14 arestas, onde os vertices representam os jogadores
    e as arestas os jogos. Como cada jogador jogou pelo menos uma vez, cada vertice do grafo tem pelo menos
    grau 1. Agora, usando o teorema temos que a soma dos graus dos vertices e 28. Da, pelo princpio da casa
    dos pombos, devem existir pelo menos 12 vertices com grau exatamente 1. Esses 12 vertices representam os

    PROBLEMAS DE TREINAMENTO

    12 jogadores solicitados pelo problema.


    Problemas Propostos
    possvel que cada uma delas conheca exatamente:
    1. Considere um grupo de 1997 pessoas. E
    a) 3 pessoas?
    b) 4 pessoas?
    possvel que cada uma delas conheca exatamente 101 pessoas
    2. Considere um grupo de 1998 pessoas. E
    do grupo?
    3. Cada um dos 102 estudantes e amigo de pelo menos 68 outros alunos. Prove que existem quatro
    estudantes com o mesmo n
    umero de amigos.
    4. Todos os vertices de um grafo tem 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 outras
    tres. Prove que existe uma pessoa que conhece todas as outras.
    6. A figura abaixo representa as ligacoes rodovi
    arias entre 14 cidades. Existe um caminho passando por
    cada cidade exatamente uma vez?

    7. Em um conjunto de 2n pessoas, cada uma delas possui um n


    umero par de amigos. Prove que existem
    duas pessoas que possuem um n
    umero par de amigos em comum.
    8. (R
    usssia 2000) Em um grafo G cada vertice possui grau pelo menos 3. Prove que nesse grafo ha um
    ciclo com o n
    umero de arestas nao divisvel por 3.
    1.3

    Grafos Orientados e Torneios

    1. Na Bruzundanga, quaisquer duas cidades s


    ao ligadas por uma estrada. Um imperador tirano decidiu
    transformar todas essas estradas em estradas de m
    ao u
    nica de tal forma que se uma pessoa sair de sua

    cidade nao poder


    a mais voltar. E possvel fazer tal crueldade?
    2. (R
    ussia 1970) Em um torneio completo de tennis haviam 12 jogadores. Prove que podemos encontrar
    tres 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 pas existem mais do que 101 cidades. A capital deste pas e
    conectada por linhas aereas a outras 100 cidades, e cada cidade, exceto pela capital, e conectada a
    outras 10 cidades (se A esta conectado a B, B esta conectado a A). Alem disso, todas as linhas aereas
    s
    ao de uma u
    nica direcao. Sabe-se que de qualquer cidade e possvel chegar a qualquer outra usando
    essas rotas. Prove que e possvel fechar metade das linhas aereas conectadas `a capital, e preservar a
    capacidade de viajar de uma cidade a qualquer outra.

    Prof. Bruno Holanda

    4. (R
    ussia 2004) Um grafo orientado tem 1001 vertices. Cada vertice possui 500 entradas e 500 sadas.
    Mostre que qualquer subgrafo de 668 vertices e conexo.
    1.4

    Misturando outras id
    eias

    De todas os assuntos abordados pela matem


    atica, a teoria dos grafos e dos que possuem o maior n
    umero de
    ideias diferentes. Nesta secao vamos resolver varios problemas de grafos usando estrategias que aprendemos
    anteriormente. Vamos comecar provando um fato conhecido com teorema de Ramsey.
    Problema 3. (Teorema de Ramsey) Em um grupo de seis pessoas sempre existem tres que se conhecem
    mutuamente ou tres que nao se conhecem mutuamente.
    Prova. Para resolver este problema vamos usar a linguagem dos grafos. Dessa forma, pense em um grafo com
    seis vertices A, B, C, D, E, F . Uma aresta contnua ir
    a representar uma amizade e uma aresta pontilhada,
    uma inimizade. Fixado o vertice A, sabemos que ele possui cinco arestas. Como s
    o ha dois tipos de aresta,
    um dos tipos foi usado pelo menos tres vezes. Sem perca de generalidade, suponha que o tipo continua foi
    escolhido tres vezes.
    A
    F
    B
    E
    C

    Agora, se uma das arestas BC,CD ou DB for contnua, teremos tres pessoas se conhecendo mutuamente.
    Caso contrario, as tres s
    ao pontilhadas. Neste caso, B,C e D nao se conhecem mutuamente.
    Veja que no exemplo anterior usamos esencialmente o princpio da casa dos pombos. O proximo problema
    e da olimpada do Leningrado de 1990. Neste exemplo vamos usar uma ideia um pouco mais sofisticada, o
    princpio do extremo.
    Problema 4. A Brunzundanga e a Zuzunzilandia s
    ao pases vizinhos. Sabe-se que cada cidade esta ligada a
    no m
    aximo dez outras cidades e que cidades do mesmo pas nao s
    ao ligadas. Prove que podemos pintar essas
    estradas usando dez cores de modo que estradas adjacentes possuam cores distintas.
    PS: As estradas s
    ao adjacentes se possuem uma cidade em comum.
    claro que podemos escolher uma
    Soluc
    ao. Suponha que inicialmente todas as estradas estavam incolores. E
    delas e pintar com uma das cores. A partir da vamos pintar as demais estradas respeitando a seguinte regra:
    Sejam X e Y duas cidades (uma de cada pas) tais que a estrada XY esta incolor. Desse modo, existe
    uma cor (digamos a cor 1) que nao foi usada em nenhuma das estradas partindo de X e uma cor (digamos a

    PROBLEMAS DE TREINAMENTO

    cor 2) que nao foi usada em nenhuma das estradas partindo de Y . Agora escolha o maior caminho da forma
    2 1 2 1 partindo de X.

    1
    2

    2
    1
    2

    Suponha, sem perda de generalidade, que esse caminho termine em uma aresta de cor 1 na cidade F .
    Desse modo, nao existe uma estrada de cor 2 partindo de F . Com isso, podemos trocar as cores das estradas
    deste caminho (onde for 2 pintamos de 1 e virce-versa) sem nenhum problema. Para finalizar, basta pintar
    a estrada XY da cor 2.
    Problemas Propostos
    1. Em um grupo de 50 cientistas sabe-se que cada um deles conhece pelo menos 25 outros cientistas. Prove
    que podemos colocar quatro deles ao redor de uma mesa de forma que cada cientista esteja sentado ao
    lado de dois amigos.
    2. (Jr. Balkan) Em um pas com seis cidades quaisquer duas s
    ao conectadas por uma linha aerea (idavolta). Cada linha aerea e operada por exatamente uma das duas empresas aereas existentes. Mostre
    que existem quatro cidades A, B, C, D tais que as linhas AB, BC, CD, DA s
    ao controladas por uma
    u
    nica empresa.
    3. (IMO 1964) Em um grafo de 17 vertices todas as arestas s
    ao tracadas e pintadas de uma de tres cores.
    Prove que existe um tri
    angulo com as tres arestas da mesma cor.
    4. (Proposto IMO 1977) Em uma sala estao nove homens. Sabe-se que em qualquer grupo de tres deles
    existem dois que se conhecem. Prove que podemos escolher quatro deles que se conhecem mutuamente.
    5. (R
    ussia 2003) Existem N cidades em um pas. Entre quaisquer duas cidades existe uma estrada ou uma
    linha de trem. Um turista deseja viajar pelo pas, visitando cada cidade uma u
    nica vez, e retornando `
    a
    cidade inicial. Prove que ele pode escolher uma cidade, e percurso da viagem de tal forma que ele nao
    ir
    a trocar de meio de transporte nao mais do que uma vez.
    6. (Sao Petersburgo 2001) Um pas possui 2000 cidades. Mostre que e possvel unir pares de cidades
    usando estradas (duas-maos) tal que para n = 1, 2, ..., 1000, existem exatamente duas cidades com
    exatamente n estradas.
    7. (R
    ussia 1974) Em um grupo de n pessoas sabe-se que se duas possuem mesmo n
    umero de amigos, entao
    elas nao possuem amigos em comum. Prove que existe uma pessoa com exatamente um amigo.

    Você também pode gostar