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

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

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

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