近傍（グラフ理論）

グラフ理論において、グラフGにおける頂点vの近傍とは、 vに辺で接続されているすべての頂点（ vに隣接する頂点）によって誘導されるGの部分グラフ、すなわち、 vに隣接するすべての頂点とそれらを接続するすべての辺から構成されるグラフのことである。

近隣地域はしばしば で表されます${\displaystyle N_{G}(v)}$または（グラフが明確な場合）${\displaystyle N(v)}$同じ近傍表記は、対応する誘導部分グラフではなく、隣接する頂点の集合を参照するためにも使用できます。上記の近傍はv自体を含まず、より具体的にはvの開近傍です。v自体を含む近傍を定義することも可能で、これはvの閉近傍と呼ばれ、 で表されます。${\displaystyle N_{G}[v]}$⁠。特に条件を付けずに述べられている場合、その地域は開放されているものとみなされます。

近傍は、隣接リストや隣接行列表現を通して、コンピュータアルゴリズムにおけるグラフの表現に用いられる。また、近傍はグラフのクラスタリング係数にも用いられる。クラスタリング係数は、グラフの近傍の平均密度を表す指標である。さらに、多くの重要なグラフクラスは、その近傍の特性、あるいは近傍同士の関係性を表す対称性によって定義される。

孤立頂点は隣接する頂点を持たない。頂点vの次数は、 vに隣接する頂点の数である。ループ、すなわち頂点自身に接続する辺は特殊なケースであり、そのような辺が存在する場合、その頂点は自身の近傍に属する。

Gのすべての頂点が同じグラフHと同型な近傍を持つ場合、Gは局所的に Hであると言われ、Gのすべての頂点があるグラフ族Fに属する近傍を持つ場合、Gは局所的に Fであると言われます。^{[ 1 ]}例えば、図に示す正八面体グラフでは、各頂点は 4 つの頂点のサイクルと同型な近傍を持つため、正八面体は局所的にC ₄です。

例えば：

• 完全グラフK _nは、局所的にはK _n−1である。局所的に完全であるグラフは、完全グラフの非交和のみである。
• TuránグラフT ( rs , r )は局所的にT (( r -1) s , r -1)である。より一般的には、任意のTuránグラフは局所的にTuránである。
• すべての平面グラフは局所的に外平面である。しかし、すべての局所的に外平面なグラフが平面グラフであるとは限らない。
• グラフが三角形を含まないのは、それが局所的に独立である場合に限る。
• すべてのk彩色グラフは局所的に ( k -1) 彩色である。すべての局所的にk彩色グラフは彩色数を持つ。${\displaystyle O({\sqrt {kn}})}$[ ^{2 ]​}
• グラフ族Fが誘導部分グラフを取る操作に関して閉じている場合、F内のすべてのグラフは局所的にFになります。たとえば、すべての弦グラフは局所的に弦グラフであり、すべての完全グラフは局所的に完全であり、すべての比較可能性グラフは局所的に比較可能であり、すべての(k)-(超)-均質グラフは局所的に (k)-(超)-均質です。
• グラフは、すべての近傍がサイクルである場合に局所的に巡回的である。例えば、正八面体は唯一の連結局所的C ₄グラフであり、正二十面体は唯一の連結局所的C ₅グラフであり、次数 13 のペイリー グラフは局所的にC _{6である。K 4}以外の局所的に巡回的なグラフは、グラフの面がグラフのクリークとなるようなグラフの曲面への埋め込みであるホイットニー三角形分割の基礎となるグラフと全く同じである。^{[ 3 ]局所的に巡回的なグラフは、}${\displaystyle n^{2-o(1)}}$エッジ。^{[ 4 ]}
• クローフリーグラフとは、局所的に共三角形を含まないグラフのことです。つまり、すべての頂点について、その頂点の近傍の補グラフに三角形が含まれません。局所的にHであるグラフは、Hの独立数が最大で 2 である場合に限り、クローフリーです。例えば、正二十面体のグラフは、局所的にC ₅であり、C _{5 の}独立数が 2 であるため、クローフリーです。
• 局所線形グラフとは、すべての近傍が誘導マッチングであるグラフのことである。^{[ 5 ]}
• ジョンソングラフは局所的にグリッド状であり、各近傍はルークグラフである。^{[ 6 ]}

頂点の集合Aに対して、 Aの近傍は頂点の近傍の和集合であり、したがって、Aの少なくとも 1 つの要素に隣接するすべての頂点の集合である。 

グラフ内の頂点の集合Aは、 A内のすべての頂点がAの外部で同じ隣接頂点の集合を持つ場合、モジュールであると言われます。任意のグラフは、モジュールへの一意の再帰的分解、すなわちモジュラー分解を持ち、これはグラフから線形時間で構築できます。モジュラー分解アルゴリズムは、比較グラフの認識など、他のグラフアルゴリズムにも応用されています。

• マルコフブランケット
• ムーア地区
• フォン・ノイマン地区
• 2つ目の近隣問題
• 頂点図形、多面体における関連概念
• リンク（単体複体）、単体複体への近傍の一般化

• Cohen, Arjeh M. (1990)、「グラフ、建物、および関連する幾何学の局所的認識」（PDF）、Kantor, William M.、Liebler, Robert A.、Payne, Stanley E.、Shult, Ernest E. (編)、『有限幾何学、建物、および関連トピック：1988年7月17日～23日にコロラド州ピングリーパークで開催された建物と関連幾何学に関する会議の論文集』、Oxford Science Publications、Oxford University Press、pp. 85–94、MR 1072157  （特に89～90ページを参照）
• Fronček、Dalibor (1989)、「局所線形グラフ」、Mathematica Slovaca、39 (1): 3–6、hdl : 10338.dmlcz/136481、MR 1016323 
• ノラ・ハーツフェルド。リンゲル、ゲルハルト(1991)、「きれいな三角形分割」、Combinatorica、11 (2): 145–155、doi : 10.1007/BF01206358、S2CID 28144260 。
• Hell、Pavol (1978)、「与えられた近傍を持つグラフ I」、組み合わせの問題とグラフ、国際連合 CNRS、第 1 巻。 260、219 ～223ページ 。
• Larrión, F.; Neumann-Lara, V. ; Pizaña, MA (2002)、「Whitney 三角形分割、局所周長、および反復クリークグラフ」、Discrete Mathematics、258 ( 1–3 ): 123–135、doi : 10.1016/S0012-365X(02)00266-2。
• Malnič, Aleksander; Mohar, Bojan (1992)、「曲面の局所巡回三角形分割の生成」、Journal of Combinatorial Theory, Series B、56 (2): 147–164、doi : 10.1016/0095-8956(92)90015-P。
• Sedláček, J. (1983), "有限グラフの局所的性質について", Graph Theory, Lagów , Lecture Notes in Mathematics, vol.  1018, Springer-Verlag, pp. 242–247 , doi : 10.1007/BFb0071634 , ISBN  978-3-540-12687-4。
• Seress, Ákos; Szabó, Tibor (1995)、「サイクル近傍を持つ密グラフ」、Journal of Combinatorial Theory, Series B、63 (2): 281–293、doi : 10.1006/jctb.1995.1020。
• Wigderson, Avi (1983)、「近似グラフ彩色における性能保証の改善」、Journal of the ACM、30 (4): 729–735、doi : 10.1145/2157.2158、S2CID 32214512 。