二部グラフ

閉路のない二部グラフの例
m = 5、n = 3の完全二部グラフ
Heawoodグラフは二部グラフです。

数学の分野であるグラフ理論において、二部グラフ（またはバイグラフ）とは、頂点が互いに素で独立した2つの集合とに分割できるグラフのことである。つまり、すべての辺がグラフ内の1つの頂点をグラフ内の1つの頂点と接続している。頂点集合とは通常、グラフの「部分」と呼ばれる。同様に、二部グラフとは、奇数長の閉路を含まないグラフのことである。[ 1 ] [ 2 ]

2 つの集合と は、グラフを 2 色で彩色したものと考えることができます。つまり、すべてのノードを青で彩色し、すべてのノードを赤で彩色すると、グラフ彩色問題で要求されるように、各エッジのエンドポイントは異なる色になります。[ 3 ] [ 4 ]一方、このような彩色は、三角形などの非二部グラフでは不可能です。1 つのノードを青、別のノードを赤に彩色すると、三角形の 3 番目の頂点は両方の色の頂点に接続されるため、どちらの色も割り当てることができなくなります。

二部グラフの分割が部分 と で、グラフの辺 で表される場合、二部グラフを と表記することがよくあります。二部グラフが連結されていない場合、複数の二分割が存在する可能性があります。[ 5 ]この場合、 という表記は、アプリケーションで重要になる可能性のある特定の二分割を指定するのに役立ちます。、つまり 2 つの部分集合の基数が等しい場合、 はバランス型二部グラフと呼ばれます。[ 3 ]二分割の同じ側にあるすべての頂点の次数が等しい場合、は双正則と呼ばれます。

例

異なる2つのオブジェクトクラス間の関係をモデル化する場合、二部グラフは自然に生じることが多い。例えば、サッカー選手とクラブのグラフでは、選手が過去にそのクラブでプレーしたことがある場合、その選手とクラブの間にエッジが設定される。これは、ソーシャルネットワーク分析で用いられる二部グラフの一種であるアフィリエーションネットワークの自然な例である。[ 6 ]

二部グラフが自然に現れるもう一つの例として、鉄道最適化問題（NP完全）が挙げられます。この問題では、列車とその停車駅の時刻表が入力として与えられ、すべての列車が少なくとも1つの駅に停車するように、可能な限り小さな駅の集合を見つけることが目標となります。この問題は、各列車と各駅を頂点とし、駅とその駅に停車する列車のペアを辺とする二部グラフの支配集合問題としてモデル化できます。 [ 7 ]

より抽象的な例としては次のようなものがあります。

プロパティ

キャラクター設定

二部グラフはいくつかの異なる方法で特徴付けることができます。

ケーニヒの定理と完全グラフ

二部グラフでは、最小頂点被覆の大きさは最大マッチングの大きさに等しい。これがケーニッヒの定理である。[ 17 ] [ 18 ]この定理の別の同等な形式は、最大独立集合の大きさと最大マッチングの大きさの合計が頂点の数に等しいというものである。孤立した頂点のないグラフでは、最小辺被覆の大きさと最大マッチングの大きさの合計が頂点の数に等しい。[ 19 ]この等式をケーニッヒの定理と組み合わせると、二部グラフでは最小辺被覆の大きさが最大独立集合の大きさに等しく、最小辺被覆の大きさと最小頂点被覆の大きさの合計が頂点の数に等しいという事実が導かれる。

関連する結果の別のクラスは、完全グラフに関するものである。すなわち、すべての二部グラフ、すべての二部グラフの補グラフ、すべての二部グラフの線グラフ、およびすべての二部グラフの線グラフの補グラフはすべて完全である。二部グラフの完全性は簡単にわかる (彩色数は 2 で、最大クリークサイズも 2) が、二部グラフの補グラフの完全性はそれほど自明ではなく、ケーニヒの定理をもう一度言い換えたものである。これは、完全グラフの最初の定義のきっかけとなった結果の 1 つであった。[ 20 ]完全グラフの線グラフの補グラフの完全性はケーニヒの定理をもう一度言い換えたものであり、線グラフ自体の完全性は、すべての二部グラフにはその最大次数に等しい色数を使用した 辺彩色があるという、ケーニヒの以前の定理を言い換えたものである。

