グラフ理論の数学分野において、双向グラフ（ Edmonds & Johnson 1970によって導入）[ 1 ]とは、各辺の両端に独立した向き（方向、矢印）が与えられているグラフである。したがって、双向辺には3種類ある。両端の矢印が頂点に向かって外側を向いているもの、両方の矢印が頂点から離れて内側を向いているもの、そして一方の矢印が頂点から離れて反対側の端に向かっている一方で、もう一方の矢印が最初の矢印と同じ方向、つまり反対側の端から離れて自身の頂点に向かっているもの。
これら3種類の辺は、それぞれ外向的、内向的、有向的と呼ばれます。「有向」辺は、有向グラフにおける通常の有向辺と同じです。したがって、有向グラフは双向グラフの特別な種類です。
片方の端だけを持つ辺（半辺）も望ましい場合があります。これらの辺には矢印が1つだけあります。端のない辺（ルーズエッジ）には矢印はありません。半辺でもルーズエッジでもない辺は、通常の辺と呼ばれます。
有向グラフが通常の無向グラフの方向として見られるのと同様に、双方向グラフは符号付きグラフの方向として見なすことができます。
その他の意味
対称有向グラフ（つまり、すべての辺の逆辺も辺である有向グラフ）は、「双有向グラフ」と呼ばれることもあります。[ 2 ]
参照
参考文献
- ^エドモンズ、ジャック、ジョンソン、エリス L. (1970)、「マッチング：線形計画のよく解かれるクラス」、組み合わせ構造とその応用：カルガリーシンポジウムの議事録、1969年6月、ニューヨーク：ゴードンアンドブリーチ. Combinatorial Optimization — Eureka, You Shrink!、Springer-Verlag、Lecture Notes in Computer Science 2570、2003年、pp. 27–30、doi : 10.1007/3-540-36478-1_3に転載。
- ^メルホーン、カート、サンダース、ピーター（2008）、アルゴリズムとデータ構造：基本ツールボックス、シュプリンガーサイエンス＆ビジネスメディア、pp.49および170-171、ISBN 978-3-540-77978-0
 | このグラフ理論関連の記事はスタブです。不足している情報を追加してWikipediaに貢献してください。 |