測地グラフ
最短経路が一意であるグラフ

グラフ理論では、測地グラフは、2 つの頂点間に 一意の (重み付けされていない)最短経路が存在する無向グラフです。

測地グラフは1962年にオイステイン・オーレによって導入されました。彼は、測地グラフが木の性質（2つの頂点間の距離に関わらず、唯一の経路が存在する）を一般化していることに気づき、その特徴づけを求めました。[1]これらのグラフは多項式時間で認識できますが、「60年以上経った今でも、完全な特徴づけは未だに困難です」。[2]

例

あらゆる木[1]、あらゆる完全グラフ[3]、そしてあらゆる奇数長閉路グラフは測地的である。[4]

が測地グラフである場合、 のすべての辺を同じ奇数長のパスで置き換えると、別の測地グラフが生成されます。[5]完全グラフ の場合、より一般的なパスによる置き換えのパターンが可能です。各頂点 に非負の整数を選択し、各辺に頂点を追加することで細分化します。その結果得られる細分化された完全グラフは測地グラフであり、この方法ですべての測地グラフの細分化された完全グラフを得ることができます。[6] [7] G {\displaystyle G} G {\displaystyle G} f （ v ） {\displaystyle f(v)} v {\displaystyle v} あなた v {\displaystyle uv} f （ あなた ） + f （ v ） {\displaystyle f(u)+f(v)}

ブロックグラフ、測地グラフの特殊なケース
ピーターセングラフは、直径2の測地グラフの1つである。

グラフのすべての2連結成分が測地的であれば、グラフ自体も測地的である。特に、すべてのブロックグラフ（2連結成分が完備なグラフ）は測地的である。[3]同様に、サイクルグラフは長さが奇数のときに測地的であるため、サイクルの長さが奇数であるすべてのサボテングラフも測地的である。これらのサボテングラフは、すべてのサイクルの長さが奇数である連結グラフと全く同じである。より強く言えば、平面グラフが測地的であるためには、そのすべての2連結成分が奇数長さのサイクルか、 4頂点クリークの測地的細分のいずれかである必要がある。 [4]

計算の複雑さ

測地グラフは、グラフの各頂点から複数の最短経路を検出できる幅優先探索のバリエーションを用いることで、多項式時間で認識できる。測地グラフは、誘導4頂点サイクルグラフや誘導ダイヤモンドグラフを含むことはできない。なぜなら、これら2つのグラフは測地グラフではないからである。[3]特に、ダイヤモンドグラフを含まないグラフのサブセットとして、測地グラフはすべての辺が唯一の最大クリークに属するという性質を持つ。この文脈では、最大クリークは線とも呼ばれる。[8]したがって、最大クリーク、または最大重み付きクリークを見つける問題は、測地グラフの場合、すべての最大クリークをリストアップすることで多項式時間で解くことができる。誘導4頂点サイクルやダイヤモンドを持たないより広いクラスのグラフは「弱測地グラフ」と呼ばれる。これは、互いにちょうど2の距離にある頂点が唯一の最短経路を持つグラフである。[3]

直径2

直径2のグラフ（つまり、すべての頂点間の距離が最大でも2であるグラフ）の場合、測地グラフと弱測地グラフは一致する。直径2の測地グラフはすべて、以下の3つのタイプのいずれかである。

  • 全ての極大クリークが単一の共有頂点で結合されたブロックグラフ（風車グラフを含む）
  • パラメータ（隣接していない頂点のペアごとに共有される近傍の数）が1に等しい、または μ {\displaystyle \mu}
  • ちょうど 2 つの異なる頂点次数を持つグラフ。

強正則測地グラフには、5頂点サイクルグラフ、ピーターセングラフ、ホフマン・シングルトングラフなどがある。このようなグラフが持つべき性質に関する追加研究にもかかわらず、[9] [10]、これらのグラフがさらに存在するのか、あるいは無限に存在するのかは分かっていない。[8]

数学における未解決問題
強く正規な測地グラフは無限に存在するのでしょうか?
数学におけるさらなる未解決問題

直径2で2つの異なる次数を持つ測地グラフは、両方の次数の頂点からなる三角形を持つことはできない。任意の有限アフィン平面から、平面の点-線分接続グラフに、各2本の平行線に対応する頂点間の辺を追加することで、このようなグラフを構築できる。4つの点と6本の2点間直線を3組の平行線で結ぶ2元アフィン平面の場合、この構築の結果はピーターセングラフとなるが、高次の有限アフィン平面の場合は、2つの異なる次数を持つグラフが生成される。有限幾何学から測地グラフを構築する他の関連手法も知られているが、直径2で2つの異なる次数を持つ測地グラフの可能なすべてを網羅しているかどうかは不明である。[8]

参考文献

  1. ^ ab Ore, Øystein (1962), Theory of Graphs, Colloquium Publications, vol. 38, Providence, Rhode Island: American Mathematical Society, p. 104, ISBN 9780821810385、MR  0150753 {{citation}}:ISBN / 日付の非互換性（ヘルプ）
  2. ^ Cornelsen, Sabine; Pfister, Maximilian; Förster, Henry; Gronemann, Martin; Hoffmann, Michael; Kobourov, Stephen; Schneck, Thomas (2020)「測地グラフにおける最短経路の描画」第28回国際グラフ描画およびネットワーク可視化シンポジウム論文集、arXiv : 2008.07637
  3. ^ abcd 「測地グラフ」、グラフクラスとその包含に関する情報システム、 2020年9月14日取得
  4. ^ ab Stemple, Joel G.; Watkins, Mark E. (1968)、「平面測地グラフについて」、Journal of Combinatorial Theory、4 (2): 101– 117、doi : 10.1016/S0021-9800(68)80035-3、MR  0218267
  5. ^ Parthasarathy, KR; Srinivasan, N. (1982)、「測地ブロックの一般的な構成」、Journal of Combinatorial Theory、シリーズB、33 (2): 121– 136、doi :10.1016/0095-8956(82)90063-6、MR  0685061
  6. ^ Plesník, Ján (1977)、「測地グラフの 2 つの構成」、Mathematica Slovaca、27 (1): 65–71、MR  0460179
  7. ^ Stemple, Joel G. (1979)、「完全グラフに同相な測地グラフ」、第2回国際組合せ数学会議（ニューヨーク、1978年）、Annals of the New York Academy of Sciences、第319巻、pp.  512– 517、doi :10.1111/j.1749-6632.1979.tb32829.x、MR  0556062
  8. ^ abc ブロックハウス、A. ; Brouwer、AE (1988)、「直径 2 の測地図」、Geometriae Dedicata、25 ( 1–3 ): 527–533、doi :10.1007/BF00191941、MR  0925851、S2CID  189890651
  9. ^ Belousov, IN; Makhnev, AA (2006)、「とその自己同型を持つ強力正則グラフについて」、Doklady Akademii Nauk、410 (2): 151– 155、MR  2455371 μ ＝ 1 {\displaystyle \mu =1}
  10. ^ Deutsch, J.; Fisher, PH (2001)、「On stronger regular graphs with 」、European Journal of Combinatorics、22 (3): 303– 306、doi : 10.1006/eujc.2000.0472、MR  1822718 μ ＝ 1 {\displaystyle \mu =1}
「https://en.wikipedia.org/w/index.php?title=Geodetic_graph&oldid=1187760452」より取得