MO405 - Exercícios - Propostos em 2002-08-21

Nos exercícios que perguntam "verdadeiro ou falso", deve-se justificar a resposta da seguinte forma: se for verdadeiro, com uma prova; se for falso, com um contra-exemplo.

  1. (2.1.4 do livro) Verdadeiro ou Falso: Todo grafo com menos arestas que vértices tem um componente que é uma árvore
  2. (2.1.10 do livro) Sendo u e v vértices em um grafo conectado com n vértices. Prove que se d(u,v)>2, então d(u)+d(v)<= n+1-d(u,v). Construa exemplos para mostrar que esta condição pode falhar quando d(u,v)<=2.
  3. (2.1.12 do livro) Calcule o diâmetro e o raio do biclique Km,n.
  4. (2.1.47 do livro) Diâmetro e raio.
      a - Prove que a função da distancia d(u,v) em um par de vértices de um grafo satisfaz a desigualdade triangular: d(u,v)+d(v,w)>= d(u,w).
      b - Usando parte de (a) prove que diam G <= 2rad G.
      c - Para todo inteiro positivo r e d que satisfaz r<=d<=2r, construa um grafo simples com raio r e diâmetro d. (Dica:Construir um grafo adequado com um circulo).

Soluções - Discutidas em classe em 2002-08-26

  1. 2.1.4

    Este problema foi dividido em dois casos:
    *Primeiro caso: Existe apenas um único componente conexo. Para este caso se tivermos n vértices o único numero possível de arestas que seja menor que n e mantenha um componente conexo é n-1, ou seja é uma arvore.

    * Segundo caso: O grafo é formado por mais de um componente:
    Supondo que todos os componentes não são arvores então cada componente tem k vértices e pelo menos k arestas se se somarmos entre todos os componente o numero de vértices dá k1+...+ ki = n. Como o número de arestas é pelo menos igual ao número de vértices pela suposição inicial, então temos a contradição.

  2. 2.1.10

    Fato: Existe um caminho entre u e v o qual dá o valor de d(u,v) e u e v não se conectam a nenhum vértice deste caminho, exceto os vértices imediatamente conectados a u e a v, porque se o fizerem a distancia entre eles iria diminuir. Existem portanto d(u,v)-1 vértices que não são vizinhos nem de u nem de v.
    d(u)+d(v)=|N(u)|+|N(v)| = |N(u) U N(v)|, porque não existem vértices vizinhos a u e a v simultaneamente (já que d(u,v) > 2)
    |N(u) U N(v)| <= n - (d(u,v)-1)
    d(u)+d(v) <= n +1 - d(u,v)

    um exemplo se quebraria a regra se d(u,v) <= 2 é K3

  3. 2.1.12 Chegamos a uma tabela que representa a solução deste exercício.
    M\N 0 1 >1
    0 X D = 0
    R = 0    		 D = infinito
    R = infinito
    1 D = 0
    R = 0    		 D = 1
    R = 1    		 D = 2
    R = 1
    >1 D = infinito
    R = infinito    		 D = 2
    R = 1    		 D = 2
    R = 2
  4. 2.1.47

    a - Supondo que d(u,v) = a e que d(v,w) = b então existe um caminho entre u e v de tamanho a, e um caminho de v a w de tamanho b. Concatenando estes caminhos temos um passeio de u a w de tamanho a+b. O caminho mínimo de u a w terá então tamanho menor ou igual a a+b.

    b - d(u,w) <= d(u,v)+d(v,w)
    Escolha u e w de forma que d(u,v)= diam(G).
    Escolha v de forma que e(v)=rad(G).
    Daí temos:
    diam(G) = d(u,w) <= d(u,v) + d(v,w) <= rad(G) + rad(G)
    ou seja, diam(G) <= 2*rad(G)

    c - Sejam r e d que satisfazem r<=d<=2r. Um grafo cujo raio seja r e o diâmetro seja d pode ser obtido da seguinte forma:

  5. Construa um circuito C2r+1. Construa também um caminho Pd-r. Ligue um dos extremos do caminho a um dos vértices do circuito. Isso irá formar um grafo parecido com 9, ou 6, que resolve o problema.