発生率（グラフ）

頂点と接続辺のペアは接続を形成します。例えば、 というラベルの付いた接続はペア です。 ${\displaystyle (u,e)}$ ${\displaystyle u}$ ${\displaystyle e}$ ${\displaystyle a}$ ${\displaystyle (A,1)}$

グラフ理論では、頂点が辺が接続する 2 つの頂点のうちの 1 つである場合、その頂点は辺に接続しています。

入射角とは、 が頂点でが に接続する辺であるペアです。^[1] 2 つの異なる入射角と が隣接している場合、かつその場合のみ、または 、あるいは辺がまたは に等しい場合です。 ${\displaystyle (u,e)}$ ${\displaystyle u}$ ${\displaystyle e}$ ${\displaystyle u}$ ${\displaystyle (u,e)}$ ${\displaystyle (v,f)}$ ${\displaystyle u=v}$ ${\displaystyle e=f}$ ${\displaystyle uv}$ ${\displaystyle e}$ ${\displaystyle f}$

グラフは、順序付き3つ組として正式に定義できます。ここで、は頂点の集合、は辺の集合、は各辺を頂点のペアにマッピングする接続関数（または接続写像）です。 ^{[2] [3]}辺 について、 の場合、およびは辺 の端点（または終点）と呼ばれ、辺 は頂点およびに接続されていると言われます。 ${\displaystyle (V,E,\psi )}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle \psi }$ ${\displaystyle e\in E}$ ${\displaystyle \psi (e)=(u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle e}$ ${\displaystyle e}$ ${\displaystyle u}$ ${\displaystyle v}$

グラフは接続構造 として指定することもできます。ここで、は「ポイント」（頂点）の集合、は「ブロック」（エッジ）の集合、はそれらの間の接続関係です。^[4] ${\displaystyle S=(P,B,I)}$ ${\displaystyle P}$ ${\displaystyle B}$ ${\displaystyle I}$

発生行列

自己ループのない無向グラフの接続行列は行列 であり、は頂点の数、は辺の数である。行は頂点に対応し、列は辺に対応し、 ${\displaystyle G=(V,E)}$ ${\displaystyle n\times m}$ ${\displaystyle A=a_{ij}}$ ${\displaystyle n=|V|}$ ${\displaystyle m=|E|}$

${\displaystyle a_{ij}=\left\{{\begin{array}{rl}\,1&{\text{if vertex }}v_{i}{\text{ is incident with edge }}e_{j},\\0&{\text{otherwise.}}\end{array}}\right.}$

接続行列の各列には、ちょうど2つの1（辺の両端点に対応）が含まれます。したがって、すべての行ベクトルの和は2を法とする零ベクトルに等しく、行は（2つの要素を持つ体）に対して線形従属となります。これは、 を意味します。^[4]頂点を持つ連結グラフにおいて、の部分行列が非特異行列であるためには、その列に対応する辺がの全域木を形成する必要があります。^[4] ${\displaystyle \mathrm {GF} (2)}$ ${\displaystyle \mathrm {rank} (A)\leq n-1}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle (n-1)\times (n-1)}$ ${\displaystyle A(G)}$ ${\displaystyle n-1}$ ${\displaystyle G}$

有向グラフには接続行列の別の形式が存在し、エントリは頂点から出るエッジ用になる場合があります (作成者の好みの規則に応じて、その逆の場合もあります)。 ${\displaystyle -1}$

発生率の色分け

グラフの発生彩色とは、グラフの各発生点に色を割り当て、隣接する発生点が異なる色で彩色されることである。発生彩色数（または発生彩色数）とは、グラフの発生彩色に必要な最小の色数である。^[1]これは、グラフの各辺を1回細分化することで得られるグラフの強辺彩色に相当する。 ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \chi _{i}(G)}$ ${\displaystyle G}$ ${\displaystyle G}$

グラフが与えられた色数で発生彩色可能かどうかを判断することはNP完全である。具体的には、LiとTuは2008年に、半立方グラフ（すべての頂点の次数が1または3であるグラフ）が4発生彩色可能かどうかを判断することはNP完全であることを示した。^{[5]これは、一般的なグラフにおいて発生彩色数を決定することが}NP困難であることを意味する。

発生率ポセット

グラフの接続順序集合は、半順序集合であり、半順序は接続関係により定義されます。 に対して、が頂点であり がに接続する辺である場合に限り、においてが成り立ちます。^[6]グラフの順序次元（または接続次元 ）は、と表記され、その交点が接続関係に等しい順序の総数の最小値です。この概念は、グラフ構造と半順序集合の理論を結び付けます。シュナイダーによる基本的な結果は、平面グラフを接続次元の観点から特徴付けます。 ${\displaystyle G=(V,E)}$ ${\displaystyle P=(X,P)}$ ${\displaystyle X=V\cup E}$ ${\displaystyle x,y\in X}$ ${\displaystyle x<y}$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle G}$ ${\displaystyle \mathrm {dim} (G)}$ ${\displaystyle V\cup E}$

定理: ^[6]グラフ が平面的である場合、かつその場合のみグラフは平面的である。 ${\displaystyle G}$ ${\displaystyle \mathrm {dim} (G)\leq 3}$

この特徴付けは、平面グラフのいくつかの古典的な性質を示唆する。例えば、すべての平面グラフの樹状度が最大3であるという代替証明を与え、頂点座標が接続ポセットの実現体における全順序から導かれる純粋に組合せ論的な意味を持つ平面上の直線埋め込みの存在を保証する。 ^[6]接続ポセットの次元は、様々なグラフクラスについて研究されてきた。例えば、トロッターは、彼の調査研究において、特定の幾何学的および組合せ論的構造から生じるグラフはしばしば有界な接続次元を持つことを示し、このパラメータを次元理論や交差グラフにおけるより広範な問題に結び付けた。^[7]

参考文献

1. Brualdi, Richard A.; Massey, Jennifer J. Quinn (1993). 「グラフの発生と強エッジ着色」.離散数学. 122 ( 1–3 ): 51–58 . doi :10.1016/0012-365X(93)90286-3.
2. Xu, Junming (2003). グラフの理論と応用(PDF) . ネットワーク理論と応用. ニューヨーク: Springer. pp.  1– 2. doi :10.1007/978-1-4419-8698-6. ISBN 978-1-4020-7540-7。
3. Al-Hasanat, Bilal N.; Al-Hasanat, Ahmad S. (2019). 「順序グラフ：有限群の新しい表現」（PDF） .国際数学・コンピュータサイエンスジャーナル. 14 (4): 809– 819.
4. Kabashi, Faton; Jusufi, Azir (2021年10月29日). 「接続行列とグラフ理論におけるその応用の一部」. 2021 UBT国際会議. pp.  367– 372.
5. Li, Xueliang; Tu, Jianhua (2008). 「半立方グラフの4入射色可能性のNP完全性」.離散数学. 308 (7): 1334– 1340. doi :10.1016/j.disc.2007.03.076.
6. Schnyder, Walter (1989). 「平面グラフとポセット次元」. Order . 5 (4): 323– 343. doi :10.1007/BF00353652.
7. Trotter, William T. (1996). 「グラフと半順序集合：最近の成果と新たな方向性」（PDF） . Congressus Numerantium . 116 : 253– 278.

外部リンク

エリック・ソペナによる「インシデンス」ぬり絵

Retrieved from "https://en.wikipedia.org/w/index.php?title=Incidence_(graph)&oldid=1321836373"