マルチグラフ

数学、より具体的にはグラフ理論において、マルチグラフとは、複数の辺（平行辺とも呼ばれる^[1]）、つまり同じ終端ノードを持つ辺を持つことが許されるグラフ である。したがって、2つの頂点は複数の辺で接続されることがある。

複数のエッジには 2 つの異なる概念があります。

• 独自の ID を持たないエッジ: エッジの ID は、接続する 2 つのノードによってのみ定義されます。この場合、「複数のエッジ」という用語は、これらの 2 つのノード間に同じエッジが複数回発生する可能性があることを意味します。
• 独自の ID を持つエッジ: エッジはノードと同じように基本的なエンティティです。複数のエッジが 2 つのノードを接続する場合、これらは異なるエッジです。

マルチグラフは、エッジが 2 つだけではなく任意の数のノードを接続できるグラフである ハイパーグラフとは異なります。

著者によっては、擬似グラフとマルチグラフという用語は同義語です。また、擬似グラフとはループが許可されているマルチグラフであると考える人もいます。

多重グラフGは、順序付きペア G  := ( V , E ) で あり、

• V頂点 またはノードの集合、​
• E は、エッジまたはラインと呼ばれる、順序付けられていない頂点のペアの多重集合です。

多重グラフGは順序付き三つ組 G  :=( V , E , r )であり、

• V頂点 またはノードの集合、​
• Eエッジまたは線の集合、​
• r  : E → {{ x , y } : x , y ∈ V }、各エッジにエンドポイントノードの順序付けられていないペアを割り当てます。

一部の著者は、マルチグラフがループ、つまり頂点をそれ自身に接続する辺を持つことを許可しているが^[2] 、他の著者はこれを擬似グラフと呼び、マルチグラフという用語はループがない場合に限って使用している^{[3] 。}

多重有向グラフは、複数の弧、つまり同じソースノードとターゲットノードを持つ弧を 持つことが許される有向グラフである。多重有向グラフGは、 G  := ( V , A ) の順序付きペアである。

• V頂点 またはノードの集合、
• 有向辺、弧、または矢印と呼ばれる頂点の順序付きペアの多重集合。

混合マルチグラフ G  := ( V , E , A ) は、混合グラフと同じ方法で定義できます。

多重ダイグラフまたはクィーバー Gは、順序付き4要素組 G  :=( V , A , s , t )で あり、

• V頂点 またはノードの集合、​
• エッジまたは線の集合、​​
• ${\displaystyle s:A\rightarrow V}$各エッジにソースノードを割り当て、
• ${\displaystyle t:A\rightarrow V}$各エッジにターゲット ノードを割り当てます。

この概念は、航空会社が提供する可能性のあるフライト接続をモデル化するために使用できます。この場合、マルチグラフは、都市を接続する有向平行エッジのペアを持つ有向グラフになり、これらの場所へのフライトとこれらの場所からのフライトの両方が可能であることを示します。

カテゴリー理論では、小さなカテゴリーは、結合合成法則と、合成の左と右のアイデンティティとして機能する各頂点の明確な自己ループを備えた多重有向グラフ（エッジが独自のアイデンティティを持つ）として定義できます。このため、カテゴリー理論では、グラフという用語は標準的に「多重有向グラフ」を意味するものと解釈され、カテゴリーの基礎となる多重有向グラフは基礎有向グラフと呼ばれます。

マルチグラフとマルチダイグラフも同様の方法でグラフラベル付けの概念をサポートします。ただし、この場合、用語に統一性はありません。

ラベル付きマルチグラフとラベル付きマルチダイグラフの定義は似ているため、ここでは後者のみを定義します。

定義 1 : ラベル付き多重有向グラフは、ラベル付きの弧 を持つラベル付きグラフです。

形式的には、ラベル付き多重有向グラフGはラベル付き頂点と弧を持つ多重グラフである。形式的には、8組の組で あり、${\displaystyle G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})}$

• ${\displaystyle V}$は頂点の集合であり、は弧の集合です。${\displaystyle A}$
• ${\displaystyle \Sigma _{V}}$利用可能な頂点と弧のラベルの有限のアルファベットであり、${\displaystyle \Sigma _{A}}$
• ${\displaystyle s\colon A\rightarrow \ V}$と弧の始点と終点を示す2つのマップです。${\displaystyle t\colon A\rightarrow \ V}$
• ${\displaystyle \ell _{V}\colon V\rightarrow \Sigma _{V}}$頂点と弧のラベル付けを記述した 2 つのマップです。${\displaystyle \ell _{A}\colon A\rightarrow \Sigma _{A}}$

定義 2 : ラベル付き多重有向グラフは、複数のラベル付き弧、つまり同じ端点と同じ弧ラベルを持つ弧を持つラベル付きグラフです (このラベル付きグラフの概念は、記事「グラフのラベル付け」で説明されている概念とは異なることに注意してください)。

• 多次元ネットワーク
• グラフ理論用語集
• グラフ理論

• Balakrishnan, VK (1997).グラフ理論. McGraw-Hill. ISBN 0-07-005489-4。
• Bollobás, Béla (2002).現代グラフ理論.数学大学院テキスト. 第184巻. Springer. ISBN 0-387-98488-7。
• チャートランド、ゲイリー、チャン、ピン（2012）。グラフ理論入門。ドーバー。ISBN 978-0-486-48368-9。
• Diestel, Reinhard (2010)。グラフ理論。Graduate Texts in Mathematics。第 173 巻 (第 4 版) 。Springer。ISBN 978-3-642-14278-9。
• グロス、ジョナサン L.、イエレン、ジェイ (1998)。グラフ理論とその応用。CRC プレス。ISBN 0-8493-3982-0。
• Gross, Jonathan L.; Yellen , Jay 編 (2003)。グラフ理論ハンドブック。CRC。ISBN 1-58488-090-2。
• ハラリー、フランク(1995)。グラフ理論。アディソン・ウェスリー。ISBN 0-201-41033-8。
• Janson, Svante ; Knuth, Donald E. ; Luczak, Tomasz; Pittel, Boris (1993). 「巨大コンポーネントの誕生」.ランダム構造とアルゴリズム. 4 (3): 231–358. arXiv : math/9310236 . Bibcode :1993math.....10236J. doi :10.1002/rsa.3240040303. ISSN  1042-9832. MR  1220220. S2CID  206454812.
• ウィルソン、ロバート A. (2002)。グラフ、カラーリング、および 4 色定理。オックスフォード サイエンス出版。ISBN 0-19-851062-4。
• ツヴィリンガー、ダニエル (2002)。CRC標準数学表と公式(第 31 版)。チャップマン & ホール/CRC。ISBN 1-58488-291-3。

•  この記事には、 Paul E. Blackのパブリック ドメイン マテリアルが組み込まれています。「Multigraph」。アルゴリズムとデータ構造の辞書。NIST 。