完全二分圖的Pt-因子分解的探討 指導教授：高金美 學生：陳昆楠.

Presentation on theme: "完全二分圖的Pt-因子分解的探討 指導教授：高金美 學生：陳昆楠."— Presentation transcript:

1 完全二分圖的Pt-因子分解的探討 指導教授：高金美 學生：陳昆楠

2 完全二分圖 K2,3 令G=(V,E)為一個圖，若 G 的點集合 V 可分成 A 和 B 兩集合，其中 A  B = V，
A  B =  ，且E={{a,b} | aA，bB }，則稱 G 是一個完全二分圖， A 和 B 為 G 的二分點集合。 若|A|=m、|B|=n，則此完全二分圖記為Km,n。 A B K2,3

3 F-因子 令F、G、H為三個圖，若 H 為 G 的一個生成子圖，且 H 中的每個分支都與 F 同構，則稱 G 有一個 F-因子。
F=P5 G有一個P5-因子

4 分割 令 G 為一個圖 若 Gi 為 G 的子圖， ，且 ， ， ， 則稱 G 可分割成 n 個子圖 G1,G2,…,Gn。 G1 G G2

5 F-因子分解 令 G 和 F 為兩個圖，若 G 可分割成 G1, G2, …, Gn，其中每個 Gi 均為 G 的 F-因子，則稱 G 有 F-因子分解。

6 K4,6有P5-因子分解？ 令A={a1,a2,a3,a4}， B={b1,b2,b3,b4,b5,b6} 為K4,6的二分點集合。
G1 G2 G3 K4,6有P5-因子分解。

7 G1、G2、G3分別為K4,6中的1組P5-因子，且邊都相異，所以K4,6有P5-因子分解。
b1 b2 b3 b4 b5 b6 a1 a2 a3 b1 b2 b3 b4 b5 b6 a4 a1 a2 a3 a4 3 2 1 G1=b1a1b2a2b3  b4a3b5a4b6 ， G2=b5a1b6a2b1  b2a3b3a4b4 ， G3=b3a1b4a2b5  b6a3b1a4b2 ， G1、G2、G3分別為K4,6中的1組P5-因子，且邊都相異，所以K4,6有P5-因子分解。

8 k-膨脹 圖G的2-膨脹。 G* v1,1 v1,2 v2,1 v2,2 v4,1 v4,2 v3,1 v3,2 G v1 v2 v4 v3

9 Km,n的P2k-因子分解

10 K4,4有P2-因子分解 假設A={a1,a2,a3,a4}和B={b1,b2,b3,b4}為K4,4的二分點集合，左邊是定義於{1,2,3,4}的4階拉丁方陣。 a1 a2 a3 a4 b1 b2 b3 b4 1 2 3 4 1 2 3 4 所以K4,4有P2-因子分解。

11 定理 假設m為正整數， 則Km,m有P2-因子分解。

12 定理. 設k, m, n 為正整數，若Km,n有P2k-因子分解， 則 m = n且m  0(mod k(2k-1))。
假設每個P2k-因子中含有 t 個P2k，因為P2k有 2k 個點且為二分圖，故每個二分點集合包含 k 個點，由點數計算可以得到 m = kt = n 由邊數的計算，每組P2k-因子有 條邊，故 Km,n可分割成 組 P2k-因子。 所以m ≡ 0(mod k(2k-1))。

13 K6,6有P4-因子分解 a1 a2 b1 b2 (1).令K2,2的二分點集合為A={a1,a2}，B={b1,b2}，令G=a1b1a2b2，則G為K2,2的一個P4-因子。 (2).由G可建構G+(i,j) 與G同構。 G (3). 將G+(i,j)的每個邊標記為ki+j+1。 a1 a2 b1 b2 G+(0,0) 1 2 3 4 a1 a2 b1 b2 G+(0,1) G+(1,0) a1 a2 b1 b2 a1 a2 b1 b2 G+(1,1)

14 K6,6有P4-因子分解 (4). G+(i,j)聯集起來可形成3K2,2，且3K2,2的每個邊都有標記。 3K2,2 a2 a1 b1

