标题: 出一道看似简单但很BT的数学题 [打印本页]
作者:
庸人自扰 时间: 2004-12-22 22:34
9 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个奇度顶点？
作者:
天痕 时间: 2004-12-22 22:40
这是什么题目？
另外要是补图不闭合或者不连通怎么算？
最好先说清楚，否则很难算。
作者:
青木风亮 时间: 2004-12-22 22:48
玩图论的大哥都来了 偶得回去补课了
作者:
金圭子 时间: 2004-12-23 12:35
我先问问我的概念理解对不对：
简单图就是点之间连线组成的那个东西吧？（那复杂图是虾米呢？）
每个点称为“顶点”
如果一个顶点上的线是奇数就是“奇度顶点”
然后把没连线的点连一下，把已经连的线擦掉，这个就是“补图”
这个概念是这么回事情么？
那如果9个点完全连接，每个点上应该有8根线，那么补图里面，奇数的点还是奇数，偶数的点还是偶数（或者没了）。
如果不存在“BT”的话应该还是4个…………
作者:
金圭子 时间: 2004-12-23 12:37
关键就是这个“简单图”和这个“补图”是怎么定义的…………
比如这个两者带不带“环”？
作者:
重阳 时间: 2004-12-23 12:37
楼上两位的观点都和我是一样的……
作者:
金圭子 时间: 2004-12-23 12:40
原帖由重阳于2004-12-23, 12:37:17发表
楼上两位的观点都和我是一样的……
你楼上和楼上的楼上都是我…………暴汗………………
作者:
青石 时间: 2004-12-25 01:58
4个
作者:
晨山尚书 时间: 2004-12-25 02:09
6个，概念都忘的差不多了。
作者:
青石 时间: 2004-12-25 11:29
楼主神龙见首不见尾
哎……
我介绍一下补图的定义：
简单图G的补图H是指和G有相同顶点集V的一个简单图，H中的两个顶点相邻当且仅当它们在中G不相邻。
由补图的定义可以知道，一个简单图与它的补图的和刚好是一个完全图
9阶完全图，每个顶点的度均为8。G有四个奇度顶点，因为8是偶数，所以这四个顶点在补图中的度数还是奇的，其余的依然是偶的。
从而，补图中奇度顶点刚好有4个。
上面的过程与结论不知有没有错，请大家指教！！
作者:
青木风亮 时间: 2004-12-25 11:44
我认为楼上的正确
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |