Breve Histórico
Snarks
Flower-Snarks
O Perfume dos Flower-Snarks
Cândida Nunes da Silva
Trabalho conjunto com Cláudio L. Lucchesi
Seminários do Instituto de Computação - UNICAMP
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Roteiro
1
Breve Histórico
2
Snarks
3
Flower-Snarks
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Teorema das Quatro Cores
Teorema das Quatro Cores (T4C)
Todo grafo planar sem arestas de corte admite uma 4-coloração de
suas faces.
Exemplo: K4
0
2
3
1
Enunciado (como conjetura) em 1852 e demonstrado por
Appel e Haken em 1977 e Robertson et al. em 1997.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Coloração de Tait
Tait (1880)
Um grafo planar cúbico e 3-conexo admite 4-coloração de faces se
e somente se admite 3-coloração de arestas.
Exemplo: K4
Redução do T4C a grafos cúbicos e 3-conexos é simples.
Versão Equivalente do T4C
Todo grafo planar cúbico e 3-conexo admite 3-coloração de arestas.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
O Engano de Tait
Todo grafo cúbico hamiltoniano tem 3-coloração de arestas.
Tait acreditava ter provado o T4C pensando que todo grafo
planar cúbico e 3-conexo seria hamiltoniano.
Tutte mostrou um contra-exemplo em 1946, mais de meio
século depois!!!
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
O Grafo de Petersen
Grafo de Petersen (1898): Cúbico, sem arestas de corte e sem
3-coloração de arestas.
Não é planar.
O grafo de Petersen tem 4-coloração de arestas.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
O Grafo de Petersen
Grafo de Petersen (1898): Cúbico, sem arestas de corte e sem
3-coloração de arestas.
Não é planar.
O grafo de Petersen tem 4-coloração de arestas.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
O Grafo de Petersen
Grafo de Petersen (1898): Cúbico, sem arestas de corte e sem
3-coloração de arestas.
Não é planar.
O grafo de Petersen tem 4-coloração de arestas.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
O Grafo de Petersen
Grafo de Petersen (1898): Cúbico, sem arestas de corte e sem
3-coloração de arestas.
Não é planar.
O grafo de Petersen tem 4-coloração de arestas.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Teorema de Vizing-Gupta
Existe limite superior no número de cores necessárias para
coloração de arestas?
Vizing (1964) - Gupta (1966)
Todo grafo simples tem coloração de arestas com ∆ ou ∆ + 1
cores.
Holyer (1981) Decidir se são necessárias ∆ ou ∆ + 1 cores é
um problema NP-completo, mesmo para grafos cúbicos.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Snarks
Um snark é um grafo cúbico, sem aresta de corte, sem
3-cortes não triviais e sem 3-coloração de arestas.
1898 - Grafo de Petersen – Primeiro snark descoberto.
1946 - Snark de Blanuša com 18 vértices.
1948 - Snark de B. Descartes (Tutte) com 210 vértices.
1973 - Snark de Szekeres com 50 vértices.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
O Nome Snark
O nome snark foi dado por B. Descartes, em alusão ao poema
”The Hunting of the Snark” de Lewis Carroll de 1874.
Poema descreve ”with infinite humor the impossible voyage of
an improbable crew to find an inconceivable creature” (Sidney
Williams and Falconer Madan).
Snake + Shark???
A dificuldade em se encontrar tais grafos motivou a escolha
do nome.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Os Flower-Snarks
Em 1975, Isaacs finalmente descobriu uma famı́lia infinita de
snarks, os flower-snarks:
y3
x3
w3
y2
x2
z3
w2
z4
y4
z2
z1
w1
y1
x4
w4
x1
Cândida Nunes da Silva
z5
w5
x5
y5
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Os Grafos Gn
Grafos Gn :
y3
x3
w3
x4
y2
x2
z3
w2
z4
y4
z2
z1
w1
y1
w4
x1
Cândida Nunes da Silva
zn
wn
xn
yn
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Os Grafos Gn
Grafos Gn :
x1
x2
x3
y1
w1
z1
x4
y2
w2
z2
Cândida Nunes da Silva
xn
y3
w3
z3
yn
y4
w4
z4
O Perfume dos Flower-Snarks
wn
zn
Breve Histórico
Snarks
Flower-Snarks
Os Grafos Hn
Grafos Hn :
y3
x3
w3
y2
x2
z3
w2
z4
y4
z2
z1
w1
y1
x4
w4
x1
Cândida Nunes da Silva
zn
wn
xn
yn
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Os Grafos Hn
Grafos Hn :
x1
x2
x3
y1
w1
z1
w2
z2
Cândida Nunes da Silva
xn
x4
y2
w3
z3
yn
y4
y3
w4
z4
O Perfume dos Flower-Snarks
wn
zn
Breve Histórico
Snarks
Flower-Snarks
Notação
Vi = {wi , xi , yi , zi }.
Ei são as arestas de Vi −1 a Vi .
Abuso: E1 = En+1 .
Vi
xi
xi −1
xi +1
yi
yi −1
yi +1
wi −1
wi
wi +1
zi −1
zi
zi +1
Ei
Cândida Nunes da Silva
Ei +1
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Colorações de Ei
Uma coloração das arestas de Ei com até três cores pode ser
uma monocoloração, bicoloração ou tricoloração, de acordo
com o número de cores utilizadas.
Em uma bicoloração a cor majoritária é usada em duas arestas
e a cor minoritária em uma só.
xi
yi
wi
zi
Ei
Cândida Nunes da Silva
Ei +1
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Transições Válidas
Uma coloração de Ei ∪ Ei +1 com até três cores forma uma
transição válida de Ei para Ei +1 se pode ser estendida a G [Vi ]
de forma que arestas adjacentes a vértices de Vi tenham cores
distintas duas a duas.
Os grafos Gn e Hn têm 3-coloração de arestas se e somente se
existe uma seqüência de transições válidas de Ei para Ei +1 ,
para todo 1 ≤ i ≤ n.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Monocolorações de Ei
Não existem transações válidas a partir de uma
monocoloração.
xi
yi
wi
zi
Ei
Cândida Nunes da Silva
Ei +1
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Bicolorações de Ei
Toda transição válida de uma bicoloração de Ei para Ei +1
satisfaz as seguintes propriedades:
A coloração de Ei +1 também é uma bicoloração.
A cor minoritária da bicoloração de Ei também é minoritária
na bicoloração de Ei +1 .
A cor majoritária da bicoloração de Ei não é usada na
bicoloração de Ei +1 .
As arestas minoritárias das bicolorações incidem em vértices
distintos de Vi .
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Bicolorações de Ei
Exemplo:
xi
yi
wi
zi
Ei
Cândida Nunes da Silva
Ei +1
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Bicolorações de Ei
Se Gn ou Hn tem 3-coloração de arestas com bicoloração para
algum Ei , então todo Ei tem bicoloração.
Para n par, Gn e Hn têm 3-coloração de arestas.
Para n ı́mpar, nem Gn nem Hn tem 3-coloração de arestas
com bicoloração para algum Ei .
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Bicolorações de Ei
Se Gn ou Hn tem 3-coloração de arestas com bicoloração para
algum Ei , então todo Ei tem bicoloração.
Para n par, Gn e Hn têm 3-coloração de arestas.
x1
x2
y1
w1
z1
x3
y2
w2
z2
xn
y3
w3
z3
yn
wn
zn
Para n ı́mpar, nem Gn nem Hn tem 3-coloração de arestas
com bicoloração para algum Ei .
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Bicolorações de Ei
Se Gn ou Hn tem 3-coloração de arestas com bicoloração para
algum Ei , então todo Ei tem bicoloração.
Para n par, Gn e Hn têm 3-coloração de arestas.
x1
x2
y1
w1
z1
xn
x3
y2
w2
z2
y3
w3
z3
yn
wn
zn
Para n ı́mpar, nem Gn nem Hn tem 3-coloração de arestas
com bicoloração para algum Ei .
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Bicolorações de Ei
Se Gn ou Hn tem 3-coloração de arestas com bicoloração para
algum Ei , então todo Ei tem bicoloração.
Para n par, Gn e Hn têm 3-coloração de arestas.
x1
x2
y1
w1
z1
xn
x3
y2
w2
z2
y3
w3
z3
yn
wn
zn
Para n ı́mpar, nem Gn nem Hn tem 3-coloração de arestas
com bicoloração para algum Ei .
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Tricolorações de Ei
Toda transição válida de uma tricoloração de Ei para Ei +1
leva a uma tricoloração de Ei +1 que é uma rotação da
tricoloração de Ei .
xi
yi
wi
zi
Ei
Cândida Nunes da Silva
Ei +1
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Tricolorações de Ei
Toda transição válida de uma tricoloração de Ei para Ei +1
leva a uma tricoloração de Ei +1 que é uma rotação da
tricoloração de Ei .
xi
yi
wi
zi
Ei
Cândida Nunes da Silva
Ei +1
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Tricolorações de Ei
Se Gn ou Hn tem 3-coloração de arestas com tricoloração para
algum Ei , então todo Ei tem tricoloração.
Para n ı́mpar, Gn tem 3-coloração de arestas com tricoloração
para todo Ei .
Hn , para n ı́mpar, não tem 3-coloração de arestas com
tricoloração para algum Ei .
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Tricolorações de Ei
Se Gn ou Hn tem 3-coloração de arestas com tricoloração para
algum Ei , então todo Ei tem tricoloração.
Para n ı́mpar, Gn tem 3-coloração de arestas com tricoloração
para todo Ei .
x1
x2
y1
w1
z1
x3
y2
w2
z2
xn
xn−1
y3
w3
z3
yn−1
wn−1
zn−1
yn
wn
zn
Hn , para n ı́mpar, não tem 3-coloração de arestas com
tricoloração para algum Ei .
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Tricolorações de Ei
Se Gn ou Hn tem 3-coloração de arestas com tricoloração para
algum Ei , então todo Ei tem tricoloração.
Para n ı́mpar, Gn tem 3-coloração de arestas com tricoloração
para todo Ei .
x1
x2
y1
w1
z1
x3
y2
w2
z2
xn
xn−1
y3
w3
z3
yn−1
wn−1
zn−1
yn
wn
zn
Hn , para n ı́mpar, não tem 3-coloração de arestas com
tricoloração para algum Ei .
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Paridade de Permutações
Tricolorações são permutações das três cores.
Permutações têm paridade de acordo com número de
inversões.
Exemplo: permutação 321 é ı́mpar (3 inversões).
Se o número de elementos é ı́mpar, uma rotação não altera a
paridade.
Uma troca de elementos inverte a paridade da permutação.
Cândida Nunes da Silva
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
Impossibilidade de 3-coloração
Parai Hn , n ı́mpar:
Se há 3-coloração, esta tem tricoloração em todo Ei .
Transições válidas de uma tricoloração de Ei para Ei +1
preservam paridade da permutação, são rotações.
É impossı́vel que as tricolorações tenham a mesma paridade
em todo Ei , pois as ligações cruzadas x1 yn e xn y1 trocam a
paridade da permutação.
x1
y1
w1
z1
x2
y2
x3
w2
z2
Cândida Nunes da Silva
y3
w3
z3
x4
xn
y4
w4
z4
yn
wn
zn
O Perfume dos Flower-Snarks
Breve Histórico
Snarks
Flower-Snarks
“The Hunting of the Snark”
“Just the place for a Snark!” the Bellman cried,
As he landed his crew with care;
Supporting each man on the top of the tide
By a finger entwined in his hair.
“Just the place for a Snark! I have said it twice:
That alone should encourage the crew.
Just the place for a Snark! I have said it thrice:
What I tell you three times is true.”
Cândida Nunes da Silva
O Perfume dos Flower-Snarks