車輪グラフとは? わかりやすく解説

車輪グラフ

出典: フリー百科事典『ウィキペディア(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であるか、W5W6を部分グラフとして含む。
  • n - 1 種類のハミルトン閉路をもつ
  • Wnに対して
    車輪グラフW4に含まれる7種類の閉路。
    下3つはすべての頂点を通るため、ハミルトン閉路である。

    n が奇数の場合、 Wn彩色数3のパーフェクトグラフである。つまり、ユニバーサル頂点以外の頂点を交互に2色に塗り分け、中央のユニバーサル頂点を3色目で塗り分けられる。n が偶数の場合、 Wn は彩色数が4であり、n ≥ 6 でパーフェクトグラフではなくなる。 W7ユークリッド平面上で唯一単位距離グラフである[4]

    車輪グラフ Wn彩色多項式は、 カテゴリ / コモンズ


車輪グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/03/02 06:44 UTC 版)

名称のあるグラフのギャラリー」の記事における「車輪グラフ」の解説

車輪グラフ Wnはn個の頂点持ち一つ頂点が(n − 1)-閉路グラフすべての頂点結ばれたものを言う。 車輪グラフの例 W 4 {\displaystyle W_{4}} – W 9 {\displaystyle W_{9}} .

※この「車輪グラフ」の解説は、「名称のあるグラフのギャラリー」の解説の一部です。
「車輪グラフ」を含む「名称のあるグラフのギャラリー」の記事については、「名称のあるグラフのギャラリー」の概要を参照ください。

ウィキペディア小見出し辞書の「車輪グラフ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「車輪グラフ」の関連用語

車輪グラフのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



車輪グラフのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの車輪グラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの名称のあるグラフのギャラリー (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS