擋得住的魅力—看你往哪逃
所謂的阻隔點是指將圖上的點標記,而該標記可使其他點無法與之連線。我們將研究『在圖A中欲使其子圖B不存在所需的最少阻隔點數。』其中討論的圖A、圖B為完全圖Km、完全二分圖Kmn、圈圖Cm、路徑圖Pm 及其組合。 一、推導出『在圖Km、圖Cm、圖Pm、圖Kmn中使圖Kx、圖Cx、圖Px、圖Kxy 不存在』這十六種組合所需最少阻隔點數的一般式。二、『在圖Km*Pq中使圖Cx不存在』中發現,當x-m>2時,圖Km*Pq中的阻隔點數需逐層討論。當x-m≦2時,圖Km*Pq中最少阻隔點數的擺法為『使每層Km的點數小於x且任相鄰兩不同層Km上的點間最多存在一連通路徑』。 三、『在圖Kmn*Pq中使圖Cx不存在』中發現,欲使阻隔點總數最少,需將阻隔點放在Kmn的短邊且隨著n與x值不同,阻隔點的擺法有其規則。四、『在圖Pm*Pq中使圖Cx不存在』中,x=4時,可以分割方式得到阻隔點的擺法。在x=6時,改以固定q值討論橫線上的連通路徑方式討論阻隔點數。