MO405 - Atas das Aulas


Aula: 
 14/08/2002
Revisões:
 __/__/____ ,
Redator:
 Cláudio M. Zaina

Nota do Instrutor: a seção sobre Problemas Extremais é menos importante para este curso. Pode ser vista apenas como material avançado que seria bom saber mas não será cobrado.

Definições:

Grafos Regulares:
  • grafo onde todos os vértices têm  o mesmo grau;
  • notação: diz-se k-regular;
  • há vários grafos k-regulares isomorfos.

    • Grafos Pares:
  • grafo em que todos os vértices têm graus pares.

    • Contagem:
  • ordem: número de vértices do grafo;
  • a soma dos graus dos vértices de um grafo é igual a duas vezes o seu número de arestas (Somatória { d(vi) = 2 . e(G) } );
  • grau médio = 2 . e(G) / ordem;
  • delta(G) <= grau médio <= DELTA(G)
  • todo grafo tem um número par de vértices de grau ímpar;
  • grafo k-regular de n vértices tem  nk / 2 arestas;

    • Problemas Extremais:
  • problemas determinando máximos ou mínimos;
  • problemas relacionados a valores máximos ou mínimos de uma função sobre uma classe de objetos;
  • (explicação sobre prova de mínimo retirada do livro, comentário 1.3.14) mostrar que beta é o mínimo de f(G) para grafos da classe G requer mostrar que: (1) f(G) >= beta para todo G em G; (2) f(G) = beta para algum G de G. A prova do limite deve valer para cada G de G. Para a igualdade basta obter um exemplo em G com o valor desejado de f.
  • se um grafo G tem delta(G) >= (n - 1) / 2 então G é conexo;
  • (n - 3) / 2  ou (n - 2) / 2 não seriam pior caso pois são menores que (n - 1) / 2 ?

    [A] delta(G) > (n - 2) / 2  ==> (?) grafo é conexo
    [B] delta(G) >= (n - 1) / ==> grafo é conexo

    Caso:
    		 A
    		 B
    n = 20
    		 delta > 9  ==> conexo (?)
    		 delta >= 9,5 ==> conexo (ok!)
    n = 31
    		 delta > 14,5 ==> conexo (?)
    		 delta >= 15 ==> conexo (ok!)

    Questão de ser mais justo (sharp)? Seria só com maior ou igual!

    Prova do Vinícius:

    Caso:
    		 A
    		 B

    		n = 2p
    delta > p - 1 <==> delta >= p

    n = 2p + 1
    delta > (2p + 1 - 2) / 2 = p - 1/2
    delta > p - 1/2  <==>  delta >= p
    		 n = 2p
    delta >= p - 1/2 <==> delta >= p

    n = 2p +1
    delta >= (2p + 1 - 1) / 2 <==> delta >= p

    Tabelando delta em função de n:
    n
    		  delta >=
    1
    		 0
    2
    		 1
    3
    		 1
    4
    		 2
    5
    		 2
    6
    		 3
    7
    		 3
    ...
    		 ...

    Aconselha-se a usar, quando tratar-se de números inteiros, a notação de chão ou teto para promover a maior exatidão da expressão. Assim fica:  delta >= teto ( (n - 1) / 2 ). Em outras palavras:
    -- inteiro maior ou igual a algo, arredonda a coisa pra cima;
    -- inteiro menor ou igual a algo, arredonda a coisa pra baixo.

    • Seqüências Gráficas:
  • Seqüência de graus de um grafo é a lista dos graus do grafo.

    • Método para determinar se uma seqüência representa um grafo válido:

    3 3 3 3 3 2 2 1
    		seqüência proposta
    2 2 2 3 2 2 1
    		passo (1) subtrai-se tantas unidades dos seguintes quantos graus tiver o maior da lista (3).
    3 2 2 2 2 2 1
    		passo (2) reordena-se a lista;
    1 1 1 2 2 1
    		(1)
    2 2 1 1 1 1
    		(2)
    1 0 1 1 1
    		(1)
    1 1 1 1
    		apenas 1s. Como há um número par deles, é possível criar um grafo cuja seqüência de graus é a seqüência original.