グラフの描き方

Frank HararyのGraph Theoryに下のような図があり, 読者を悩ませる. つまり頂点の黒丸が小さいので, 中央の線の集まったところに頂点があるようなないような.




説明を読むと, 上のFig.12.8はA uniquely 3-colorable graph having no triangles, 下のFig.12.9はA uniquely 3-colorable planer graphだから, 上は頂点なし, 下は頂点ありだ.

回路図の上で線が交差する場合, そこが接続されているか, 別の線なのかを表わすのに, 下のA, B2つの流儀がある.



どちらも左は別の線, 右は接続である. 用心深い人は, 接続には黒丸をつけ, 別線の時は飛び越えるように描く. 私は, 接続する場合は丁字に描き, 十字路は別線とするようにしていた.

英国の田舎の道は, 細い道が太い道と交わるとき, 細い方が必ず少し食い違いになっていて, 停車せず突っ切れないようになっている. 私のやり方と同じである. 都会の横断歩道にもそんな感じだったりする.



しかし, 私の流儀は回路図だから出来るので, グラフ理論では, 次数3の頂点までしか表示出来ず, 実用にならぬ.

例えば, 別の線が2本以上, 1点で交わらないように描くというのはどうか. 上の図の中央のW₉のようなところを, そのように描いたのがこれだ.



描いてはみたが, センスあるとは申せない. もう1工夫必要だ.

最初の図は, uniquelyに3色塗り分け可能という. どう塗り分けられるか. 以前のブログのプログラムを使って, 塗り分けたのが下だ.




ところで, 上の図は, 中央に頂点があっても3色塗り分け可能である.



この程度に頂点がしっかり描いてあれば, 悩むことはないのだが.