次へ / 戻る / 次へ

(6)　二部グラフ

　頂点集合 $V$ が交わりの無い２つの部分集合 $A$, $B$ に分かれ ( $V=A \cup B$,   $A \cap B = \emptyset$ )、 $A$ に属する頂点と $B$ に属する頂点の間にしか辺が無いグラフを二部グラフと呼びます。 $A$ の頂点同士、$B$ の頂点同士は隣接しない、と言っても同じです。

(7)　完全二部グラフ $K_{m,n}$

　上の状況で、特に

• $|\,A\,|=m$, $|\,B\,|=n$ で、
• $A$ の頂点と $B$ の頂点は必ず隣接する

ものを完全二部グラフと呼び、$K_{m,n}$ と表します。

$K_{2,2}$		$K_{2,3}$

(8)　星グラフ

　$K_{1,n}$ のことですが、頂点の配置によって星の形に見えるので星グラフと呼びます。

		$\cong$
$K_{1,5}$				こう描けば星の形

ネットワーク論で「スター型」と呼ぶ構造です。

(9)　閉路 $C_n$

　$n$ 頂点の、輪の形のグラフです。$n$ 角形の頂点と辺から作ったグラフ、と言っても同じです。 （ 対角線は入れません。）

$C_3$		$C_4$

(10)　道グラフ $P_n$

　$n$ 頂点の、一直線の形のグラフです。

$P_3$		$P_4$

(11)　車輪グラフ $W_n$

　$n$ 頂点の、文字通り車輪の形のグラフです。 真ん中にも点があるので $W_n$ は $n-1$ 角形の車輪です。

$W_6$ は五角形		$W_7$ は六角形

(12)　$k$ 次元立方体グラフ $Q_k$

　$k$ 次元立方体の頂点と辺から作ったグラフです。 言葉を変えるとこういう定義もできます：

• 長さ $k$ のビット列を頂点とする。
• $1$ ビットだけ違うビット列同士を辺で結ぶ。

$k=2,\,3$ の場合を描いてみると、

$Q_2 \cong C_4$		$Q_3 \cong$ 立方体グラフ

それぞれ $xy$-平面の単位正方形、$xyz$-空間の単位立方体になっていますね。
※　$Q_k$ の中での距離は、符号理論で用いる「ハミング距離」と同じもので、信号の誤り訂正能力に関わる重要な概念です。

形は変えてもいい

　以上、「何々の形をした」という書き方をしましたが、同型なグラフは「同じもの」として同じ名前で呼びますので、 頂点の配置は自由に動かして構いません。ここ大事 !

　たとえば直線の形はしていませんが、次のグラフたちも $P_6$ です：

  

次へ / 戻る / 次へ