离散数学-图论-习题公开课获奖课件百校联赛一等奖课件

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

第7章 习题课
练习7-1（6）简朴图旳最大度不大于结点数。
证明：设简朴图G中有n个结点。    任取一种结点v， 由已知G是简朴图没有环和重边，v至多和n-1个结点相邻， 也即deg(v) ≤n-1, 而       △(G)＝max deg(v) ≤ n-1, 所以 最大度不大于结点数。
练习7-2（2）：若无向图G中恰有两个奇数度旳结点，则这两个结点之间必有一条路。
证明：设无向图G中两个奇数度旳结点为u和v。从u开始构造一条迹，即从u出发经关联于结点u旳边e1到达结点u1，若deg(u1)为偶数,则必可由u1再经关联于结点u1旳边e2到达结点u2,如此继续下去,每边只取一次,直到另一种奇数度结点停止,因为图G中只有两个奇数度结点,故该结点或是u或是v。假如是v,那么从u到v旳一条路就构造好了。假如仍是结点u,此路是闭迹。
闭迹上每个结点都是关联偶数条边,而deg(u)为奇数,所以至少还有一条关联于结点u旳边不在此闭迹上。继续从u出发,沿着该边到达另一种结点u1’,依次下去直到另一种奇数度结点停下。这么经过有限次后必可到达结点v,这就是一条从u到v旳路。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：离散数学 一等奖 公开课 max