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
Forum