离散数学：设G是有n个结点的简单图,其最小度大于等于（n+q)/2
离散数学：设G是有n个结点的简单图,其最小度大于等于（n+q)/2
证明：G中存在包含任意q条互不相邻边的哈密顿回路
证明：G中存在包含任意q条互不相邻边的哈密顿回路
赞 Julia_Chen 幼苗
共回答了15个问题采纳率：93.3% 举报
问：G是n个结点、m条边和r个面的连通平面图,则m等于（ ）.
A、n+r-2
B、n-r+2
C、n-r-2
D、n+r+2
答：正确答案是：A
欧拉定理：设有一个连通的平面图G,共有v个结点,e条边和r个面,则欧拉公式 v-e+r=2 成立.
在本题中,n-m+r=2
解得 m=n+r-2
{[希望它对你有一定的帮助,不好意识我尽力了!]}
A、n+r-2
B、n-r+2
C、n-r-2
D、n+r+2
答：正确答案是：A
欧拉定理：设有一个连通的平面图G,共有v个结点,e条边和r个面,则欧拉公式 v-e+r=2 成立.
在本题中,n-m+r=2
解得 m=n+r-2
{[希望它对你有一定的帮助,不好意识我尽力了!]}
1年前 追问
3
我找到一份资料，可能对你有用！由于太长，分段发给你！
哈密顿回路由来 天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。 这个问题和著名的过桥问题的不同之处在于，某些城市之间的旅行不一定是双向的。比如A→B不允许,但B→A是允许的。 换一种说法，对于一个给定的网络，确定起点和终点后，如果存在一条路径，且满足每个顶点只被访问一次的情况下能穿过这个网络，我们就说这个网络存在哈密顿路径。 算法 哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。 从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。 要满足两个条件：
可能相似的问题
-
1年前1个回答
-
1年前1个回答
你能帮帮他们吗