首頁 現(xiàn)實

數(shù)學心

第四百零五章 伯恩賽德引理(圖論)

數(shù)學心 蔡澤禹 11196 2021-01-07 05:42:09

  1902年,伯恩賽德提出了伯恩賽德引理。

  一個由2*2方格組成的正方形,每個格子上可以涂色或不涂色,問共有多少種本質不同的涂色方案。

  每個格子可以涂色,可以不涂色,共有16種方案。將16種方案編號。

  把本質相同的方案合并:方案1:{1},方案2:{2},方案3:{3,4,5,6},方案4:{7,8,9,10},方案5:{11,12},方案6:{13,14,15,16},共6種方案。

  旋轉可以看作是置換,所有置換組成置換群。

  如果x通過某個置換可以變成y,說明x和y等價。

  與x互相等價的一組元素組成了一個集合,稱為x的等價類。

  這個問題中,我們要求的就是這樣的等價類有多少個。

  我們由Burnside's lemma 可得一種公式,這個公式的意思是:等價類的個數(shù)=每個置換中不動元的個數(shù)和÷置換群大小。|X/G|=(16+2+4+4)/4=6。

  也可說為等價類個數(shù)=不動元個數(shù)的平均數(shù)

按 “鍵盤左鍵←” 返回上一章  按 “鍵盤右鍵→” 進入下一章  按 “空格鍵” 向下滾動
目錄
目錄
設置
設置
書架
加入書架
書頁
返回書頁
指南