マルチグラフ

数学、特にグラフ理論において、多重グラフとは、複数の辺（平行辺とも呼ばれる^{[ 1 ]} ）を持つことが許されているグラフの ことである。つまり、同じ終点ノードを持つ辺のことである。したがって、2つの頂点は複数の辺で接続される可能性がある。

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

• 固有の識別情報を持たないエッジ：エッジの識別情報は、それが接続する2つのノードによってのみ定義されます。この場合、「多重エッジ」という用語は、同じエッジがこれら2つのノード間に複数回出現する可能性があることを意味します。
• 固有の識別子を持つエッジ：エッジはノードと同様に基本的なエンティティです。複数のエッジが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}$そして${\displaystyle t\colon A\rightarrow \ V}$これらは、弧の始点と終点の頂点を示す2つのマップです。
• $\displaystyle \ell _{V}\colon V\rightarrow \Sigma _{V}}$そして$\displaystyle \ell _{A}\colon A\rightarrow \Sigma _{A}}$これらは、頂点と弧のラベル付けを記述した2つのマップです。

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

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

• Balakrishnan, VK (1997).グラフ理論. McGraw-Hill. ISBN 0-07-005489-4。
• ボロバス、ベラ（2002）。現代グラフ理論。大学院数学テキストシリーズ。第 184巻。シュプリンガー。ISBN 0-387-98488-7。
• Chartrand, Gary ; Zhang, Ping (2012).グラフ理論入門. Dover. ISBN 978-0-486-48368-9。
• Diestel, Reinhard (2010).グラフ理論. 大学院数学テキストシリーズ. 第 173巻 (第4 版). Springer. ISBN 978-3-642-14278-9。
• グロス、ジョナサン・L.、イェレン、ジェイ（1998）。グラフ理論とその応用。CRC Press。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). "巨大成分の誕生". Random Structures and Algorithms . 4 (3): 231– 358. arXiv : math/9310236 . Bibcode : 1993math.....10236J . doi : 10.1002/rsa.3240040303 . ISSN 1042-9832 . MR 1220220 . S2CID 206454812 .   
• ウィルソン、ロバート A. (2002).グラフ、彩色、そして四色定理. オックスフォード科学出版. ISBN 0-19-851062-4。
• ズウィリンガー、ダニエル（2002）。CRC標準数学表と公式（第31 版）。チャップマン＆ホール/CRC。ISBN 1-58488-291-3。

•  この記事は、ポール・E・ブラック著「マルチグラフ」、『アルゴリズムとデータ構造の辞典』、NIST のパブリックドメイン資料を組み込んでいます。