近傍（グラフ理論）

グラフ理論では、グラフ内の頂点vの隣接頂点とは、辺によってvに接続された頂点のことです。グラフG内の頂点vの近傍とは、 vに隣接するすべての頂点によって誘導されるGのサブグラフ、つまり、vに隣接する頂点と、 vに隣接する頂点を接続するすべての辺で構成されるグラフです。

近傍は、多くの場合⁠ ⁠${\displaystyle N_{G}(v)}$または (グラフが明確な場合) ⁠ ⁠ と${\displaystyle N(v)}$表記されます。同じ近傍表記法は、対応する誘導サブグラフではなく、隣接する頂点の集合を指すためにも使用できます。上記の近傍にはv自体は含まれず、より具体的にはvの開近傍です。v自体が含まれる近傍を定義することも可能で、これは閉近傍と呼ばれ、 ⁠ ⁠と表記されます。何の修飾もなく述べられる場合、近傍は開いているとみなされます。 ${\displaystyle N_{G}[v]}$

近傍は、隣接リストと隣接行列表現を介して、コンピュータ アルゴリズムでグラフを表すために使用される場合があります。近傍は、グラフのクラスタリング係数にも使用されます。クラスタリング係数は、近傍の平均密度の尺度です。さらに、多くの重要なグラフ クラスは、近傍の特性によって、または近傍同士を関連付ける対称性によって定義される場合があります。

孤立した頂点には隣接する頂点がありません。頂点の次数は隣接する頂点の数に等しくなります。特殊なケースとして、頂点を自分自身に接続するループがあります。このようなエッジが存在する場合、頂点は自身の近傍に属します。

G内のすべての頂点が同じグラフHに同型の近傍を持つ場合、G は局所的に Hであるとされ、G内のすべての頂点が何らかのグラフファミリーFに属する近傍を持つ場合、G は局所的に Fであるとされます。^[1]たとえば、図に示す八面体グラフでは、各頂点は4つの頂点のサイクルと同型の近傍を持つため、八面体は局所的にC ₄です 。

例えば：

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

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

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

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

• 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、vol. 260、219–223ページ。
• Larrión, F.; Neumann-Lara, V .; Pizaña, MA (2002)、「ホイットニー三角分割、局所内周、反復クリークグラフ」、離散数学、258 (1–3): 123–135、doi : 10.1016/S0012-365X(02)00266-2。
• マルニッチ、アレクサンダー;モハル、ボヤン(1992)、「表面の局所的巡回三角形分割の生成」、組み合わせ理論ジャーナル、シリーズ B、56 (2): 147–164、doi :10.1016/0095-8956(92)90015-P。
• Sedláček, J. (1983)、「有限グラフの局所特性について」、グラフ理論、Lagów、数学講義ノート、vol. 1018、Springer-Verlag、pp. 242–247、doi :10.1007/BFb0071634、ISBN 978-3-540-12687-4。
• セレス、アコス; サボー、ティボル (1995)、「サイクル近傍を持つ密なグラフ」、組み合わせ理論ジャーナル、シリーズ 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。