強いパーフェクトグラフ定理によれば、パーフェクトグラフは二部グラフに似た禁制グラフ特性を持つ。すなわち、グラフが二部グラフであるためには、サブグラフとして奇数サイクルを持たないことが必要であり、グラフがパーフェクトであるためには、誘導サブグラフとして奇数サイクルまたはその補グラフを持たないことが必要である。二部グラフ、二部グラフの線グラフ、およびそれらの補グラフは、強いパーフェクトグラフ定理の証明で使用されるパーフェクトグラフの5つの基本クラスのうち4つを形成する。[ 21 ]したがって、二部グラフの任意のサブグラフも、奇数サイクルを獲得できないため、二部グラフである。[ 22 ]

程度

頂点において、隣接する頂点の数は次数と呼ばれ、 と表記される。二部グラフの次数の総和の公式は[ 23 ]で表される。

二部グラフの次数列は、2つの部分と の次数を含むリストのペアです。例えば、完全二部グラフK 3,5の次数列は です。同型二部グラフは同じ次数列を持ちます。しかし、次数列は一般に二部グラフを一意に識別するものではなく、場合によっては、同型でない二部グラフが同じ次数列を持つことがあります。

二部グラフ実現問題とは、与えられた2つの自然数リストを次数列とする単純な二部グラフを見つける問題である。（末尾のゼロは、適切な数の孤立した頂点を有向グラフに追加することで簡単に実現できるため、無視できる。）

ハイパーグラフと有向グラフとの関係

二部グラフの双隣接行列は、隣接する頂点のペアごとに1、隣接しない頂点ごとに0を持つ、サイズが(0,1)の行列です。 [ 24 ]双隣接行列は、二部グラフ、ハイパーグラフ、有向グラフ間の同値性を記述するために使用できます。

ハイパーグラフは、無向グラフと同様に頂点と辺を持つ組み合わせ構造ですが、辺は必ずしも2つの端点を持つ必要はなく、任意の頂点集合をとることができます。二部グラフは、Uがハイパーグラフの頂点集合、Vがハイパー辺集合であり、Eがハイパーグラフの頂点vからハイパーグラフの辺eへの辺を含む（ただし、 vはeの端点の1つである）ようなハイパーグラフをモデル化するために使用できます。この対応関係において、二部グラフの双方向隣接行列は、対応するハイパーグラフの接続行列と正確に一致します。二部グラフとハイパーグラフの対応関係の特別な例として、任意のマルチグラフ（同じ2つの頂点間に2つ以上の辺が存在するグラフ）は、いくつかのハイパー辺が等しい端点の集合を持ち、多重隣接を持たず、二部グラフの片側の頂点がすべて次数2であるような二部グラフで表されるハイパーグラフとして解釈することができる。[ 25 ]

隣接行列の同様の再解釈は、有向グラフ（与えられた数のラベル付き頂点を持ち、自己ループを許容する）と、二分グラフの両側に同じ数の頂点を持つバランスの取れた二部グラフとの間の1対1の対応を示すために使用することができる。なぜなら、 n頂点を持つ有向グラフの隣接行列は、サイズ の任意の(0,1)行列にすることができ、これは、二分グラフの各側にn頂点を持つ二部グラフの隣接行列として再解釈することができるからである。 [ 26 ]この構成では、二部グラフは有向グラフの 二部二重被覆である。

アルゴリズム

二分性のテスト

