现在的位置: 首页 > 综合 > 正文

弦图判断

2017年12月13日 ⁄ 综合 ⁄ 共 376字 ⁄ 字号 评论关闭
定义:
无向图中,如果任意边数大于3的环,至少存在一条边连接环中不相邻的某两
个点,则称此图为弦图(Chordal Graph)。

zoj1015的题目:
判断无向图是否为弦图,是则输出Perfect,否则输出Imperfect。

以下是时间复杂度为O(n+m)的算法,n是图的点数,m是图的边数。
第一步:给节点编号
设已编号的节点集合为A,未编号的节点集合为B
开始时A为空,B包含所有节点。
for num=n-1 downto 0 do
{
在B中找节点x,使与x相邻的在A集合中的节点数最多,将x编号为num,
并从B移入A
}
第二步:检查
for num=0 to n-1 do
{
对编号为num的节点x,设所有编号大于num且与x相邻的节点集合为C,
在集合C中找出编号最小的节点y,如果集合C中存在不等于y的节点z,
且y与z间没有边,则此图不是弦图,退出。
}
检查完了,则此图是弦图。 
 

抱歉!评论已关闭.