c＃鄰接矩陣蠍子

Question

我有一個問題開始這項任務： 一個n-vertex圖是一個蠍子，如果它有一個度數爲1的頂點（蜇）連接到一個二級頂點（尾部）連接一個頂點n-2級（身體）與其他n-3級（足部）連接。有些腳可能連接到其他腳。設計一個算法來決定給定圖形是否代表蠍子。 。 我應該使鄰接矩陣，然後嘗試基本搜索與尾巴只有一個連接，並與尾巴和身體做同樣的事情... ...？

Answer 1

你開始通過確定各頂點的程度（從鄰接矩陣或鄰接列表或任何其他方式，這是可能的），則選擇爲身體中心n-2度的一個頂點（僅存在一個這樣的頂點如果n > 4和你的圖形是一個蜘蛛，也不應該有頂點n-1）。如果圖形是蜘蛛，刺頭是身體中心不相鄰的一個頂點。檢查蟄頭是否具有度數1.然後檢查蟄頭是否連接到度數爲2的頂點（即st尾關節）。如果n <= 4，你只能得到退化的蜘蛛（對於n=4，蜘蛛有一條腿，因爲n=3蜘蛛沒有腿，因爲n=2,n=1或n=0你不能有蜘蛛）。