深さ優先探索(DFS)を使用すると、グラフが二部グラフであるかどうかをテストし、二部グラフの場合は 2 色、そうでない場合は奇数サイクルを線形時間で返すことができます。基本的な考え方は、DFS フォレスト内の各頂点に親の色と異なる色を割り当て、深さ優先探索フォレストの事前順序トラバーサルで色を割り当てることです。これにより、頂点をその親に接続するエッジで構成されるスパニング フォレストの 2 色彩が必然的に提供されますが、フォレスト以外のエッジの一部は適切に色付けされない可能性があります。DFS フォレストでは、フォレスト以外のエッジの 2 つのエンドポイントのうちの 1 つは、もう一方のエンドポイントの祖先であり、深さ優先探索でこのタイプのエッジが検出されると、これら 2 つの頂点が異なる色を持っていることがチェックされます。そうでない場合、祖先から子孫への森のパスと、誤って色付けされた辺は奇数サイクルを形成し、アルゴリズムはグラフが二部グラフではないという結果と共にこの奇数サイクルを返します。しかし、アルゴリズムがこのタイプの奇数サイクルを検出せずに終了した場合、すべての辺は適切に色付けされているはずであり、アルゴリズムはグラフが二部グラフであるという結果と共に、その色付けを返します。[ 27 ]

あるいは、DFSの代わりに幅優先探索を用いて同様の手順を用いることもできる。この場合も、各ノードには探索フォレスト内の親ノードと反対の色が幅優先順に与えられる。頂点が色付けされた際に、その頂点を既に同じ色で色付けされた頂点に接続する辺が存在する場合、この辺と、幅優先探索フォレスト内の2つの端点をそれらの最下位共通祖先に接続するパスは奇数閉路を形成する。このようにしてアルゴリズムが奇数閉路を発見せずに終了した場合、適切な色付けが発見されたとみなされ、グラフが二部グラフであると安全に結論付けることができる。[ 28 ]

ユークリッド平面上の線分やその他の単純な図形の交差グラフでは、グラフ自体が最大 個の辺を持つ場合でも、グラフが二部グラフであるかどうかをテストし、2色または奇数サイクルを時間内に返すことができます。[ 29 ]

奇数サイクル横断

サイズ 2 の奇数サイクル横断を持つグラフ: 下の 2 つの青い頂点を削除すると、二部グラフが残ります。

奇数サイクル横断は、グラフG = ( V , E )と数kが与えられたとき、 Gから削除すると結果として得られるグラフが二部グラフになるようなk個の頂点の集合が存在するかどうかを問う NP 完全なアルゴリズム問題である。 [ 30 ]この問題は固定パラメータで扱える。つまり、実行時間がグラフのサイズの多項式関数にkのより大きな関数を乗じたものに制限されるアルゴリズムが存在する。[ 31 ]奇数サイクル横断という名前は、グラフが二部であるためには奇数サイクルが存在しないということに由来する。したがって、二部グラフを得るためにグラフから頂点を削除するには、「すべての奇数サイクルをヒットする」、つまりいわゆる奇数サイクル横断集合を見つける必要がある。図では、グラフ内のすべての奇数サイクルに青い頂点（一番下）が含まれているため、これらの頂点を削除するとすべての奇数サイクルが削除され、二部グラフが残る。

辺二分化問題は、グラフを二分化するためにできるだけ少ない辺を削除するアルゴリズム問題であり、グラフ修正アルゴリズムにおいても重要な問題です。この問題も固定パラメータで扱いやすく、時間で解くことができます。 [ 32 ]ここで、kは削除する辺の数、mは入力グラフの辺の数です。

マッチング

グラフにおけるマッチングとは、その辺のサブセットであり、どの2つも端点を共有しない。マッチングに関する多くのアルゴリズム問題では、最大マッチング（できるだけ多くの辺を使うマッチングを見つける）、最大重みマッチング、安定結婚など、多項式時間アルゴリズムが知られている。[ 33 ]多くの場合、マッチング問題は非二部グラフよりも二部グラフの方が簡単に解ける。[ 34 ]また、最大カーディナリティマッチングのためのホップクロフト・カープアルゴリズム[ 35 ]など、多くのマッチングアルゴリズムは二部入力に対してのみ正しく動作する。

