一道离散数学图论题,急!题目是：若一无向图有5个顶点,如果它的补图是连通图,那么这个无向图最多有几条边?答案是6.请问详

一道离散数学图论题,急!
题目是：
若一无向图有5个顶点,如果它的补图是连通图,那么这个无向图最多有几条边?
答案是6.
请问详解是什么?说仔细点,谢谢!
一米阳光1984 1年前 已收到2个回答 举报
赞

石青沸冰 幼苗

共回答了16个问题采纳率：87.5% 举报

首先知道什么是无向图的补图吧?就是所有节点保留,两点之间有边的,补图里面没边,两点之间没边的,补图里面有边,原图边数＋补图边数等于C(5,2)=10……所以求无向图最多有多少边,就是求补图最少有多少边,既然它说补图是连通的,所以补图最少有4条边（树图）,10-4=6,所以原图中最多就有6条边了～
另外这道题是有前提的,就是无向简单图,简单图是指无自环、无平行边.
有问题请补充,满意请采纳～

1年前 追问

9

一米阳光1984 举报

请问那10是怎么来的？还有另外问一下，已知一个完全图有6个顶点，那它有多少条边呢？谢谢

举报 石青沸冰

10就是5点完全无向简单图的边数，就是两两点之间都有边，所以用排列组合得到是10。 6个点的完全图就有15条边。n个点的无向完全简单图有C(n,2)=n(n-1)/2条边。 如果没有学过排列组合，稍微看看书吧。

饮火听寒驻水 幼苗

共回答了32个问题 举报

我们知道，这其实就是数学中的反证法。 但是，在他极为细致深入的推理过程垂直于同一直线的两条直线，当两端延长的时候，离散到无穷。 不存在相似的

1年前

1
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 18 q. 0.021 s. - webmaster@yulucn.com