至今不明白原理
无向图中，如果任意边数大于3的环，至少存在一条边连接环中不相邻的某两
个点，则称此图为弦图(Chordal Graph)，所以说这里的算法就是
第一步：给节点编号
设已编号的节点集合为A，未编号的节点集合
1 /*
2 无向图中，如果任意边数大于3的环，至少存在一条边连接环中不相邻的某两
3 个点，则称此图为弦图(Chordal Graph)
4 */
5 #include <iostream>
6 using namespace std;
7 int n,m;
8 bool map[1001][1001];
9 bool used[1001];
10 int seta[1001];
11 void number()
12 {
13 memset(used,0,sizeof(used));
14 used[1]=1;
15 seta[n]=1;
16 for(int num=n-1;num>=1;--num)
17 {
18 int Max=0;
19 int p=0;
20 for(int i=1;i<=n;++i)
21 if(!used[i])
22 {
23 int sum=1;
24 for(int k=n;k>=num;--k)
25 if(map[i][seta[k]])
26 sum++;
27 if(sum>Max)
28 {
29 Max=sum;
30 p=i;
31 }
32 }
33 seta[num]=p;
34 used[p]=1;
35 }
36 }
37 bool check()
38 {
39 int setc[1001];
40 for(int i=1;i<n;++i)
41 {
42 int x=seta[i];
43 int k=0;
44 for(int j=i+1;j<=n;++j)
45 {
46 int y=seta[j];
47 if(map[x][y])
48 setc[k++]=y;
49 }
50 if(k>1)
51 {
52 for(int j=1;j<k;j++)
53 if(!map[setc[0]][setc[j]])return 0;
54 }
55 }
56 return true;
57 }
58 int main()
59 {
60 int a,b;
61 while(scanf("%d%d",&n,&m)&&n)
62 {
63 memset(map,0,sizeof(map));
64 for(int i=1;i<=m;++i)
65 {
66 scanf("%d%d",&a,&b);
67 map[b][a]=map[a][b]=1;
68 }
69 //编号
70 number();
71 if(check())printf("Perfect\n\n");
72 else printf("Imperfect\n\n");
73 }
74 return 0;
75 }
为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间没有边，则此图不是弦图，退出。
}
检查完了，则此图是弦图。