簡単な例として、ある集団の人々が複数の職種の中から求職活動を行っているが、全員がすべての職種に適しているわけではないと仮定する。この状況は、各求職者と各適職をそれぞれ辺で結ぶ二部グラフとしてモデル化できる。[ 36 ]完全マッチングとは、すべての求職者の満足度とすべての求人への充足を同時に実現する方法である。ホールの結婚定理は、完全マッチングを可能にする二部グラフの特徴付けを提供する。全米レジデントマッチングプログラムは、グラフマッチング手法を用いて、米国の医学生求職者と病院レジデント職の求職活動におけるこの問題を解決している。[ 37 ]

ダルメージ・メンデルゾーン分解は二部グラフの構造分解であり、最大マッチングを見つけるのに役立ちます。[ 38 ]

追加のアプリケーション

二部グラフは現代の符号理論において、特に通信路から受信した符号語を復号するために広く用いられている。ファクターグラフやタナーグラフはその代表例である。タナーグラフは二部グラフであり、二分グラフの一方の頂点は符号語の数字を表し、もう一方の頂点は符号語において誤りなく合計がゼロになると予想される数字の組み合わせを表す。[ 39 ]ファクターグラフは、LDPC符号やターボ符号の確率的復号に用いられる、密接に関連したビリーフネットワークである。[ 40 ]

コンピュータサイエンスにおいて、ペトリネットは並行システムの分析とシミュレーションに用いられる数学的モデリングツールです。システムは、2つのノードセットを持つ二部有向グラフとしてモデル化されます。「場所」ノードセットはリソースを保持し、イベントノードセットはリソースを生成または消費します。ノードとエッジには、システムの動作を制約する追加の制約が存在します。ペトリネットは、二部有向グラフの特性やその他の特性を利用することで、システムの挙動を数学的に証明すると同時に、システムのシミュレーションを容易に実装することを可能にします。[ 41 ]

射影幾何学において、レヴィグラフは二部グラフの一種であり、ある配置における点と直線の交差をモデル化するために用いられる。2本の直線は最大でも1点で交わり、2本の直線は1本の直線で結ばれるという点と直線の幾何学的性質に対応して、レヴィグラフには長さ4の閉路が必ず含まれず、したがってその内周は6以上でなければならない。[ 42 ]

参照

