[發明專利]一種彩色k-星核分解方法

在審

• 申請號: 202110326947.1
• 申請日: 2021-03-26
• 公開（公告）號: CN112950728A
• 公開（公告）日: 2021-06-11
• 發明（設計）人: 高森;李榮華;王國仁;金福生;秦宏超
• 申請（專利權）人: 北京理工大學
• 主分類號: G06T7/90
• 分類號: G06T7/90;G06K9/62
• 代理公司: 北京圣州專利代理事務所(普通合伙) 11818
• 代理人: 劉巖

1.一種彩色k-星核分解方法，其特征在于，步驟如下：

S1、設置一個包含k個節點的k-星圖，其中一個中間節點與其他k-1個點相連，給定圖G和一個點u，u作為中間節點參與的k-星的數量記作該點的k-星度；

S2、用貪婪算法對給定的圖G進行著色，使得沒有兩個相鄰結點具有相同的顏色值；

S3、計算每個點初始的彩色k-星度；

S4、按彩色k-星度的大小對所有節點從小到大排序；

S5、每次刪除當前子圖中彩色k-星度最小的點u直到刪除所有點，并將當前的核值賦給u，同時更新該點的鄰居的彩色k-星度，最后得到每個點的彩色k-星核值以及一個節點被刪除的順序。

2.根據權利要求1所述的一種彩色k-星核分解方法，其特征在于：步驟S2中，首先先將點u的鄰居按顏色分為若干組，然后利用動態規劃的方式來計算該點作為中間節點所參與的彩色k-星的數量；

其中，動態規劃的轉移方程為：dp(c,i)＝dp(c-1,i)+dp(c-1,i-1)*cnt(i)；

dp(c,i)表示從前c種顏色中選出i種不同顏色的選法種數，可以分成兩個情況來考慮：

(1)不選第i種顏色，只從前i-1種顏色種選擇，選法種樹為dp(c-1,i)；

(2)選第i種顏色，其中第i種顏色包含cnt(i)個點，此時還需從前i-1種顏色中選c-1種顏色，這種情況下有dp(c-1,i-1)*cnt(i)種選法；

從前c種顏色中選出i種不同顏色的選法種數應為這兩種選法種數之和。

3.根據權利要求1所述的一種彩色k-星核分解方法，其特征在于：步驟S3中，通過貪婪著色，每個點u有一個顏色值，記作color(u)。若一個k-星中所有點的顏色各不相同，則稱這樣的k-星為彩色的k-星；

給定圖G和一個點u，u作為中間節點參與的彩色k-星的數量成為該點的彩色k-星度。