ハリングラフ

グラフ理論において、ハリングラフは平面グラフの一種で、木の葉を 閉路に接続して構築される。木には少なくとも4つの頂点が必要であり、どの頂点もちょうど2つの隣接頂点を持たない。木は平面上に描かれ、辺が交差しないようにする（これを平面埋め込みと呼ぶ）必要があり、閉路はこの埋め込み内で葉を時計回りの順序で接続する。したがって、閉路はハリングラフの外面を形成し、その中に木がある。^[1]

ハリングラフは、1971年に研究したドイツの数学者ルドルフ・ハリンにちなんで名付けられました。^[2] 立方ハリングラフ（各頂点がちょうど3つの辺に接するグラフ）は、1世紀以上前にカークマンによってすでに研究されていました。^[3] ハリングラフは多面体グラフであり、つまり、すべてのハリングラフを使用して凸多面体の頂点と辺を形成でき、それらから形成される多面体は屋根のない多面体またはドームと呼ばれています。

すべての Halin グラフには、すべての頂点を通るハミルトン サイクルと、グラフの頂点の数までのほぼすべての長さのサイクルがあります。Halin グラフは線形時間で認識できます。Halin グラフはツリー幅が狭いため、ハミルトン サイクルの検索など、他の種類の平面グラフでは難しい計算上の問題の多くが、Halin グラフでは迅速に解決できます。

星は、内部にちょうど 1 つの頂点を持つ木です。星に Halin グラフ構成を適用すると、ピラミッド(の辺) のグラフであるホイール グラフが生成されます。^[4]三角柱のグラフも Halin グラフです。長方形の面の 1 つが外部サイクルとなり、残りの辺が 4 つの葉、2 つの内部頂点、5 つの辺を持つ木を形成するように描くことができます。^[5]

フルヒトグラフは、非自明なグラフ自己同型を持たない5つの最小の立方グラフの1つであり、^[6]ハリングラフでもある。^[7]

すべての Halin グラフは3 連結であり、つまり、2 つの頂点を削除して残りの頂点を切断することはできません。これは辺最小 3 連結であり、その辺のいずれか 1 つを削除すると、残りのグラフは 3 連結ではなくなります。^[1] Steinitz の定理により、3 連結平面グラフとして、凸多面体の頂点と辺の集合として表すことができます。つまり、多面体グラフです。グラフを実現する多面体は、木の葉がすべて含まれる面が水平で、他のすべての面がその上に等傾斜で配置されるように選択できます。^[8]すべての多面体グラフと同様に、Halin グラフには、どの面を外面とするかという選択に至るまで、一意の平面埋め込みがあります。^[1]

すべてのハリングラフはハミルトングラフであり、グラフのすべての辺はハミルトン閉路に属します。さらに、どのハリングラフも、頂点を削除した後もハミルトングラフのままです。^[9] 次数2の頂点を持たないすべての木には、同じ親を共有する2つの葉が含まれているため、すべてのハリングラフには三角形が含まれます。特に、ハリングラフが三角形のないグラフや二部グラフになることは不可能です。^[10]

さらに強い言い方をすれば、すべてのハリングラフはほぼ汎巡回的であり、3からnまでのすべての長さのサイクルを持ち、1つの偶数長を除いて例外がある可能性がある。さらに、1つの辺を縮約しても、どのハリングラフもほぼ汎巡回的であり、3次の内部頂点を持たないすべてのハリングラフは汎巡回的である。^[12]

最大次数Δ( G )が4 より大きいHalin グラフGの発生彩色数はΔ ( G ) + 1である。^[13]これは、グラフの頂点vと、 vに接する辺eのすべてのペア ( v、e )を色付けするために必要な色の数であり、色付けに関する一定の制約に従う。頂点を共有するペアや辺を共有するペアは、同じ色を持つことはできない。さらに、ペア ( v、e ) は、 eのもう一方の端点を使用する別のペアと同じ色を持つことはできない。 Δ( G ) = 3または4の Halin グラフの場合、発生彩色数はそれぞれ5または6になることがある。^[14]

