计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2013年
22期
52-54
,共3页
色多项式%伴随多项式%色唯一%伴随唯一
色多項式%伴隨多項式%色唯一%伴隨唯一
색다항식%반수다항식%색유일%반수유일
chromatic polynomial%adjoint polynomial%chromatic uniquness
如果两个图的色多项式相等，称这两个图色等价。如果与一个图色等价的所有图都与这个图同构，称这个图色唯一。类似的，如果两个图的伴随多项式相等，称这两个图伴随等价。如果与一个图伴随等价的所有图都与这个图同构，称这个图伴随唯一。众所周知，两个图色等价当且仅当它们的补图伴随等价；一个图色唯一当且仅当它的补图伴随唯一。给出了一类图伴随唯一的一个充分必要条件，因而给出了它的补图色唯一的一个充分必要条件。
如果兩箇圖的色多項式相等，稱這兩箇圖色等價。如果與一箇圖色等價的所有圖都與這箇圖同構，稱這箇圖色唯一。類似的，如果兩箇圖的伴隨多項式相等，稱這兩箇圖伴隨等價。如果與一箇圖伴隨等價的所有圖都與這箇圖同構，稱這箇圖伴隨唯一。衆所週知，兩箇圖色等價噹且僅噹它們的補圖伴隨等價；一箇圖色唯一噹且僅噹它的補圖伴隨唯一。給齣瞭一類圖伴隨唯一的一箇充分必要條件，因而給齣瞭它的補圖色唯一的一箇充分必要條件。
여과량개도적색다항식상등，칭저량개도색등개。여과여일개도색등개적소유도도여저개도동구，칭저개도색유일。유사적，여과량개도적반수다항식상등，칭저량개도반수등개。여과여일개도반수등개적소유도도여저개도동구，칭저개도반수유일。음소주지，량개도색등개당차부당타문적보도반수등개；일개도색유일당차부당타적보도반수유일。급출료일류도반수유일적일개충분필요조건，인이급출료타적보도색유일적일개충분필요조건。
Two graphs are chromatically equivalent if they have the same chromatic polynomials. A graph is said to be chromati-cally unique if each graph which has same chromatic polynomial is isomorphic with it. Similarly, two graphs are adjointly equiv-alent if they have the same adjoint polynomials. A graph is said to be adjointly unique if each graph which has same adjoint poly-nomial is isomorphic with it. As we all know, two graphs are chromatically equivalent if their complement are adjointly equivalent;a graph is chromatically unique if its complement is adjointly unique. In this paper, a necessary and sufficient condition of a classe graphs adjointly unique is given, thus a necessary and sufficient condition of their complement chromatically unique is given.