15 K6,6有P4-因子分解 所以K6,6可分割成4組邊相異的P4-因子，因此K6,6有P4-因子分解。 a1,1 a2,1 b1,1 b2,1
3 4 2 a1,2 a1,3 a2,1 a2,2 a2,3 a1,1 a2,1 b1,1 b2,1 a1,2 a1,3 a2,2 a2,3 b1,2 b1,3 b2,2 b2,3 a1,1 a2,1 b1,1 b2,1 a1,2 a1,3 a2,2 a2,3 b1,2 b1,3 b2,2 b2,3 所以K6,6可分割成4組邊相異的P4-因子，因此K6,6有P4-因子分解。

16 設k為正整數， 則Kk(2k-1),k(2k-1)有P2k-因子分解
定理

17 K6,6有P4-因子分解，則K12,12有P4-因子分解 A B

18 K6,6有P4-因子分解，則K12,12有P4-因子分解 b1,1 b1,2 b1,3 b1,4 b1,5 b1,6 b2,1 b2,2
a1,1 1 3 4 2 5 7 8 6 a1,2 a1,3 a1,4 a15 a1,6 a2,1 a2,2 a2,3, a2,4 a2,5 a2,6

19 令 t 為大於等於2的正整數，若Km,n有Pt-因子分解，則對於每一個正整數s，Kms,ns有Pt-因子分解。
定理 令 t 為大於等於2的正整數，若Km,n有Pt-因子分解，則對於每一個正整數s，Kms,ns有Pt-因子分解。

20 定理. Km,n有P2k-因子分解，若且唯若 m=n且m≡0 (mod k(2k-1))。
結果： 1. 假設m為正整數，則Km,m有P2-因子分解。 2. 設k為正整數，則Kk(2k-1),k(2k-1)有P2k-因子分解 3. 令 t 為大於等於2的正整數，若Km,n有Pt-因子分解， 則對於每一個正整數 s，Kms,ns有Pt-因子分解。 定理. Km,n有P2k-因子分解，若且唯若 m=n且m≡0 (mod k(2k-1))。

21 Km,n的P2k+1-因子分解

22 定理. 假設k為正整數，若Km,n有P2k+1-因子，則 (i)m+n≡0(mod(2k+1))
定理. 假設k為正整數，若Km,n有P2k+1-因子，則 (i)m+n≡0(mod(2k+1)). (ii)km  (k+1)n, kn  (k+1)m。 A B x個 y個 假設 F 為Km,n 的一組P2k+1-因子。 從點數來看，因為|V(Km,n)| = m+n且|V(P2k+1)|=2k+1， 所以 F 中含有(m+n)/(2k+1)個P2k+1，故 m+n≡ 0(mod(2k+1)) 。 因為F為Km,n的生成子圖，得kx+(k+1)y=m和(k+1)x+ky=n，所以 因為x，y都大於等於0，所以 km (k+1)n, kn (k+1)m 。

23 m=7, n=8, k=2 A B 所以K7,8有P5-因子。

24 定理 假設 k 為正整數，則 Km,n有 P2k+1-因子的充分必要條件為 (1) m+n≡ 0(mod(2k+1))， (2) km(k+1)n且 kn  (k+1)m。

25 因為P2k+1有2k條邊且每組P2k+1-因子有(m+n)/(2k+1)個P2k+1，所以每一組P2k+1-因子有
定理. 假設k為正整數，若Km,n有P2k+1-因子分解，則 (i)m+n 0(mod(2k+1)) (ii)km (k+1)n，kn (k+1)m (iii) 是整數。 因為P2k+1有2k條邊且每組P2k+1-因子有(m+n)/(2k+1)個P2k+1，所以每一組P2k+1-因子有 條邊，又|E(Km,n)| = mn，故得Km,n 可分割成 組P2k+1-因子， 所以 是整數。

26 定理. 若Km,m有P2k+1-因子分解，則 m≡0 (mod 4k(2k+1))。
(2k+1)m/4k為正整數，所以gcd(2,2k+1)=1，gcd(4k,2k+1)=1，得 m≡0 (mod 2k+1) ， m≡0 (mod 4k) ， 故m ≡0(mod 4k(2k+1)) 。

