三角格及滿二叉樹上的σ全一問題.pdf

1、細(xì)胞自動機(jī)是一種離散動力系統(tǒng)，它包含了由細(xì)胞單元的狀態(tài)構(gòu)成的配制以及作用在配制上的傳遞規(guī)則．其數(shù)學(xué)刻畫如下：假設(shè)在一個(gè)無向圖的每個(gè)頂點(diǎn)上安裝有一個(gè)指示燈和一個(gè)按鈕．如果在該圖中按下一個(gè)按鈕，則它的所有相鄰點(diǎn)上的燈將由暗到亮，反之亦然．開始時(shí)，所有燈都是暗的，問題是：是否有可能按下一系列的按鈕使得最終所有的燈都亮了?該問題被稱為σ全一問題，特別地，若圖的每一個(gè)點(diǎn)都有一個(gè)自環(huán)，則它也被稱為σ+全一問題，起源于Sutner引入的棋盤上的全一問

2、題，后被Peled稱為點(diǎn)燈問題． 近年來σ+全一問題已經(jīng)被廣泛的研究，Barua和Ramakrish-nan[2]以及Dodis和Winkler[13]．用線性代數(shù)的理論，Sutner證明σ+全一問題的解對任何圖總是存在的，并給出了n×n的格子圖上解的一些計(jì)數(shù)結(jié)果．Erikisson等給出了解存在性的圖論證明[15]．進(jìn)而，Chen和Gu[8]給出了一個(gè)精巧的圖論算法來找到一般圖上的解．與σ+全一問題不同，σ全一問題在很多圖上都