O Teorema da Amizade - inigma.files.wordpress.com · Grafos de Amizade Grafos que representam as rela˘c~oes de amizade. Pessoas - V ertices. Rela˘c~oes de Amizade - Arestas

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

O Teorema da AmizadeSeminario Diagonal

David Mesquita

Faculdade de Ciencias da Universidade do Porto

13 de Maio de 2009


Teorema da Amizade,TAFormulacao Original

Suponha-se que numa sociedade, cada par de pessoas temexactamente um amigo em comum. Entao ha uma pessoa quee amiga de toda a gente.


Conceitos 1

Definicao - Grafo (Simples)

Chama-se grafo,G, a um dupleto (V (G ),E (G )) ondeV (G ) = {v0, v1, ..., vn} e chamado o conjunto de vertices,E (G ) = {e1, ..., em} o conjunto das arestas.

Definicao- Grafo Finito

Um grafo diz-se finito se V (G ) e E (G ) forem finitos.


Conceitos 2

Definicao - Grau

Chama-se grau de um vertice v ao numero d(v) de arestasque incidem sobre esse vertice.

Definicao - Adjacencia

Dois vertices u, v dizem-se adjacentes se estiverem ligadospor uma aresta. Escreveremos u ∼ v .


Conceitos 3

Definicao - N-Caminho

Um n-caminho num grafo e uma sequencia finita(v1, ..., vn) ⊆ V (G ) onde vi ∼ vi+1, ∀i ∈ {1, ..., n − 1}.

Definicao - N-Ciclo

Um n-ciclo e um caminho (v0, ..., vn) ⊆ V (G ) onde v0 = vn evi 6= vj , ∀i , j ∈ {0, ..., n}.


Exemplo


Grafos de Amizade

Grafos que representam as relacoes de amizade.

Pessoas - Vertices.

Relacoes de Amizade - Arestas.

Dois vertices sao adjacentes se as respectivas pessoasforem amigas.

Nota

Estamos a assumir que a amizade e recıproca e sempre emrelacao a outrem.


Teorema da AmizadeFormulacao Combinatoria

Grafo Amigo - A-Grafo

Um grafo G diz-se amigo sse quaisquer 2 vertices de G temexactamente um vertice adjacente a ambos.

Teorema da Amizade - Grafos

Seja G um A-grafo finito. Entao ha um vertice de G que eadjacente a todos.


Quais sao os A-Grafos finitos?

O Teorema da Amizade, garante que estes sao os unicosA-grafos finitos.


E para A-Grafos infinitos?O 5-ciclo iterado

Construa-se G0 assim:

G1 = 5− ciclo;

Gn+1 = Gn+{vizinhos comuns para pares (u, v) ⊂ Gn quenao os tinham};G0 = limn→∞ Gn

Conclusao

O TA nao tem analogo para A-grafos infinitos.


Demonstracao- Paul Erdos, Alfred Renyi, Vera SosProva por reducao ao absurdo

Suponhamos que nenhum vertice de G = (V (G ),E (G )), umA− grafo, e adjacente a todos os outros. Isto e equivalente adizer que ∀u ∈ V (G ),∃v ∈ V (G ) : u 6∼ v .


Parte 1 - Combinatoria

Proposicao

G e regular, i.e., temos d(u) = d(v), ∀u, v ∈ V (G ).

Prova

Nao pode haver ciclos de comprimento 4.

Fixados u, v , u 6∼ v temos d(u) = d(v) = k .

d(z) = k , ∀z ∈ V (G )− {u, v}.QED.


Parte 1 - CombinatoriaVertices de G

Quantos tem?

G tem n = k2 − k + 1 vertices.


Parte 2 - Algebra Linear

Se k ≤ 2 temos,

Passamos daqui em diante a supor k > 2.


Parte 2 - Algebra LinearMatriz de adjacencia

Definicao

Chama-se matriz de adjacencia de G = (V (G ),E (G )) ,V (G ) = {v1, ..., vn}, a matriz M = (aij) definida por:

aij =

