O Teorema da Amizade - inigma.files.wordpress.com · Grafos de Amizade Grafos que representam as...

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

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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 .

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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}.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

Exemplo

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

Quais sao os A-Grafos finitos?

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

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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 .

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

Parte 1 - CombinatoriaVertices de G

Quantos tem?

G tem n = k2 − k + 1 vertices.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

Parte 2 - Algebra Linear

Se k ≤ 2 temos,

Passamos daqui em diante a supor k > 2.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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).

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

Parte 2 -Algebra LinearValores proprios de M

Quais sao?

Resposta

k ,√

k − 1, −√

k − 1.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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α−β

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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 .

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

Grafos Fortemente Regulares

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

O TA Generalizado

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

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

(λ, µ)-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)}).

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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 .

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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.

Formulacao Original Conceitos Formulacao Combinatoria Demonstracao Generalizacoes Bibliografia

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);