TREE函數(shù)

定義

規(guī)定：（圖：點(diǎn)和邊構(gòu)成，邊必須有兩個(gè)端點(diǎn)，邊是直的，圖形連續(xù)）

1. 第k張圖最大頂點(diǎn)數(shù)為k

2.圖不能包括以前的任何一張圖

TREE(n)=用n種顏色按照規(guī)定能畫出的最大圖數(shù)（不同顏色的點(diǎn)不一樣）

代入求值

TREE(0)

用0種顏色畫圖，第1張圖畫不出來，TREE(0)=0

TREE(1)

用1種顏色畫圖

第1張圖（最大頂點(diǎn)數(shù)：1）：第1種顏色的點(diǎn)1個(gè)

第2張圖（最大頂點(diǎn)數(shù)：2）：

1個(gè)點(diǎn)

第1種顏色的點(diǎn)1個(gè)（不符合規(guī)定）

2個(gè)點(diǎn)

第1種顏色的點(diǎn)2個(gè)（不符合規(guī)定）

第2張圖畫不出來，TREE(1)=1

TREE(2)

用2種顏色畫圖

第1張圖（最大頂點(diǎn)數(shù)：1）：第1種顏色的點(diǎn)1個(gè)

第2張圖（最大頂點(diǎn)數(shù)：2）：第2種顏色的點(diǎn)2個(gè)

第3張圖（最大頂點(diǎn)數(shù)：3）：第2種顏色的點(diǎn)1個(gè)

第4張圖畫不出來，TREE(2)=3

TREE(3)

第1張圖（最大頂點(diǎn)數(shù)：1）：第1種顏色的點(diǎn)一個(gè)

第2張圖和以后：多種可能

TREE(3)<∞，證明：

∵圖數(shù)越多，符合規(guī)定的圖越少

∴圖數(shù)→∞，符合規(guī)定的圖→0

TREE(4)和以后都沒有實(shí)質(zhì)性突破

SSCG函數(shù)

定義

方法：

1.刪除1個(gè)點(diǎn)或1條邊

2.合并一條邊上的兩個(gè)端點(diǎn)（邊消失）

規(guī)定：（圖：點(diǎn)和邊構(gòu)成，邊必須有兩個(gè)端點(diǎn)，邊是直的，圖形不必連續(xù)）

1. 第m張圖最大頂點(diǎn)數(shù)為m+n（n：代入函數(shù)的數(shù)）

2.圖通過以任何順序?qū)D使用方法的任何一點(diǎn)后不能和以前的任何一張圖一樣

SSCG(n)=按照規(guī)定能畫出的最大圖數(shù)+1

代入求值

SSCG(0)

圖的最大頂點(diǎn)數(shù)分別為：1,2,3……

第1張圖（最大頂點(diǎn)數(shù)：1）：點(diǎn)1個(gè)

第2張圖（最大頂點(diǎn)數(shù)：2）：

1個(gè)點(diǎn)

點(diǎn)1個(gè)（不符合規(guī)定）

2個(gè)點(diǎn)

圖形不連續(xù)

點(diǎn)2個(gè)（沒有邊連接）（不符合規(guī)定）

圖形連續(xù)

點(diǎn)2個(gè)（有邊連接）（不符合規(guī)定）

第2張圖畫不出來，SSCG(0)=1+1=2

SSCG(1)

圖的最大頂點(diǎn)數(shù)分別為：2,3,4……

第1張圖（最大頂點(diǎn)數(shù)：2，圖形連續(xù)）：點(diǎn)2個(gè)

第2張圖（最大頂點(diǎn)數(shù)：3，圖形連續(xù)）：點(diǎn)3個(gè)

第3張圖（最大頂點(diǎn)數(shù)：4，圖形連續(xù)）：點(diǎn)2個(gè)

第4張圖（最大頂點(diǎn)數(shù)：5，圖形連續(xù)）：點(diǎn)1個(gè)

第5張圖畫不出來，SSCG(1)=4+1=5

SSCG(2)

圖的最大頂點(diǎn)數(shù)分別為：3,4,5……

第1張圖和以后：多種可能

SSCG(3)

圖的最大頂點(diǎn)數(shù)分別為：4,5,6……

第1張圖和以后：多種可能

SSCG(2)<SSCG(3)<∞，證明：

∵圖數(shù)越多，符合規(guī)定的圖越少

∴圖數(shù)→∞，符合規(guī)定的圖→0

SSCG(4)和以后都沒有實(shí)質(zhì)性突破

比較

SSCG函數(shù)增長率遠(yuǎn)遠(yuǎn)超過TREE函數(shù)

SSCG函數(shù)中，圖的最大頂點(diǎn)數(shù)會(huì)和代入函數(shù)的數(shù)一起變化，圖經(jīng)過變化后，只需要滿足不能和以前的任何一張圖一樣

TREE函數(shù)中，圖的最大頂點(diǎn)數(shù)固定，圖必須滿足不能包含以前的任何一張圖

SSCG函數(shù)：圖的最大頂點(diǎn)數(shù)比TREE函數(shù)多

滿足不一樣的圖>滿足不包括的圖

所以SSCG函數(shù)增長率遠(yuǎn)遠(yuǎn)超過TREE函數(shù)

（文章允許轉(zhuǎn)載科普，原創(chuàng)：@沒用的名字_）