{1 se vi ∼ vj

0 se vi 6∼ vj


Parte 2 - Algebra LinearA matriz de adjacencia de G

Como sera a matriz de adjacencia M de G?

Simetrica ( portanto, diagonalizavel).

Cada linha tem exactamente k 1’s.

Para quaisquer 2 linhas, ha uma coluna onde ambaslevam 1.

A diagonal so tem 0’s.


Parte 2 - Algebra LinearA matriz M2

Esta matriz esta bem definida.

Forma

M2 = (k − 1)I + O , I a identidade, O a matriz com 1’s emtodas as entradas.

Valores proprios: k2 (multiplicidade 1) e k − 1(multiplicidade n − 1).


Parte 2 -Algebra LinearValores proprios de M

Quais sao?

Resposta

k ,√

k − 1, −√

k − 1.


Parte 2- Algebra LinearUsando o traco de M

α - numero de valores proprios√

k − 1;

β - numero de valores proprios −√

k − 1;

α + β = n − 1;

tr(M) = k + α√

k − 1− β√

k − 1 = 0

Como α 6= β,√

k − 1 = kα−β


Parte 3 - Teoria de Numeros

Teorema

Se√

m ∈ Q, entao√

m ∈ N.

Prova - Deedekind,1858

n0 - menor natural tal que n0

√m ∈ N.

Se√

m /∈ N, existe l ∈ N tal que 0 <√

m − l < 1.

Se n1 = n0(√

m − l),entao n1 ∈ N.

n1

√m ∈ N mas n1 < n0.

Contradicao.


Parte 3 - Teoria de Numeros

Seja entao h =√

k − 1 ∈ N.Voltando acima, tiramos

h(α− β) = k = h2 + 1.

Conclusao

h divide h2 e h2 + 1. Logo h = 1 e k = 2. Contradicao.

Esta demonstrado o Teorema da Amizade.


O TA Generalizado

Suponha-se que numa festa, cada par de pessoas amigas temexactamente λ amigos em comum, e cada par de pessoas quenao se conhecem tem exactamente µ ≥ 1 amigos em comum.Entao ou toda a gente tem o mesmo numero de amigos, ou hauma pessoa que e amiga de toda a gente.


Em Grafos

Definicao - (λ, µ)-Grafo

Grafo onde ∀u, v ∈ V (G ), u e v tem ou exactamente λvizinhos, se u ∼ v , ou exactamente µ vizinhos, se u 6∼ v .

Definicao - Grafo Fortemente Regular → GFR(n,k,λ, µ)

E um (λ, µ)− grafo de n vertices, onde d(v) = k , ∀v ∈ V .


Grafos Fortemente Regulares


O TA Generalizado

Seja G um (λ, µ)-grafo, µ ≥ 1. Entao ou G e fortementeregular, ou G tem um vertice adjacente a todos os outros.


(λ, µ)-Grafos IrregularesCaracterizacao

Teorema

Seja G um (λ, µ)-Grafo irregular de n vertices. Entao uma dasseguintes afirmacoes ocorre:

µ = 0, G = mKλ+2 + tK1, n = m(λ + 2) + t;

µ = 1, G = K1 ∨ (mKλ+1), n = m(λ + 1) + 1;

Nota

G1 + G2 = (V (G1) ∪ V (G2),E (G1) ∪ E (G2)).G1 ∨ G2 = (V (G1) ∪ V (G2),E (G1) ∪ E (G2) ∪ {(u, v) : u ∈V (G1), v ∈ V (G2)}).


Outra Formulacao

Seja G um grafo com a propriedade de entre quaisquer 2vertices existir um unico 2− caminho. Entao G tem umvertice que e adjacente a todos.


Em aberto...

Conjectura de Kotzig - 1974

Seja l > 2. Entao nao ha grafos finitos com a propriedade deentre quaisquer 2 vertices existir um unico l − caminho .


Problema

Suponha-se que numa festa, quaisquer m ≥ 2 pessoas temexactamente um amigo em comum. Encontra o numero deamigos da pessoa que tem mais amigos.


Bibliografia I

IGNER, Martin; ZIEGLER, Gunter:Proofs from the Book,Terceira Edicao,Springer;

ERA, Ralucca; SHEN, Jian:Extension of Strongly RegularGraphs,THE ELECTRONIC JOURNAL OFCOMBINATORICS 15, (2008);

Documents

O Teorema da Amizade - inigma.files.wordpress.com · Grafos de Amizade Grafos que representam as rela˘c~oes de amizade. Pessoas - V ertices. Rela˘c~oes de Amizade - Arestas