測地グラフ

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

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

例

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

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

計算の複雑さ

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

直径2

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

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

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

数学における未解決の問題:

強く正規な測地グラフは無限に存在するのでしょうか?

（数学における未解決の問題がさらに増える）

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

参考文献

^ ab Ore, Øystein (1962)、グラフ理論、Colloquium Publications、第38巻、プロビデンス、ロードアイランド州：アメリカ数学会、p. 104、ISBN 9780821810385、MR 0150753
^ Cornelsen, Sabine; Pfister, Maximilian; Förster, Henry; Gronemann, Martin; Hoffmann, Michael; Kobourov, Stephen; Schneck, Thomas (2020)、「測地グラフにおける最短経路の描画」、第 28 回国際グラフ描画およびネットワーク可視化シンポジウムの議事録、arXiv : 2008.07637
^ abcd 「測地グラフ」、グラフクラスとその包含に関する情報システム、 2020年9月14日取得
^ 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
^ Parthasarathy, KR; Srinivasan, N. (1982)、「測地ブロックの一般的な構成」、Journal of Combinatorial Theory、シリーズ B、33 (2): 121–136、doi :10.1016/0095-8956(82)90063-6、MR 0685061
^ Plesník, Ján (1977)、「測地グラフの 2 つの構成」、Mathematica Slovaca、27 (1): 65–71、MR 0460179
^ 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
^ abc ブロックハウス、A . ; Brouwer、AE (1988)、「直径 2 の測地図」、Geometriae Dedicata、25 (1–3): 527–533、doi :10.1007/BF00191941、MR 0925851、S2CID 189890651
^ Belousov, IN; Makhnev, AA (2006)、「 とその自己同型を持つ強力正則グラフについて」、 Doklady Akademii Nauk、410 (2): 151–155、MR 2455371 $\mu =1$
^ Deutsch, J.; Fisher, PH (2001)、「」を持つ強力正則グラフについて、European Journal of Combinatorics、22 (3): 303–306、doi : 10.1006/eujc.2000.0472、MR 1822718 $\mu =1$

[ore-1] Ore, Øystein (1962)、グラフ理論、Colloquium Publications、第38巻、プロビデンス、ロードアイランド州：アメリカ数学会、p. 104、ISBN 9780821810385、MR 0150753

[cghks-2] Cornelsen, Sabine; Pfister, Maximilian; Förster, Henry; Gronemann, Martin; Hoffmann, Michael; Kobourov, Stephen; Schneck, Thomas (2020)、「測地グラフにおける最短経路の描画」、第 28 回国際グラフ描画およびネットワーク可視化シンポジウムの議事録、arXiv : 2008.07637

[gc-3] 「測地グラフ」、グラフクラスとその包含に関する情報システム、 2020年9月14日取得

[sw-4] 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

[ps-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

[plesnik-6] Plesník, Ján (1977)、「測地グラフの 2 つの構成」、Mathematica Slovaca、27 (1): 65–71、MR 0460179

[stemple-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

[bb-8] ブロックハウス、A . ; Brouwer、AE (1988)、「直径 2 の測地図」、Geometriae Dedicata、25 (1–3): 527–533、doi :10.1007/BF00191941、MR 0925851、S2CID 189890651

[bm-9] ^ Belousov, IN; Makhnev, AA (2006)、「 とその自己同型を持つ強力正則グラフについて」、 Doklady Akademii Nauk、410 (2): 151–155、MR 2455371 $\mu =1$

[df-10] Deutsch, J.; Fisher, PH (2001)、「」を持つ強力正則グラフについて、European Journal of Combinatorics、22 (3): 303–306、doi : 10.1006/eujc.2000.0472、MR 1822718 $\mu =1$

例

関連するグラフクラス

計算の複雑さ

直径2

参考文献