图论习题解析



解答题 (共 12 题 ),解答过程应写出必要的文字说明、证明过程或演算步骤
设图 $G$ 中有 9 个结点, 每个结点的度不是 5 就是 6 。试证明 $G$ 中至少有 5 个 6 度结点或至少有 6 个 5 度结点。



(1) $n(n \geq 1)$ 阶无向完全图与有向完全图各有多少条边?
(2) 完全二部图 $K_{n, m}$ 中共有多少条边?
(3) $n$ 阶 $k$ 正则图中共有多少条边?



寻找一个 $n(n \geq 2)$ 阶简单图 $G$, 使得它的边数 $m$ 为 $\frac{(n-1)(n-2)}{2}$ 。



(1) $m$ 条边的 $n$ 阶无向简单图 $G$ 可产生多少个定向图?
(2) 画出星形图 $K_{1,2}$ 的全部的定向图。



有 $n$ 个药箱, 若每两个药箱里有一种相同的药, 而每种药恰好放在两个箱中, 问共有多少种药品?



某一次聚会的成员到会后相互握手。试用图论的知识说明与奇数个人握手的人数一定是一个偶数。



证明 3 正则图必有偶数个结点。



若有 $n$ 个人, 每个人恰恰有三个朋友, 则 $n$ 必为偶数。



在 $n(n \geq 2)$ 阶简单图 $G$ 中, $n$ 为奇数, 问 $\bar{G}$ 与 $G$ 的奇度结点的个数有何关系?



设 $G$ 为至少有两个结点的简单图, 证明: $G$ 中至少有两个结点度数相同。



证明: 在至少有 2 个人的人群中, 至少有 2 个人, 他们有相同的朋友数。



将无向完全图 $K_6$ 的边随意地涂上红色或绿色, 证明: 无论如何涂法, 总存在红色的 $K_3$ 或绿色的 $K_3$ 。



非会员每天可以查看15道试题。 开通会员,海量试题无限制查看。

  • 无限看试题

  • 下载试题

  • 组卷
开通会员

热点推荐

试卷二维码

分享此二维码到群,让更多朋友参与

试卷白板

试卷白板提供了一个简单的触摸书写板,可供老师上课、或者视频直播时, 直接利用白板给学生讲解试题,如有意见,欢迎反馈。