📢 Webサイト閉鎖と移転のお知らせ
このWebサイトは2026年9月に閉鎖いたします。
新しい記事は移転先で追加しております。（旧サイトでは記事を追加しておりません）
| 150行目: | 150行目: | ||
下図のグラフの次数列は、(1, 3, 6, 8)である。<br> | 下図のグラフの次数列は、(1, 3, 6, 8)である。<br> | ||
[[ファイル:Graph Theory 2 8.jpg|フレームなし|中央]] | [[ファイル:Graph Theory 2 8.jpg|フレームなし|中央]] | ||
<br><br> | |||
== 握手補題 == | |||
補題 : 任意のグラフのすべての点の次数を合計すれば偶数になる。<br> | |||
グラフの各辺は2本あるので、全ての点の合計は辺数の2倍である。<br> | |||
<br><br> | |||
== 部分グラフ == | |||
部分グラフ(sub graph)とは、その点はすべてV(G)に属し、その辺はすべてE(G)に属すグラフのことである。<br> | |||
グラフの辺と点を除去して部分グラフを作ることができる。<br> | |||
<br> | |||
例<br> | |||
下図Aのグラフは、下図Bのグラフの部分グラフである。<br> | |||
下図Aのグラフは、下図Cのグラフの部分グラフではない。下図Cのグラフには、点と辺により作られる三角形が含まれないため。<br> | |||
[[ファイル:Graph Theory 2 9.jpg|フレームなし|中央]] | |||
<br><br> | |||
== 辺と点の除去 == | |||
* 辺の除去(1) | |||
*: eがグラフGの辺であるとき、Gから辺eを除去して得られるグラフをG - eと書く。 | |||
* 辺の除去(2) | |||
*: グラフGの辺の集合の部分集合をFとしたとき、GからFの辺をすべて除去して得られるグラフをG - Fと書く。 | |||
* 点と辺の除去(1) | |||
*: 同様にして、グラフGから点vおよびvに接続する辺すべてを除去して得られるグラフをG - vと書く。 | |||
* 点と辺の除去(2) | |||
*: SがGの点の集合の部分集合であるとき、Sの点とそれらに接続している全ての辺を除去して得られるグラフをG - Sと書く。 | |||
<br> | |||
例<br> | |||
[[ファイル:Graph Theory 2 10.jpg|フレームなし|中央]] | |||
<br><br> | |||
== 辺の縮約 == | |||
グラフGから、辺eを除去し、その端点vとwを同一視して1点にすることを、グラフGの辺eに対する縮約(contraction)という。<br> | |||
即ち、端点vまたはwに接続していた(辺e以外)の辺を新しくできた点に接続させたグラフである。<br> | |||
グラフGの辺eに対する縮約グラフを、<math>G \backslash e</math>と書く。<br> | |||
<br> | |||
例<br> | |||
下図に、グラフGの辺eに対する縮約グラフを示す。<br> | |||
[[ファイル:Graph Theory 2 11.jpg|フレームなし|中央]] | |||
<br><br> | <br><br> | ||
__FORCETOC__ | __FORCETOC__ | ||
[[カテゴリ:グラフ理論]] | [[カテゴリ:グラフ理論]] | ||