我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:爱彩网 > 二分图 >

怎么证明这个图示2分图 而不是汉米尔顿图

归档日期:06-27       文本归类:二分图      文章编辑:爱尚语录

  定理1 若图G=V,E具有汉密尔顿回路,则对于结点集V的每个非空子集S均有 W(G-S)≤S成立。其中W(G-S)是G-S中连通分支数。

  定理2 设G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则在G中存在一条汉密尔顿路。 定理3 设G是具有n个结点的简单图。如果G中每一对结点度数之和大于等于n,则在G中存在一条汉密尔顿回路。 定义2 给定图G=V,E有n个结点,若将图G中度数之和至少是n的非邻接结点连接起来得图G’,对图G’重复上述步骤,直到不再有这样的结点对存在为止,所得到的图,称为是原图G的闭包,记作C(G)。 定理4 当且仅当一个简单图的闭包是汉密尔顿图时,这个简单图是汉密尔顿图。

  知道合伙人数码行家采纳数:1968获赞数:10308有态度、有温度、有深度的企划运营主编向TA提问展开全部从图上可以这么看:若图G=V,E具有汉密尔顿回路,则对于结点集V的每个非空子集S均有 W(G-S)≤S成立。其中W(G-S)是G-S中连通分支数。

本文链接:http://pikeducation.com/erfentu/422.html