2部グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/21 05:56 UTC 版)
2つの部分がr個とs個の頂点を持つ2部グラフの隣接グラフAは以下の形式で書くことができる。 A = ( 0 r , r B B T 0 s , s ) , {\displaystyle A={\begin{pmatrix}0_{r,r}&B\\B^{T}&0_{s,s}\end{pmatrix}},} 上式において、Bはr × s 行列、0r,rおよび0s,sはr × rおよびs × sゼロ行列を表わす。この場合、より小さな行列Bがグラフを一意に表わし、Aの残りの部分は冗長として捨てることができる。Bはbiadjacency行列と呼ばれることがある。 形式的に、G = (U, V, E)を部分U = {u1, …, ur}およびV = {v1, …, vs}を持つ2部グラフとする。Biadjacency行列は、 (ui, vj) ∈ Eの時かつその時に限りbi,j = 1のr × s 0–1行列Bである。 Gが2部多重グラフまたは重み付きグラフならば、要素 bi,jは頂点間の辺の数、または辺(ui, vj)の重みをそれぞれ取る。
※この「2部グラフ」の解説は、「隣接行列」の解説の一部です。
「2部グラフ」を含む「隣接行列」の記事については、「隣接行列」の概要を参照ください。
2部グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/12 14:26 UTC 版)
「グラフ (離散数学)」の記事における「2部グラフ」の解説
詳細は「2部グラフ」を参照 「2部グラフ (bipartite graph)」とは、頂点集合を U {\displaystyle U} と V {\displaystyle V} の2集合に分割し、 U {\displaystyle U} 内で任意の2頂点が辺を共有することがなく、 V {\displaystyle V} 内でも任意の2頂点が辺を共有することがないようにできる単純グラフのこと。言い換えるなら、彩色数2となるグラフ。 完全2部グラフにおいて、頂点集合は2つの素集合 U {\displaystyle U} と V {\displaystyle V} の合併 (union) であり、 U {\displaystyle U} 内にある全ての頂点が V {\displaystyle V} 内にある全ての頂点と隣接しているのだが、素集合の U {\displaystyle U} 内や V {\displaystyle V} 内で完結する辺がないものをいう。
※この「2部グラフ」の解説は、「グラフ (離散数学)」の解説の一部です。
「2部グラフ」を含む「グラフ (離散数学)」の記事については、「グラフ (離散数学)」の概要を参照ください。
Weblioに収録されているすべての辞書から2部グラフを検索する場合は、下記のリンクをクリックしてください。
全ての辞書から2部グラフ
を検索
- 2部グラフのページへのリンク
