同構因子分解

同構因子分解(isomorphic factorization),是同構因子分解圖的一種特殊的因子分解。

同構因子分解(isomorphic factorization)圖的一種特殊的因子分解.圖G的邊集E (G)的一個劃分E1,Ez,...,E稱為G的一個同構因子分解,若對於任意i, j:liGjm,E與E,在G上的導出子圖同構.圖G可分解為t個同構因子的一個必要條件是t可整除G的邊數.這個條件稱為G關於t的可分性條件.稱圖G是有理圖,若對任意整數t,G關於t的可分條件也是G可同構因子分解的充分條件.已經證明:完全圖和完全等分多部圖(即,將完全圖的節點用基數相同的獨立集代替使得任一節點與其他部的所有節點都相鄰)等都是有理的.當然,不是任何圖都是有理的.

相關詞條

熱門詞條

聯絡我們