范氏定理的一个构造性证明
首发时间:2009-12-11
摘要:以下条件称为范条件:一个n顶点二连通图G任意两个距离是2的点u,v必定有max(d(u),d(V))≥n/2。满足范条件的图被证明是H图被称为范氏定理。范氏定理被公认为作为H图的充分条件迄今就度型条件来说是最好的一个结果。本文将对此定理给出一个构造性证明,即给出一个算法证明满足范条件的图存在H圈的同时,由此算法一定可以找出它一个H圈。
For information in English, please click here
A Constructability Proof for Fan Theorem
Abstract:Following condition called Fan-condition:Let G is a 2-connection graph on n ,if max(d(u),d(v))≥n/2 for every u,v in G and d(u,v)=2. In this paper,a algorithm for finding a H cycle in a graph ,satisfying the Fan -condition (journal of combinatorial theory,series B 37,221-227(1984))is given.
Keywords: Fan-condition H cycle H graph P-chain
基金:
论文图表:
引用
No.3746839436412605****
同行评议
共计0人参与
勘误表
范氏定理的一个构造性证明
评论
全部评论0/1000