http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9% …
によると、
隣接する頂点同士が同じ色にならないように全頂点に彩色する問題を頂点彩色という。
彩色多項式とは、与えられたグラフをt色以下で彩色したときの彩色の組合せ数を求める式である。
閉路グラフC_n(つまり、n角形)をt色以下で彩色したときの彩色多項式は、
(t-1)^n+(-1)^n*(t-1)
これがどのように示されるのかがわからないので、どうか教えていただけないでしょうか。
No.2ベストアンサー
- 回答日時:
>もし、正多角形の塗りわけで、隣り合う色が異なり、回転して同じ配色になると同じとみなす、ものの場合の数の公式や理論がありましたら紹介いただけるとありがたいです。
残念乍、関連する文献は存じません。が、単純に考えれば正n角形の360/n度の回転から生成される巡回群は、自然に正n角形に作用しますので、P(C[n],t)/nで求められるような気がするんですが。
なお、正方形に関しては、昔対称軸による折り返しまで含めて似たようなことを考えたことがあります。その場合は、4次の二面体群D4の自然な作用を考えることになるので、P(C[4],t)/8が求める結果でした。
nが大きい場合は、対称軸が増えるので結構ややこしくなりそうですね。
ご返答ありがとうございます。
例えば、正方形の頂点を、r(赤)、b(青)、y(黄)の3色以下で配色するとき、
隣り合う色が異なり、回転して同じ配色になっても異なるとみなす、ものの場合の数は、n=4,t=3として、(t-1)^n+(-1)^n*(t-1)=18通りとなりますが、具体的には次のようになります。
rbrb,brbr
ryry,yryr
byby,ybyb
rbry,bryr,ryrb,yrbr
brby,rbyb,bybr,ybrb
yryb,ryby,ybyr,byry
そのなかで、回転して同じ配色になっても異なるとみなすと、同じ行の彩色は同じとなり、結局6通りとなります。
ちなみに、隣り合う色の制約はなく、回転して同じ配色になっても異なるとみなす、ものの場合の数は、t=3として,t^4/4+t^2/4+t/2=24通りとなりますが、具体的には次のようになります。
rrrr,bbbb,yyyy
rrrb,rrbb,rbbb,rbrb
rrry,rryy,ryyy,ryry
bbby,bbyy,byyy,byby
rrby,rryb,rbry
bbry,bbyr,brby
yyrb,yybr,yryb
環指標(cycle index)という概念を非可換にすれば、隣り合う色が異なり、回転して同じ配色になると同じとみなす、ものの場合の数が求められる気がするのですが、よくわからないです。
No.1
- 回答日時:
dfhsdsさん、今晩は。
結構長いので概略に留めます。詳細は、下記文献を参照してください。
グラフGの色数tの彩色多項式をP(G,t)と書くことにする。
Gの一つの辺をeとするとき、P(G,t)=P(G-e,t)-P(G/e,t) (**)が成り立つ。但し、G/eはeによる縮約。
C[n]をn-サイクルとするとき、C[n]/e=C[n-1]、また、M=C[n]-eは長さn-1の道であり、このとき、P(M,t)=t(t-1)^(n-1)である。
よって、(**)より、P(C[n],t)=P(C[n]-e,t)-P(C[n]/e,t)=t(t-1)^(n-1)-P(C[n-1],t)である。
C[n-1]もサイクルだから、同様にしてP(C[n],t)=t(t-1)^(n-1)-t(t-1)^(n-2)+P(C[n-2],t)となる。以下、同様。
参考文献 グラフの不変数(組合せ論演習3) 秋山仁、榎本彦衛著 東海大学出版会
51ページの問題2.39
ご回答まことにありがとうございます。
漸化式を考えるのだろうとは思いながら、予備知識がない自力では難しいと感じていました。
あとでじっくりと拝読したいと思います。
僕は、組合せ論の方面から、正多角形や正多面体の塗りわけ(ただし、隣り合う色が同じでも良い。回転して同じ配色になるものは同じとみなす)に興味を持って、それはポリアの定理と呼ばれるもので解けることを最近知りました。
今回、投稿させていただいた正多角形の塗りわけは、隣り合う色が異なり、回転して同じ配色になっても異なるとみなす、ものです。
もし、正多角形の塗りわけで、隣り合う色が異なり、回転して同じ配色になると同じとみなす、ものの場合の数の公式や理論がありましたら紹介いただけるとありがたいです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 『4色問題③』 2 2022/11/14 00:31
- 芸術学 バルールとはなんでしょうか。 この絵が「正解」である場合、ピントの合っている部分から奥に行くにつれて 1 2022/04/01 04:44
- 日本語 「無彩の色」 「ネズミ色の服を着た人が、煤竹色の小さな部屋で、灰色の茶碗を見つめている。」で、筆者が 1 2022/08/03 14:46
- 食べ物・食材 ホラン千秋さんの弁当なかなかイケてますね^^ 8 2022/09/29 20:20
- 美術・アート 水彩色鉛筆について。 水彩鉛筆の動画を見て、肌に青を入れたり、緑を入れたり、髪の毛にもいろんな色を入 3 2023/04/01 07:09
- 美術・アート 油絵、アクリル画、水彩画で二色の間を滲ませない方法は? 2 2022/05/05 20:47
- デジタルカメラ フィルム調の色彩が撮影できるデジタルカメラは存在しないの? 5 2023/05/12 14:11
- 数学 正八面体の8面を、7色A~Gで塗り分ける方法は何通りあるか(隣り合う面は同じ色でもいいが、回転して一 1 2022/08/04 23:06
- 美術・アート 色鉛筆画について教えてください。 3 2022/09/24 16:18
- その他(職業・資格) 色彩検定1級について 2 2022/05/06 16:20
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
余次元って何?
-
多項式について質問です。 エク...
-
2次以上の多項式g(x)であって, ...
-
(x-1)(x-2)(x-3)の展開の...
-
パデ近似の利点について教えて...
-
データのノイズ除去法 - Savitz...
-
パデ近似の収束半径
-
斉次とは?(漢字と意味)
-
約数と因数の違い(∈N)
-
CRCアルゴリズムのZ/2Z上の多項...
-
問題が理解できません
-
等差×等比 型の数列の和を求め...
-
複素Newton法?
-
三次自然スプライン
-
nが正の自然数の時、2n(n²+n+...
-
多変数関数の微分とテイラー展...
-
解法を教えてください
-
ケーリー・ハミルトンの定理の...
-
2次式(2次3項式)の因数分解で、...
-
よく0.9…=1を議論したがる方...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
(x-1)(x-2)(x-3)の展開の...
-
代数
-
この中で多項式はいくつありま...
-
あってますか?
-
(中3数学)次の式を展開しなさ...
-
多項式について質問です。 エク...
-
素イデアルの判定がわからないです
-
約数と因数の違い(∈N)
-
deg f?
-
e^sinXの展開式について。。。
-
単項式と分数式の違いについて
-
(x+3)(x-3)(x^4+9x^2+81)の展開...
-
arcsinのマクローリン展開について
-
斉次とは?(漢字と意味)
-
データのノイズ除去法 - Savitz...
-
(1+x)^n=1+nxについて
-
等差×等比 型の数列の和を求め...
-
余次元って何?
-
塾での問題なんですが・・・至...
-
パデ近似の利点について教えて...
おすすめ情報