Loading article…
数学のグラフ理論の領域において、双方向グラフ（Edmonds & Johnson 1970 により導入）[1]は、各辺の両端に独立した向き（または方向、矢印）が与えられているグラフである。したがって、双方向辺には 3 種類ある。両端で矢印が外側、つまり頂点に向かっているもの、両方の矢印が内側、つまり頂点から離れて向いているもの、そして 1 つの矢印が頂点から離れて反対側の端に向かっており、もう 1 つの矢印が最初の矢印と同じ方向、つまり反対側の端から離れて自身の頂点に向かっているものである。
これら 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