哈密顿图
h哈密顿通路(回路)与哈密顿图 通过图G的每个结点一次，且仅一次的通路(回路)，就是哈密顿通路(回路). 存在哈密顿回路的图就是哈密顿图.
判断哈密顿图是较为困难的.
h哈密顿图的充分条件和必要条件
(1) 在无向简单图G=<V,E>中½V½³3,任意不同结点 ,则G是哈密顿图.(充分条件，定理4)
(2) 有向完全图D＝<V,E>, 若 ，则图D是哈密顿图. (充分条件，定理5推论)
(3) 设无向图G=<V,E>,"V1ÌV，则P(G－V1)£½V1½(必要条件，定理3)
若此条件不满足，即$V1ÌV，使得P(G－V!)>½V1½,则G一定不是哈密顿图(非哈密顿图的充分条件). |
|
|