福克曼圖(Folkman graph)是一類極圖，具有最少頂點(20個)的邊可遷但非頂點可遷的正則圖。
基本介紹
- 中文名：福克曼圖
- 外文名：Folkman graph
- 領域：數學
- 性質：一類極圖
- 特點：正則圖
- 相關概念：格雷圖
概念,極圖,正則圖,格雷圖,
概念
福克曼圖(Folkman graph)是一類極圖，具有最少頂點(20個)的邊可遷但非頂點可遷的正則圖(見圖)。
福克曼圖極圖
極圖是一類特殊的圖。指階數一定在某種意義下最大的圖。給定一個圖族L，在所有n階圖中含邊最多，不以L中圖為其子圖的圖。這個給定的圖族L稱為禁用圖類。關於L的全部n階極圖的集記為Ex(n，L)，其中每個極圖邊數相等，記為ex(n，L)。例如，Tm，n圖，即有n個節點，各部節點數分別為[n/m](即n/m的整數部分)或[n/m]+1的完全m部圖，就是一個極圖。其中，L是m+1階完全圖.Tm，n常稱為圖蘭圖。事實上，有圖蘭定理：在所有不含完全圖Kn作為子圖的m階圖中，邊數最多的圖只有一個，就是Tm，n-1。它第一次出現在圖蘭(Turn，P.)1941年發表的文章中，由此而得名。
正則圖
正則圖是一類特殊的圖。指所有節點的次都相同的圖。節點的次為k的正則圖稱為k正則圖。一個圖上某一條邊的次是指這個圖上與這條邊有公共端點的邊的數目。所有邊的次都相同的圖稱為邊正則圖。對於一個圖，若存在正整數k，λ，μ，使得下列條件成立，則稱該圖為強正則圖：
1.G是k正則圖。
2.對於圖上任意兩個不同節點v和w，若v和w相鄰，則G上與v和w都相鄰的節點的數目是λ，否則，G上與v和w都相鄰的節點的數目是μ。
3.正則圖是指所有節點的次都是3的圖。每個連通片不是圈就是二階完全圖，即由一條桿組成的圖，稱為一個半正則圖。
格雷圖
格雷圖是一種特殊的圖。指一個有54個頂點(較福克曼圖多)的3正則的邊可遷但非頂點可遷的圖。它是這樣構造的：三個K3，3圖，每個的九條邊一一對應，每一對應的三邊組中加一個剖分點，如圖中v1，v2，v3，然後另加一點v4與此三點相連。下面的圖只畫出其中一組。
格雷圖