Lucas perguntou na aula se é verdade que todo
digrafo semicompleto forte contém um torneio
gerador forte. Eu respondi que achava que sim,
mas vejo agora ques estava errado. Um
contraexemplo é o ciclo de comprimento 2.
Também existem contraexemplos com 3, 4, etc.
vértices.
Apesar disso, é verdade que o teorema de Camion
vale para qualquer digrafo semicompleto forte
(embora o enunciado do livro só fale em torneios.)
--P
Como seriam esses contra-exemplos de tamanho 3, 4, etc?
Estava pensando que para digrafos >= 3, poderia ser feito algo assim: "Pelo Teorema de Camion, vale que o digrafo D tem um ciclo hamiltoniano H. Como D é semicompleto, basta completar H até que seja um torneio, que claramente será forte e gerador".
Ulalá! A coisa está esquentando.
Parece que falei mais uma bobagem.
Vamos fazer uma lista do que sabemos.
1. O digrafo completo com 2 vértices tem as
seguintes propriedades: é semicompleto e forte,
mas não contém um torneio forte com 2 vértices.
2. Todo digrafo semicompleto forte tem um
ciclo hamiltoniano. (Acho que isso é verdade,
não?)
3. Todo digrafo semicompleto forte com 3 ou mais
vértices tem um subdigrafo gerador forte que é
um torneio. (Prova: Seja D o digrafo em questão.
Seja C um ciclo hamiltoniano de D. Retire de D
todo arco uv tal que vu está em C. Em seguida,
para cada arco que não está em C mas pertence
a um 2-ciclo, apague qualquer dos dois arcos do
2-ciclo. O que sobra é um torneio forte com
conjunto de vértices V(D).)
4. Para todo n >= 2 existe um digrafo semicompleto
forte com n vértices com a seguinte propriedade:
se retirarmos um dos arcos de cada 2-ciclo, o que
sobra é um torneio não-forte.
Será que tudo isso está certo?
--Paulo
Parece que falei mais uma bobagem.
Vamos fazer uma lista do que sabemos.
1. O digrafo completo com 2 vértices tem as
seguintes propriedades: é semicompleto e forte,
mas não contém um torneio forte com 2 vértices.
2. Todo digrafo semicompleto forte tem um
ciclo hamiltoniano. (Acho que isso é verdade,
não?)
3. Todo digrafo semicompleto forte com 3 ou mais
vértices tem um subdigrafo gerador forte que é
um torneio. (Prova: Seja D o digrafo em questão.
Seja C um ciclo hamiltoniano de D. Retire de D
todo arco uv tal que vu está em C. Em seguida,
para cada arco que não está em C mas pertence
a um 2-ciclo, apague qualquer dos dois arcos do
2-ciclo. O que sobra é um torneio forte com
conjunto de vértices V(D).)
4. Para todo n >= 2 existe um digrafo semicompleto
forte com n vértices com a seguinte propriedade:
se retirarmos um dos arcos de cada 2-ciclo, o que
sobra é um torneio não-forte.
Será que tudo isso está certo?
--Paulo