文档介绍：第劝卷第3 期经济数学 V ol .解 N O .3
2 0 0 7 年 9 月 M 叭rp日E M A 竹《万 IN E C 〔)N O M IC S 卿. 2(X 介
论连通图的可重构性
谢力同,刘家壮
(山东大学数学研究所,济南,25 01 00 )
摘要本文我们利用带权核子图的可重构性证明了连通图是可重构的,从而证明了重构猜想为真.
关键词图,重构,带权核子图
中图分类号 01 57 ,5 文献标识码 A
1. 引言
本文研究的图都是有限简单图,这种图有一个基本间题就是“重构猜想”,即:如果两个图
的主子图族相同,则此两个图同构〔’(否则有反例[3] ),由于对不连
通图来说,这个猜想已被证明为真[3j ,
的符号见文献[4].

为重构的两个图同构.
“可重构”一词较一般的意义是指定义在一类图上的一种关系,如果对类中某个图‘上取
一定值(或满足一定的条件),则此类图中重构于‘的任意一个图上也取同一值(或满足同样
的条件).例如我们有下列命题:
命题连通图‘中任何两点间的邻接关系(即相邻或不相邻)是可重构的.
下一节我们将给出带权核子图的概念,并介绍带权核子图可重构的相关内容,然后在最后
一节里用它来证明连通图的可重构性.
2. 带权核子图与独点带权图
设‘是一个至少有三个点的连通图,F 是‘中任意指定的一个非空真导出子图,‘中与
F 相邻的点集记作N (F ),‘中不与F 相邻的点集记作斥(助,这时我们称三元组(F ,IN (F )!,
‘〔斥(F) 」)为‘中以F !N (F) l叫做“权”,c[ 斥(F) 」叫做“皮”.三元
组(F ,!N (F)1,c[ 斥(F )」)也可以视为由三个相互不交图F 、IN (F )1个孤立点和c[ 元(F) 〕
构成的和图F + IN (F)IK,+ c[ 斥(F)] ,显然它是G 的一个支撑子图.
设(F’,IN (F’)1,c[ 凡(F’)〕)是‘中另一个带权核子图,则这两个带权核子图同构的充
要条件是下列三个条件同时成立:
收稿日期:2(X J7 一以一加
万方数据
2 22 经济数学第从卷
①尸二尸‘; ② 1浑(尸) 1二1浑(尸‘) 1; ③ C[元(r)〕二C[凡(F’)〕.
若将‘中同构于(F ,IN (F)1,‘〔元(F)」)的带权核子图的个数记作
5((尸,1万(F ) 1,C[斥(F )]),C ),
我们则有
‘是一个至少有三个点的连通图,F 是‘的一个非空真导出子图,则
5((尸,1浑(F )1,C〔元(F )〕,C)是可重构的.
另外,当F 是‘中任意指定的一个点a 时,我们称三元组(a,IN (a) l,C[ 斥(a) 」)为‘中
以a
设‘是一个至少有三个点的连通图,a 是‘中任意指定的一个点,则 s( (a ,
1刀(a)1,G[凡(a)]),C)是可重构的.
中令