車輪グラフ
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/03/06 06:07 UTC 版)
車輪グラフ | |
---|---|
![]()
車輪グラフの例
|
|
頂点 | n |
辺 | 2(n - 1) |
直径 | 1 (n = 4) 2 (n > 4) |
内周 | 3 |
彩色数 | 3 (n が奇数の場合) 4 (n が偶数の場合) |
特性 | ハミルトングラフ 自己双対 平面グラフ |
表記 | Wn |
車輪グラフ(しゃりんグラフ、英: Wheel graph)とは、グラフ理論のグラフの1つであり、閉路グラフと、そのすべての頂点に接続するユニバーサル頂点(支配頂点)と呼ばれる頂点からなるグラフである。n 頂点の車輪グラフは、 n - 1角錐の、1-骨格とも定義できる(3 < n)。n 頂点の車輪グラフをWnで表したり[1]、n + 1 頂点の車輪グラフを、 n 角形で表せることから Wnで表したりする[2]。本記事内では、前者の表記を用いる。
内包表記での構成
頂点集合 {1, 2, 3, …, v }に対し辺の集合は内包表記で{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v - 1, v}, {v ,2}}と表せる[3]。 ここで、頂点1がユニバーサル頂点であり、頂点2から頂点 v は閉路グラフを構成する。
性質
車輪グラフは
- 平面グラフであり、一意な平面グラフを持つ。
- 車輪グラフはハリングラフ(木(グラフ)の葉を閉路でつないだ平面グラフ)である。
- 車輪グラフは自己双対である。
- 最大平面グラフは、K4 = W4であるか、W5 か W6を部分グラフとして含む。
- n - 1 種類のハミルトン閉路をもつ
- Wnに対して
車輪グラフW4に含まれる7種類の閉路。
下3つはすべての頂点を通るため、ハミルトン閉路である。n が奇数の場合、 Wn は彩色数3のパーフェクトグラフである。つまり、ユニバーサル頂点以外の頂点を交互に2色に塗り分け、中央のユニバーサル頂点を3色目で塗り分けられる。n が偶数の場合、 Wn は彩色数が4であり、n ≥ 6 でパーフェクトグラフではなくなる。 W7 はユークリッド平面上で唯一単位距離グラフである[4]
車輪グラフ
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/03/02 06:44 UTC 版)
「名称のあるグラフのギャラリー」の記事における「車輪グラフ」の解説
車輪グラフ Wnはn個の頂点を持ち、一つの頂点が(n − 1)-閉路グラフのすべての頂点と結ばれたものを言う。 車輪グラフの例 W 4 {\displaystyle W_{4}} – W 9 {\displaystyle W_{9}} .
※この「車輪グラフ」の解説は、「名称のあるグラフのギャラリー」の解説の一部です。
「車輪グラフ」を含む「名称のあるグラフのギャラリー」の記事については、「名称のあるグラフのギャラリー」の概要を参照ください。
- 車輪グラフのページへのリンク