二重連結グラフ

グラフ理論では、2重連結グラフは連結された「分離不可能な」グラフであり、頂点を1 つ削除してもグラフは連結されたままになります。したがって、2 重連結グラフには連結頂点がありません。

2 連結であるという特性は、2 頂点の完全グラフが通常は 2 連結であるとは見なされない ことを除いて、2 連結であることと同じです。

このプロパティは、単一のエッジ(または接続) が削除されたときに切断されるのを防ぐために、 2 倍の冗長性を持つグラフを維持する場合に特に役立ちます。

この冗長性の特性のため、二重連結グラフの使用はネットワークの分野で非常に重要です (ネットワーク フローを参照)。

2連結 無向グラフは、単一の頂点 (およびその接続辺) を削除しても切断された部分に分割されない連結グラフです。

2連結 有向グラフとは、任意の 2 つの頂点vとwに対して、 vとw以外に共通の頂点を持たない、vからwへの2 つの有向パスが存在するグラフです。

• 
  4つの頂点と4つの辺を持つ2連結グラフ
• 
  2 重連結ではないグラフ。頂点 x を削除するとグラフが切断されます。
• 
  5つの頂点と6つの辺を持つ2連結グラフ
• 
  2 重連結ではないグラフ。頂点 x を削除するとグラフが切断されます。

すべての 2 連結グラフは、サイクルにパスを追加することによって帰納的に構築できます (Diestel 2016、p. 59)。

• 二重連結成分

• Eric W. Weisstein。「二重連結グラフ」。MathWorld より - Wolfram Web リソース。http://mathworld.wolfram.com/BiconnectedGraph.html
• Paul E. Black、「biconnected graph」、Dictionary of Algorithms and Data Structures [online]、Paul E. Black 編、米国国立標準技術研究所。2004 年 12 月 17 日。(本日アクセス) 入手可能: https://xlinux.nist.gov/dads/HTML/biconnectedGraph.html
• Diestel、Reinhard (2016)、グラフ理論 (第 5 版)、ベルリン、ニューヨーク: Springer-Verlag、ISBN 978-3-662-53621-6。

• jBPT ライブラリ内の二重連結コンポーネントのツリー Java 実装 (BCTree クラスを参照)。