BipartiteGraphQ

BipartiteGraphQ[g]
グラフ g が二部グラフであればTrueを,そうでなければFalseを返す.

詳細詳細

  • あるグラフの頂点が2つのグループに分けられ,すべての辺が両グループ間にあるとき,そのグラフは二部グラフである.

予備知識
予備知識

  • BipartiteGraphQは,指定されたグラフが二部グラフかどうかを調べる.頂点集合が の2つの独立集合(「部集合」と呼ばれる)に分割できるグラフは二部グラフである.独立頂点集合は,同じ辺に接続する頂点は存在しないという条件を満たす頂点集合である.換言すれば,二部グラフの辺の片方の端点はすべて に含まれ,もう片方の端点はすべて に含まれる.BipartiteGraphQは,あるグラフが二部グラフのときはTrue を返し,それ以外のときはFalseを返す.グラフが二部グラフになる条件と同等の条件に,奇数長の閉路がない,彩色数が最大2である,等がある.木(および森)は閉路を含まない.従って自動的に二部グラフである.二部グラフの族には,奇数個の頂点を持つ閉路グラフ,格子グラフ,超立方体グラフ,ナイト(騎士)グラフ,スターグラフ(木であるため二部グラフである)等が含まれる.
  • 二部グラフは ある種の割り当て問題から自然発生した.例えば,労働者の集合 と常勤の仕事の集合 は, の部集合があり労働者が仕事を行う資格がある場合に労働者とその仕事を繋ぐ辺がある二部グラフを構築する.雇用が最大になるように労働者を仕事に割り当てることは,最大独立辺集合を求めることに等しい.
  • グラフ理論における多くの基本的な結果が二部グラフを含んでいる.ケーニヒ(König)の線彩色定理は,二部グラフの線彩色数はグラフの最大次数と等しいと述べている.ケーニヒ・エゲルヴァーリ(KönigEgerváry)の定理は,二部グラフのおける独立辺集合の最大サイズは頂点被覆の最小サイズに等しいと述べている.オーレ(Ore)の欠損公式は,グラフに部集合 があるなら,共通する値は, のすべての部分集合 上で最大の から 内のある点に接続する の頂点数を引いたものを のサイズから引いたものであると述べている. のどの部分集合も における近傍より多くの頂点を含まない特殊ケースの場合,オーレの欠損公式はホール(Hall)の結婚定理となる.この定理は,この条件が, の各頂点に接続する辺の独立集合の存在に等しいと述べている.
  • CompleteGraph[{m,n}]は,部集合 についての,サイズがそれぞれ mn の完全二部グラフを返す.この二部グラフは, のすべての頂点が の各頂点に接続している二部グラフである.

例題例題すべて開くすべて閉じる

  (2)  (2)

グラフが二部グラフかどうか調べる:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=

すべてのグラフが二部グラフである訳ではない:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=
2010年に導入
(8.0)