MO405 - Atas das
Aulas
Ata de Aula: 27/11/2002
Capítulo: 8.5
Gráficos Aleatórios e 8.6 Autovalores de Grafos
Redator: Cibele Brunetto 012107
Tópicos Discutidos mais
importantes:
8.5 Gráficos Aleatórios
8.5.1. Pontos de Fusão
Imagine a representação de um sólido por um grafo que é o produto cartesiano de Pl, Pm, Pn. Cada vértice representa uma molécula e cada aresta é uma ligação química entre moléculas. Quando a temperatura aumenta, algumas ligações são quebradas. Assumimos que as ligações se quebram aleatoriamente, conforme a temperatura vai subindo. Cada temperatura corresponde a um nível de ligações quebradas. Enquanto o grafo permanece amplamente conexo, o material é sólido.
Existe um limite para o número de ligações a serem quebradas tal que quase todo modo de quebrar algumas poucas ligações deixa a componente (do grafo) gigante e quase todo modo de quebrar mais ligações deixa as componentes pequenas. Abaixo da temperatura limite o material irá quase certamente ser um sólido e, acima da temperatura limite o material quase certamente não será um sólido.
8.5.3. Espaço ou modelo de probabilidade
Um espaço de probabilidade (ou modelo de probabilidade) discreto é um conjunto finito S com pesos não negativos nos elementos, que somam 1. Um evento é um subconjunto de S. A probabilidade P(A) de um evento A é a soma dos pesos dos elementos de A. Dois eventos A e B são independentes se a probabilidade da intersecção de A com B for igual ao produto da probabilidade de A pela probabilidade de B.
8.5.6. Variáveis aleatórias
Uma variável aleatória é uma função que atribui um número real a cada elemento de um espaço de probabilidade (notação: X = k consiste de todos os elementos onde a variável X tem valor k).
A esperança E(X) de uma variável aleatória
X é a média dos valores de X
Notação: Somatória em k { k.P(X=k) }
Exemplo de variável aleatória (Meidanis):
- espaço de probabilidade: probabilidade de cada aluno bater o carro
- variável aleatória: custo do carro de cada aluno
A esperança E(X) = custo de cada carro * probabilidade de bater o carro, significa o quanto se "espera" gastar com um acidente em carro da classe.
8.5.7 Propriedade de linearidade
Se X e o conjunto finito {Xi} são variáveis aleatórias no mesmo espaço e X = Somatória { Xi }, então E(X) = Somatória { E(Xi) } e também E(cX)= cE(X) para toda constante real c.
A esperança é uma função linear.
Variável indicadora: todo elemento do espaço assume um valor em {0,1}. A esperança desa variável indicadora é a probabilidade de que ela seja igual a 1.
8.5.3. Modelo A: Dados n e p = p(n), gerar grafos com conjunto de vértices [n], deixando que cada par seja uma aresta com probabilidade p, independentemente. Cada grafo com m arestas tem a seguinte probabilidade:
Exemplo para Modelo A: Desenhar grafos aleatórios de 3 vértices, seguindo o modelo A.
p = p(n) = p(3) = 0,1 (esse valor de 0,1 foi a probabilidade escolhida pela turma para ser a probabilidade da existência de cada aresta em um grafo de 3 vértices)
Figura 1.
(Meidanis) O que acontece se mudarmos a probabilidade p(n) = ½?
A probabilidade de ocorrer cada um desses 8 grafos será igual, ou seja, 0,125.
8.5.14. Modelo B: A probabilidade de um grafo com conjunto de vértices [n] e m arestas é igual a:
(Meidanis) Esse modelo quer que todos os grafos com um mesmo número de arestas tenham a mesma probabilidade de ocorrer.
Exemplo para o Modelo B:
(Usando os mesmos grafos da Figura 1)
Fixamos o número de vértices n = 3
Seja m o número de arestas:
8.5.19. Propriedade monotônica: é uma propriedade de grafos que é preservada ao se adicionar arestas ao grafo.
Função limiar de probabilidade para uma propriedade monotônica Q é uma função t(n) tal que quando p(n)/t(n) -> zero quase nenhum grafo satisfaz Q, e quando p(n)/t(n) -> infinito quase todo grafo satisfaz Q.
(Meidanis): é o valor (limiar) da probabilidade em função de n tal que, abaixo daquele limiar, quase nenhum grafo tem tal propriedade e, acima daquele limiar, quase todo grafo tem tal propriedade.
Evolução dos Grafos
O que acontece (quais propriedades valem) nas seguintes funções limiares:
1) p = 1/n^(k/(k-1))
Propriedade monotônica: aparecem árvores de k vértices e não há ciclos.
Abaixo dessa probabilidade, não existem árvores com k vértices. Acima dessa probabilidade, existem árvores com k vértices.
2) p = 0.9/n
Grafos têm várias componentes com poucas arestas (no máximo log n) e cada componente tem no máximo 1 ciclo.
3) p = 1/n
Grafos têm várias componentes e quase todas têm ciclos e tamanho da maior componente é n^2/3.
4) p = 1.1/n
O número de vértices fora da “componente gigante” se torna o(n) e começam a aparecer alguns ciclos com 3 cordas cruzadas e os grafos não são planares.
5) p = 0.9*(ln n)/n
Grafos não são conexos, têm vértices isolados e componente gigante.
6) p = 1.1*(ln n)/n
Grafos são conexos, não têm vértices isolados e provavelmente têm ciclos hamiltonianos.
7) p = (ln n)^2/n
Os grafos não são mais esparsos (têm um grande número de arestas).
Testar isomorfismo em grafos aleatórios
É possível testar isomorfismo em grafos aleatórios e o algoritmo para isso é quadrático.
Em linhas gerais, o algoritmo seria:
- Pegar 2 grafos aleatórios
- Criar ordem canônica para esses grafos (ordena vértices pelos graus)
- Compara matrizes de adjacência dos grafos
- Se as matrizes dos grafos forem iguais, então eles são isomorfos.
Como calcular chi’ em grafos aleatórios
· chi’(G) = DELTA(G) (onde DELTA(G) é o grau máximo)
8.6 Autovalores de Grafos
8.6.39. Teorema da Amizade: Se G é um grafo no qual quaisquer 2 vértices têm exatamente um vizinho em comum, então G tem um vértice adjacente a todos os outros.
Este teorema diz que em qualquer festa na qual todo par de pessoas têm exatamente 1 conhecido em comum, então existe 1 pessoa que conhece todo mundo. O grafo resultante da relação de conhecidos consiste em alguns triângulos compartilhando 1 vértice.