うさぎでもわかる離散数学（グラフ理論） 第9羽 グラフの基礎3
グラフ \( G_1 = (V_1,E_1) \)、グラフ \( G_2 = (V_2,E_2) \) に対し、任意の2つの頂点 \( u,v \in V_1 \) に対し、隣接関係\[(u,v) \in E_1 \Leftrightarrow ( f(u),f(v) ) \in E_2 \]となるとき*4、\( G_1 \) と \( G_2 \) は 同型 であるという。さらに写像（関数） \( f \) を 同型写像 と呼ぶ。
同型グラフと変数・点の数・総和の関係ただし、辺の数、点の数がともに等しくても 同型であるとはかぎらない 。
(2) 同型の判定法のコツStep1：辺の数、点の数を確認
まず辺の数、点の数を確認します。2つのグラフで どちらか一方でも異なった場合 は同型ではありません。
Step2：それぞれの次数が何個ずつあるのかを確認（次数列の確認）
Step1：辺の数、点の数を確認
Step2：次数列を確認
次数列もともに 4,4,4,4,3,3,3,3 になるのでOK。
Step3：同じ次数の点の隣接する点の次数の組み合わせをチェック
- それぞれのグラフの点の数、辺の数が同じかを確認。
- それぞれのグラフの次数列 が同じになるかを確認。（次数列ではなくても、それぞれの次数が何個あるかを確認して2つの次数で完全一致するかどうかを確認すればいい。）
- 同じ次数の点に対して、それぞれの点に隣接する点の次数を比べて一致するかを確認
６．正則グラフ
(1) 正則グラフとはあるグラフの すべての点における次数が同じようなグラフ のことを 正則グラフ と呼びます。それぞれの次数がすべて \( n \) であるとき、 \( n \) 次正則グラフ (n-正則グラフ)と呼びます。
あるグラフ \( G \) における次数がすべて同じ \( n \) であるとき、\( G \) を \( n \) 次正則グラフ と呼ぶ。
(2) 完全グラフ・完全2部グラフと正則グラフの関係 完全グラフと正則グラフ\( n \) 個の点からなる完全グラフ \( K_n \) は実は必ず正則グラフとなります。
\( K_n \) は自分以外の点 \( n-1 \) 個すべてに辺が接続されていますね。なので、どの点においても \( n-1 \) 個の辺が接続されています。つまり、すべての点において次数が \( n-1 \) となります。
なので、完全グラフ \( K_n \) は \( n-1 \) 次の正則グラフ となるのです！
例えば、\( K_4 \) であれば3次正則グラフとなります。
完全2部グラフと正則グラフ\( X \) の点と \( Y \) の点がともに同じ \( n \) 個の場合の完全2部グラフを考えてみましょう。
このとき、それぞれの \( X \) 上の点 \( n \) 個に対し、\( Y \) のすべての点 \( n \) 個に辺を接続していますね。
なので、\( X \) 上のすべての点、\( Y \) 上のすべての点ともに次数が \( n \) になりますね。
なので、完全2部グラフ \( K_ \) は \( n \) 次の正則グラフ となりますね。
完全グラフ・完全2部グラフと正則グラフ完全グラフ \( K_n \) は必ず \( n-1 \) 次正則グラフとなる。
また、完全グラフ \( K_ \) は \( m = n \) のとき、必ず \( n \) 次正則グラフとなる。
７．補グラフ
あるグラフにおいて、 もともと辺があった場所の辺をなくし、もともと辺がなかった場所の辺をつけた（辺の有無を反対にしたような）グラフ のことを補グラフと呼びます。
補グラフのイメージは、 完全グラフからもとのグラフを引いたもの と覚えておくとわかりやすいと思います。
グラフ \( G = (V,E) \) に対し、もとのグラフ \( G \) と補グラフ \( \overline \) のどちらかが必ず連結である。
もとのグラフ \( G \) が連結でなければ、補グラフが連結になることを示します。
下の図のように非連結グラフは、2つ以上の連結成分に分けることができます。これを \( C_1 \), \( C_2 \), … ,\( C_n \) としましょう。
（任意のグループ同士の2点 \( x \) ,\( y \) は、ある他のグループの1点 \( t \) を通り、\[x \to t \to y\]の長さ2の道で結ばれる。）
上の図の場合、例えば \( C_1 \) 同士のどの2点も他のグループ \( C_2 \), \( C_3 \) のどの点を経由しても2辺だけたどって戻ることができますね。
（\( C_1 \) の任意の2点 \( x \), \( y \) は他のグループ \( C_2 \), \( C_3 \) の中の1点を通る長さ2の道で結ばれる）
そのため、もとのグラフ \( G \) が非連結であった場合は必ず補グラフ \( \overline \) が連結となるので、\( G \) か \( \overline \) のどちらかが必ず連結となるのです！
８．練習問題
練習1(1) 完全グラフを1つ選びなさい。(2) 2部グラフをすべて選びなさい。(3) 正則グラフになるものをすべて選び、何次の正則グラフになるかを答えなさい。(4) 互いに同型となるペアを1つ見つけなさい。
練習2(1) 完全グラフ \( K_ \) の辺の数を答えなさい。(2) 完全2部グラフ \( K_ \) の辺の数を答えなさい。
練習3 練習4 練習5 練習6９．練習問題の答え
解答11は \( K_4 \) の完全グラフである。
解答：②・③（実は両方とも完全2部グラフ \( K_ \) になります。）
解答2\( K_ \) にはそれぞれの点10個が、自分以外の点9個と辺を接続している。しかし、無向グラフなのでそれぞれの辺をダブルカウントしないように2で割る必要がある。よって、\[\frac \cdot 10 \cdot 9 = 45\]となる*6。
\( K_ \) は8個の点が6方向に対して辺を接続している。なので、\[8 \times 6 = 48\]となる。
解答3 解答4 解答5 解答6点数が6の完全グラフ \( K_6 \) のそれぞれの次数は5ですね。（わからなければ実際に書いてみましょう）
10．さいごに
*1 : たどるためには \( v_3 \) と \( v_5 \) の間、もしくは \( v_4 \) と\( v_6 \) を結ぶような辺が必要。
*2 : 普通に \( n \) 個の中から順番を考えずに2つ取り出すから \( _n \mathrm _2 \) でもいいが今回はあえて詳しく説明しています。
*4 : 述語論理を使って書くと、\[\forall u,v \in E_1 \ \ \mathrm \ \ (u,v) \in E_1 \Leftrightarrow ( f(u),f(v) ) \in E_2 \]となる。
*5 : グラフの各点におけるそれぞれの次数を大きい順に並べたもの。例えば、下のような図の場合、各点における次数は1, 4, 2, 2, 3なので次数列はそれぞれの次数を大きい順に並び替えた4,3,2,2,1となる。
*6 : 普通に \( _ \mathrm _2 = 45 \) でもOK
公開日： 2019年10月15日 更新日： 2019年10月15日 この記事を書いた人 コメント一覧 コメントはありません。 関連記事 うさぎでもわかる解析 Part25 極座標変換を用いた2重積分の求め方 【基本情報対策】うさぎでもわかるデータベース 第01羽 関係データベース（主キーと外部キーの違い） うさぎでもわかるアルゴリズム 動的計画法 うさぎでもわかる信号処理 番外編 ブロック図(ブロック線図)の読み方・書き方 うさぎでもわかる線形代数 第20羽 2次形式 うさぎでもわかる計算機システム Part06 プロセッサの基礎 うさぎでもわかる線形代数 補充2 平面・空間上における直線の方程式（ベクトル方程式の基礎） うさぎでもわかる解析 Part13 2変数関数の極限の求め方・連続性の確認 うさぎでもわかる離散数学（グラフ理論） 第8羽 グラフの基礎2 歩道・小道・道・回路・閉路とは 最高の研究室生活を送るために 研究室選びのいろはカテゴリー
各種便利ツール・問い合わせ- 【完全無料】離散数学演習ツール・計算機まとめ
- 【離散数学】べき集合 2^A・P(A) 自動計算＆全列挙ツール
- 【離散数学】上界/下界・最大元/最小元・極大元/極小元・上限(最小上界)/下限(最大下界) 判定ツール
- 【離散数学】真理値表 自動作成ツール（途中式あり）
- 【離散数学】集合の「∈・⊆」真偽チェッカー（答え合わせ用）
- 【離散数学テスト対策】真理値表の穴埋めガチ演習ツール
- 【離散数学テスト対策】集合の「∈・⊆」ガチ演習！ 弱点分析つき○×ドリル
目次
工業大学生ももやまのうさぎ塾 (Momousagi Academy)