算法分析實踐環(huán)節(jié)習題集-2016

1、信息工程學院算法分析實踐環(huán)節(jié)習題集2016年序號項目名稱任務描述設計要求指導教師人數(shù)1搜索圖中最小控制頂點集合給定一個無向連通子圖G=(VE)，其中V表示圖中頂點集合，E表示邊的集合。G的最小控制頂點集合為V的一個子集，S；假設集合R表示V排除集合S后剩余頂點集合，即=V；則最小控制頂點集合S滿足約束條件:R中任意一個頂點至少與S的一個頂點直接相連。例如下圖中紅色頂點集合MDset表示一個最小控制頂點集合，任意一個綠色的頂點至少與一個紅

2、色頂點直接相連。讀取文件(網(wǎng)絡)，設計算法求解最小控制頂點集合。文件中數(shù)據(jù)格式如下：ABBCCDBD每一行表示圖的兩個頂點，且兩個頂點之間有一條邊。算法：Input：圖文件Output:最小控制頂點集合劉全中1后的集合；，則.(3)重復步驟1和2，直到集合G不發(fā)生變化，即收斂，算法結束。算法：Input:圖文件Output:圖中所有的內(nèi)聚性最大的cluster.4最大匹配率算法設計與實現(xiàn)兩個圖A和B之間的匹配率計算公式：，其中|A|表示

3、圖A中頂點個數(shù)，表示圖A和圖B共同頂點組成的子圖。例如下圖中R1和P1的匹配率為：(44)(45)=0.8.給定兩組子圖RP例如，如下圖R=R1R2，P=P1P2P3圖中的邊上的權值表示兩個圖之間的匹配率。R和P之間最大匹配率計算方法如下：1.找出一組邊，使得P和R中的每一個頂點最多出現(xiàn)一條邊上，而且邊的權重累加和最大。2.最大匹配率為：第1步選擇邊的權重之和除以R中子圖的個數(shù)例如:下圖中最大匹配率為：(0.80.75)2Input：兩