- 著者
-
山下 哲
- 出版者
- 木更津工業高等専門学校
- 雑誌
- 木更津工業高等専門学校紀要 (ISSN:2188921X)
- 巻号頁・発行日
- vol.35, pp.41-44, 2002-01
「グラフ」とは、数個の「頂点」と数本の「辺」(2頂点を端点とする線分)から成る図形のことである。グラフを平面上に描いた図のうちで、自己交差がない図を「平面グラフ」と呼ぶ。一般に、頂点の個数に比べて辺の本数が多過ぎるグラフは平面グラフをもたない。平面グラフをもつグラフを「平面的グラフ」と呼ぶ。各辺の図が直線分である平面グラフを「直線的平面グラフ」と呼ぶ。1948年にFaryは次の定理を証明した:「任意の平面的グラフの任意の平面グラフは、直線的平面グラフに平面上で辺を交差させることなく変形できる。」 グラフを平面上に描いた図の中で、曲線分と一致する部分をそのグラフの「道」と呼ぶ。道は、ちょうど1本の辺に接続している頂点を2個だけもち、その他の頂点はちょうど2本の辺と接続している部分グラフである。Faryの定理を拡張して、次の問題が考えられる:「任意の平面的グラフと任意の数本の道に対して、その平面的グラフの任意の平面グラフが、それら数本の道がすべて直線分である直線的平面グラフに平面上で辺を交差させることなく変形できるための必要十分条件を求めよ。」 グラフを平面上に描いた図の中で、閉曲線と一致する部分をそのグラフの「閉路」と呼ぶ。閉路は、すべての頂点がちょうど2本の辺と接続している部分グラフである。閉路を含まない連結グラフを「木」と呼ぶ。木は平面的グラフである。上述のFaryの定理の拡張問題を一般の平面的グラフについて解決することは難しい。本論文では、木についてFaryの定理の拡張問題を解決した。