Olimpíadas ⇒ Teoria dos Grafos Tópico resolvido

[goncalves3718]

Determine o número mínimo de pessoas em uma festa para que podemos garantir que existem [tex3]3[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]3[/tex3]

pessoas que se conhecem ou [tex3]3[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]3[/tex3]

pessoas que não se conhecem.

[leozitz]

esse é um problema sobre os números de ramsey, em particular, estamos falando do R(3, 3), o menos valor n tal que se temos um K_n e pintamos suas arestas usando duas cores, teremos um K_3 de uma cor ou um K_3 da outra, nesse caso estamos imaginando cores como conhece ou não conhece.
lema: [tex3]R(3, 3) \le6 [/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]R(3, 3) \le6 [/tex3]

olhando para um vértice v, ele tem 5 vizinhos e dessa forma, por PCP ele conhece ou desconhece 3 dos seus vizinhos, vamos supor que ele conheça 3 de seus vizinhos (se não a gente prossegue da mesma forma porém encontra 3 que não se conhecem).
v conhece a, b e c se a conhece b ou a conhece c ou ainda b conhece c, o problema acaba, então vamos supor que a e b, a e c , b e c não se conhecem , dessa forma encontramos 3 pessoas que não se conhecem mutualmente.

agora para provar que 6 é o menor valor, precisamos encontrar uma configuração com 5 que não funcione.

Captura de tela de 2022-10-08 19-52-36.png (26.47 KiB) Exibido 487 vezes

a configuração acima n tem 3 que se conhecem mutualmente e nem 3 que se desconhecem mutualmente, portanto o minimo é 6.

obs: a imagem acima é do material do POTI