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你不能有蜘蛛）。