作业帮一道离散数学图论题,急!
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/07/16 20:22:33
一道离散数学图论题,急!
题目是：
若一无向图有5个顶点,如果它的补图是连通图,那么这个无向图最多有几条边?
答案是6.
请问详解是什么?说仔细点,谢谢!
题目是：
若一无向图有5个顶点,如果它的补图是连通图,那么这个无向图最多有几条边?
答案是6.
请问详解是什么?说仔细点,谢谢!
首先知道什么是无向图的补图吧?就是所有节点保留,两点之间有边的,补图里面没边,两点之间没边的,补图里面有边,原图边数＋补图边数等于C(5,2)=10……所以求无向图最多有多少边,就是求补图最少有多少边,既然它说补图是连通的,所以补图最少有4条边（树图）,10-4=6,所以原图中最多就有6条边了～
另外这道题是有前提的,就是无向简单图,简单图是指无自环、无平行边.
有问题请补充,满意请采纳～
再问： 请问那10是怎么来的？还有另外问一下，已知一个完全图有6个顶点，那它有多少条边呢？谢谢
再答： 10就是5点完全无向简单图的边数，就是两两点之间都有边，所以用排列组合得到是10。 6个点的完全图就有15条边。n个点的无向完全简单图有C(n,2)=n(n-1)/2条边。 如果没有学过排列组合，稍微看看书吧。
另外这道题是有前提的,就是无向简单图,简单图是指无自环、无平行边.
有问题请补充,满意请采纳～
再问： 请问那10是怎么来的？还有另外问一下，已知一个完全图有6个顶点，那它有多少条边呢？谢谢
再答： 10就是5点完全无向简单图的边数，就是两两点之间都有边，所以用排列组合得到是10。 6个点的完全图就有15条边。n个点的无向完全简单图有C(n,2)=n(n-1)/2条边。 如果没有学过排列组合，稍微看看书吧。