参考文献

  1. ^ Diestel, Reinard (2005),グラフ理論,大学院数学テキスト, Springer, ISBN 978-3-642-14278-9、2011年4月9日にオリジナルからアーカイブされ、2012年2月27日に取得
  2. ^ Asratian, Armen S.; Denley, Tristan MJ; Häggkvist, Roland (1998), Bipartite Graphs and their Applications , Cambridge Tracts in Mathematics, vol. 131, Cambridge University Press, ISBN 9780521593458。
  3. ^ a b cアスラティアン、デンリー、ヘグクヴィスト (1998)、p. 7.
  4. ^ a b cシャイナーマン、エドワード・R.（2012）、数学：離散入門（第3版）、Cengage Learning、p.363、ISBN 9780840049421。
  5. ^ Chartrand, Gary ; Zhang, Ping (2008)、「クロマティックグラフ理論、離散数学とその応用」第53巻、CRC Press、p. 223、ISBN 9781584888000。
  6. ^ワッサーマン、スタンレー、ファウスト、キャサリン（1994）、ソーシャルネットワーク分析：方法と応用、社会科学における構造分析、第8巻、ケンブリッジ大学出版局、pp.  299– 302、ISBN 9780521387071。
  7. ^ Niedermeier, Rolf (2006), 「固定パラメータアルゴリズムへの招待」、オックスフォード数学とその応用講義シリーズ、オックスフォード大学出版局、pp.  20– 21、ISBN 978-0-19-856607-6
  8. ^ソイファー、アレクサンダー（2008年）、数学ぬりえブック、シュプリンガー・フェアラーク、pp.  136– 137、ISBN 978-0-387-74640-1この結果は「二色定理」と呼ばれることもあるが、ソイファーはこれを、四色定理の誤った証明を含むアルフレッド・ケンペの1879年の有名な論文に起因するとしている。
  9. ^ Bandelt, H.-J.; Chepoi, V.; Eppstein, D. (2010)「有限および無限平方グラフの組合せ論と幾何学」、SIAM Journal on Discrete Mathematics、24 (4): 1399– 1440、arXiv : 0905.4537、doi : 10.1137/090760301、S2CID 10788524 。
  10. ^ Asratian、Denley、Häggkvist (1998)、p. 11.
  11. ^ Archdeacon, D. ; Debowsky, M. ; Dinitz, J. ; Gavlas, H. (2004) 「完全二部グラフにおけるサイクルシステムから1因子を引いたもの」、離散数学、284 ( 1–3 ): 37– 43、doi : 10.1016/j.disc.2003.11.021。
  12. ^ Ovchinnikov, Sergei (2011), Graphs and Cubes , Universitext, Springer特に第5章「部分立方体」の127～181ページを参照してください。
  13. ^ Asratian, Denley & Häggkvist (1998)、定理2.1.3、p. 8。Asratianらはこの特徴づけを1916年のデーネス・ケーニヒの論文に帰している。無限グラフの場合、この結果は選択公理を必要とする。
  14. ^ Bang-Jensen, Jørgen; Gutin, Gregory (2001), Digraphs: Theory, Algorithms and Applications (PDF) (第1版), Springer, p. 25, ISBN 9781852332686、2023年1月2日にオリジナルからアーカイブ（PDF）され、2023年1月2日に取得
  15. ^ Woodall, DR (1990)、「マッキーのオイラー二部特性の証明」、離散数学、84 (2): 217– 220、doi : 10.1016/0012-365X(90)90380-Z、MR 1071664 
  16. ^ビッグス、ノーマン（1994）、代数グラフ理論、ケンブリッジ数学図書館（第2版）、ケンブリッジ大学出版局、p.53、ISBN 9780521458979。
  17. ^ Kőnig、Dénes ( 1931)、「Gráfok és mátrixok」、Matematikai és Fizikai Lapok、38 : 116–119。
  18. ^ Gross, Jonathan L.; Yellen, Jay (2005)、『グラフ理論とその応用』『離散数学とその応用』（第2版）、CRC Press、p. 568、ISBN 9781584885054。
  19. ^チャートランド、ゲイリー、チャン、ピン（2012）、グラフ理論入門、クーリエ・ドーバー出版、pp.  189– 190、ISBN 9780486483689。
  20. ^ Béla Bollobás (1998)、「Modern Graph Theory」、Graduate Texts in Mathematics、vol. 184、Springer、p. 165、ISBN 9780387984889。
  21. ^マリア・チュドノフスキー、ニール・ロバートソン、ポール・シーモア、ロビン・トーマス(2006)、「強完全グラフ定理」、Annals of Mathematics、164 (1): 51– 229、arXiv : math/0212070、CiteSeerX 10.1.1.111.7265、doi : 10.4007/annals.2006.164.51、S2CID 119151552  。
  22. ^ DeVos, Matt、「Matchings」（PDF）、講義ノート：グラフ理論入門、数学345、サイモンフレーザー大学
  23. ^ Lovász、László (2014)、組み合わせ問題と演習(第 2 版)、エルゼビア、p. 281、ISBN 9780080933092
  24. ^ Asratian、Denley、Häggkvist (1998)、p. 17.
  25. ^ AA Sapozhenko (2001) [1994]、「ハイパーグラフ」、数学百科事典、EMSプレス
  26. ^ Brualdi, Richard A.; Harary, Frank ; Miller, Zevi (1980)、「行列によるバイグラフとダイグラフの比較」、Journal of Graph Theory、4 (1): 51– 73、doi : 10.1002/jgt.3190040107、MR 0558453 Brualdiらはこの同値性のアイデアをDulmage, AL; Mendelsohn, NS (1958)「二部グラフの被覆」、Canadian Journal of Mathematics、10 : 517– 534、doi : 10.4153/CJM-1958-052-0、MR 0097069、S2CID 123363425に帰した。  。
  27. ^ Sedgewick, Robert (2004)、『Javaアルゴリズム 第5部 グラフアルゴリズム（第3版）』、Addison Wesley、pp.  109– 111。
  28. ^ジョン・クラインバーグ; Tardos、Éva ( 2006)、アルゴリズム設計、Addison Wesley、 94–97ページ 。
  29. ^ Eppstein, David (2009)、「幾何学的交差グラフの二部性テスト」、ACM Transactions on Algorithms、5 (2): Art. 15、arXiv : cs.CG/0307023、doi : 10.1145 / 1497290.1497291、MR 2561751、S2CID 60496  。
  30. ^ Yannakakis, Mihalis (1978)、「ノードおよびエッジ削除NP完全問題」、第10回ACMコンピューティング理論シンポジウム（STOC '78）の議事録、pp.  253– 264、doi : 10.1145/800133.804355、S2CID 363248 
  31. ^リード、ブルース、スミス、ケイリー、ヴェッタ、エイドリアン（2004）、「奇数サイクル横断の検出」、オペレーションズ・リサーチ・レターズ、32（4）：299– 301、CiteSeerX 10.1.1.112.6357、doi：10.1016/j.orl.2003.10.009、MR 2057781  。
  32. ^ Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006)、「フィードバック頂点集合と辺二分化のための圧縮ベースの固定パラメータアルゴリズム」、Journal of Computer and System Sciences、72 (8): 1386– 1396、doi : 10.1016/j.jcss.2006.02.001
  33. ^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993)、「12. Assignments and Matchings」、Network Flows: Theory, Algorithms, and Applications、Prentice Hall、pp.  461– 509。
  34. ^ Ahuja、Magnanti、Orlin (1993)、p. 463：「非二部マッチング問題は、標準的なネットワークフロー問題に還元されないため、解決がより困難です。」
  35. ^ホップクロフト、ジョン・E. ;カープ、リチャード・M. (1973)、「二部グラフにおける最大マッチングのためのn 5/2アルゴリズム」、SIAM Journal on Computing、2 (4): 225– 231、doi : 10.1137/0202019。
  36. ^ Ahuja、Magnanti、Orlin（1993）、アプリケーション12.1二者間人事配置、pp.463-464。
  37. ^ Robinson, Sara (2003年4月)、「医学生は（可能な限り）最適な相手と出会っているか？」(PDF)、SIAM News (3): 36、 2016年11月18日時点のオリジナル(PDF)からアーカイブ、2012年8月27日閲覧。。
  38. ^ダルメイジ＆メンデルソン（1958年）。
  39. ^ムーン、トッド・K.（2005）、誤り訂正符号化：数学的手法とアルゴリズム、ジョン・ワイリー・アンド・サンズ、p.638、ISBN 9780471648000。
  40. ^ムーン（2005年）、686頁。
  41. ^カサンドラ、クリストス・G.; ラフォルチュン、ステファン（2007年）、離散事象システム入門（第2版）、シュプリンガー、p.224、ISBN 9780387333328。
  42. ^ Grünbaum, Branko (2009), 「点と線の構成」 , Graduate Studies in Mathematics , vol. 103, American Mathematical Society , p. 28, ISBN 9780821843086。
「 https://en.wikipedia.org/w/index.php?title=Bipartite_graph&oldid=1317867085」から取得