![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/4/49/Star_network_7.svg/langja-640px-Star_network_7.svg.png&w=640&q=50)
スター (グラフ理論)
ウィキペディア フリーな encyclopedia
スター もしくは星Sk は、グラフ理論の用語の1つであり、ただ1つの頂点とそれにつながる k 個の葉のみを持つグラフである。また、スターは完全2部グラフ K1, kでもある。スター Sk を直径が2で次数が k である木とする人も存在し、この場合 2 < k であり葉の数は k-1 である。
![]() | 原文と比べた結果、この記事には多数の(または内容の大部分に影響ある)誤訳があることが判明しています。情報の利用には注意してください。(2017年9月) |
![]() | この記事の正確性に疑問が呈されています。 |
概要 スター, 頂点 ...
スター | |
---|---|
![]() 葉を7つ持つスター S7(一部の人はこれを S8と表現する) | |
頂点 | k+1 |
辺 | k |
直径 | min(2, k) |
内周 | ∞ |
彩色数 | min(2, k + 1) |
彩色指数 | k |
特性 |
頂点推移グラフ 木 (数学) 単位距離グラフ 2部グラフ |
表記 | Sk |
テンプレートを表示 |
閉じる
頂点が3個の星は特別にクローもしくは爪と呼ぶ。
スター Sk は k が偶数のときには edge-graceful であり、 k が奇数の場合はそうでない。スターは頂点推移グラフであり、 1 < k においてグラフの直径は2であり、内周は ∞ である。また、スターは自己同型群を持つ。すなわち、 k 次の対称群である。
スターは、(最大でも)1つの頂点の次数が1より大きい、連結グラフともいえる。