27 K12,12有P3-因子分解 a1 a2 a3 b1 b3 b2 (1).令K3,3的二分點集合為A={a1,a2,a3}，B={b1,b2,b3}，令G=a1b1a2∪b2a3b3，則G為K3,3的一個P3-因子。 G b1 b2 b3 a1 1 a2 a3 (2).利用 G 可得與 G 同構的G+(i,j)並將 G+(i,j) 的每個邊標記為(2k+1)i+j+1。

28 1,5,6,7 2,4,6 3,4,5 1,4 2,5,7 3,6,7 2,3,4,7 1,3,5 1,2,6 1,5,6,7 2,4,6,8 3,4,5 1,4,8 2,5,7 3,6,7,8 2,3,4,7 1,3,5,8 1,2,6 1,5,6,7 2,4,6,8 3,4,5,9 1,4,8,9 2,5,7,9 3,6,7,8 2,3,4,7 1,3,5,8 1,2,6,9 1,5,6 2,4,6 3,4,5 1,4 2,5 3,6 2,3,4 1,3,5 1,2,6 1,5 2,4 3,4,5 1,4 2,5 3 2,3,4 1,3,5 1,2 2 1,2 2 3 2,3 1,3 1,2 2,4 3,4 1,4 2 3 2,3,4 1,3 1,2 b1 b2 b3 a1 1 a2 a3 b1,1 b1,2 b1,3 b1,4 a1,1 1 5 6 7 a1,2 a1,3 a1,4

29 為了方便觀察我們把9個4階拉丁方陣放在一起：
K12,12有P3-因子分解 b1,1 b1,2 b1,3 b1,4 b2,1 b2,2 b2,3 b2,4 b3,1 b3,2 b3,3 b3,4 a1,1 1 5 6 7 2 4 8 3 9 a1,2 a1,3 a1,4 a2,1 a2,2 a2,3 a2,4 a3,1 a3,2 a3,3 a3,4 為了方便觀察我們把9個4階拉丁方陣放在一起：

30 定理 假設 k 為正整數，則 K4k(2k+1),4k(2k+1)有P2k+1-因子分解。

31 定理. 假設 k 為正整數，則 Km,m有P2k+1-因子分解的 充分必要條件為 m≡0(mod(4k)(2k+1))。
結果 4.若Km,m有P2k+1-因子分解，則 m≡0 (mod 4k(2k+1))。 5. 假設k為正整數，則K4k(2k+1),4k(2k+1)有P2k+1-因子分解 3. 令 t 為大於等於2的正整數，若Km,n有Pt-因子分解， 則對於每一個正整數 s，Kms,ns有Pt-因子分解。 定理. 假設 k 為正整數，則 Km,m有P2k+1-因子分解的 充分必要條件為 m≡0(mod(4k)(2k+1))。

32 K3,4有P7-因子分解 令K3,4的二分點集合為A={a1,a2,a3}和B={b1,b2,b3,b4} ，
F1=b1a1b2a2b3a3b4，F2=b3a1b4a2b1a3b2，所以F1、F2為K3,4的兩組邊相異P7-因子，因此K3,4有P7-因子分解。 a1 a2 a3 b1 b2 b3 b4

33 定理 假設k為奇數， 則Kk,(k+1)有P2k+1-因子分解。

34 K4,6有P5-因子分解 令K4,6的二分點集合為A={a1,a2,a3,a4}和B={b1,b2,b3,b4,b5,b6}。
F1=b1a1b2a2b3b4a3b5a4b6，F2=b3a1b4a2b5b6a3b1a4b2 ，F3=b5a1b6a2b1b2a3b3a4b4， 所以F1、F2、F3為 K4,6的三組邊相異P5-因子， 故K4,6有P5-因子分解。 a1 a2 a3 a4 b1 b2 b3 b5 b6 b4 a1 a2 a3 a4 b1 b2 b3 b5 b6 b4 a1 a2 a3 a4 b1 b2 b3 b5 b6 b4

35 假設k為正整數,則K2k,2(k+1)有P2k+1-因子分解。
定理 假設k為正整數,則K2k,2(k+1)有P2k+1-因子分解。

36 結果 6. 假設k為正整數且k為奇數，對於所有正整數 s，則Kks,(k+1)s有P2k+1-因子分解。

37 謝謝各位老師聆聽 END