作业帮 > 数学 > 作业

图论和染色问题证明n个点任意连接n条线段,必存在一个圈(即封闭图形)等待PS:分值还会提高..

来源:学生作业帮 编辑:拍题作业网作业帮 分类:数学作业 时间:2024/11/01 07:25:16
图论和染色问题
证明n个点任意连接n条线段,必存在一个圈(即封闭图形)
等待
PS:分值还会提高..
一个图,n个结点,n条边,证明存在回路,讨论:
1.不是连通图,设有k个连通支H1,H2...Hk.结点数分别是n1,n2...nk;边数分别是m1,m2...mk.
n1+n2+...+nk=n,m1+m2+...+mk=n.那么k个连通支中必有一个,mk>=nk.
2.是连通图,边数=结点数
由1,2问题转化为,边数>=结点数 的连通图,存在回路.
反证:假设没有回路,根据树的定义,不含回路的连通图为树,根据树的定义,边数=结点数-1,与条件矛盾...