与えられたn頂点グラフが Halin グラフであるかどうかを線形時間でテストすることは、グラフの平面埋め込み (存在する場合) を見つけ、次にすべて次数 3 の少なくともn /2 + 1 個の頂点を持つ面が存在するかどうかをテストすることによって可能です。存在する場合、そのような面は最大で 4 つあり、それらのそれぞれについて、グラフの残りの部分がこの面の頂点を葉とする木を形成するかどうかを線形時間でチェックすることができます。一方、そのような面が存在しない場合、グラフは Halin ではありません。^{[15]あるいは、} n頂点とm辺を持つグラフがHalin である場合、それは平面で、3 連結であり、頂点数がグラフの回路階数 m − n + 1に等しい面を持ち、これらはすべて線形時間でチェックできます。^[16]線形時間でハリングラフを認識する他の方法としては、クールセルの定理の応用やグラフ書き換えに基づく方法などがあるが、どちらもグラフの平面埋め込みを知ることに依存していない。^[17]

すべての Halin グラフはtreewidth = 3です。 ^[18]したがって、最大独立集合 を見つけるなどの任意の平面グラフに対してNP 完全な多くのグラフ最適化問題は、動的計画法^[19]または Courcelle の定理を使用して Halin グラフ上で線形時間で解決できます。また、場合によっては (ハミルトン閉路の構築など) 直接アルゴリズムによって解決できます。^[17] ただし、特定のグラフの最大の Halin サブグラフを見つけること、特定のグラフのすべての頂点を含む Halin サブグラフが存在するかどうかをテストすること、または特定のグラフがより大きな Halin グラフのサブグラフであるかどうかをテストすることは NP 完全です。^[20]

1971年、ヘイリンは、最小3頂点連結グラフのクラスとしてヘイリングラフを導入した。グラフ内の各辺を削除すると、グラフの連結性が低下する。^[2]これらのグラフは、任意の平面グラフでは計算上不可能であった多くのアルゴリズムの問​​題が、これらのグラフ上で効率的に解けるという発見により、重要性を増した。^{[9] [16]}この事実は、後に、それらの低い木幅と、低い木幅のグラフ上でこれらの問題に効率的な解決策を提供するクールセルの定理などのアルゴリズムのメタ定理の結果であると説明された。^{[18] [19]}

これらのグラフに関するヘイリンの研究以前には、1856年にトーマス・カークマン^[3]が、1965年にハンス・ラデマッハーが、立方（または3正則）ヘイリングラフに関するグラフ列挙問題を研究していた。ラデマッハーはこれらのグラフを多面体ベースと呼んでいる。彼はこれを、 f面を持ち、そのうちの1面がf − 1辺を持つ立方多面体グラフとして定義している。 ^[21]この定義に当てはまるグラフは、まさに立方ヘイリングラフである。^[22]

ハリングラフと4頂点接続平面グラフの両方にハミルトン閉路が含まれているという事実に触発されて、ロヴァースとプラマー（1974）は、すべての4頂点接続平面グラフには全域ハリンサブグラフが含まれていると予想しました。ここで「全域」とは、サブグラフがより大きなグラフのすべての頂点を含むことを意味します。ロヴァース-プラマー予想は、2015年に無限に多くの反例の構成が発表されるまで未解決のままでした。^[23]

ハリングラフは、スカート付き木^[11]や屋根のない多面体^[9]と呼ばれることもあります。しかし、これらの名前は曖昧です。一部の著者は、葉を閉路に接続して木から形成された平面グラフを指すために「スカート付き木」という名前を使用していますが、木の内部の頂点の次数が3以上である必要はありません。^[24]また、「基底多面体」と同様に、「屋根のない多面体」という名前は、立方ハリングラフを指すこともあります。^[22]グラフがハリングラフである凸多面体は、ドームとも呼ばれています。^[25]

• Halin グラフ、グラフ クラスの包含に関する情報システム。