G を単純無向グラフ、 e を G の枝、そして π を G 上の
向き付けであるとします。ここで、 π の e に対応する向き
だけを逆向きに、その他の向きは全てそのままにして、 G 上の
新しい向き付け π' を生成する操作のことを、 π
の e に対する``edge flip operation''と呼ぶことに致します。
本発表では``clique-acyclic digraph''と呼ばれる有向グラフ
(すなわち、自身の有する任意のclique上においてacyclic
であることが保証されているような有向グラフ)上における、
``edge flip operation''についてお話ししたいと思います。
なお、得られた主要な結果は以下のようなものです。
1): G が平面グラフであるか、もしくは最大次数が7以下
である場合には、 G 上の2つのclique acyclicな向き付け
π と π' をどの様に選んできても、 π から
出発して高々「2×( G の枝の数)回」のflip操作により、
その各中間段階で得られる向き付けのclique acyclicityを
保存しつつ、 π' に移してやることが出来ます。
2):上述の定理における後半の条件「最大次数が7以下」
は、sharpです。すなわち、最大次数が8である場合には、
上述の定理を満たさない単純無向グラフ G の例が丁度
五つだけあり、それらのグラフの位数は順に15点、18点、
18点、20点、そして24点です。