早教吧作业答案频道 -->物理-->
极大连通子图的概念是什么?它跟极小连通子图有什么关系?除了极大极小连通子图还有其他种类的连通子图吗别说书上有.看不懂
题目详情
极大连通子图的概念是什么?它跟极小连通子图有什么关系?除了极大极小连通子图还有其他种类的连通子图吗
别说书上有.看不懂
别说书上有.看不懂
▼优质解答
答案和解析
首先先明确两个概念,无向图和有向图;其次,明确一个概念,极大连通子图可以存在于无向图中,也可以存在于有向图中(下面进行分析);最后知道,极小连通子图只存在于连通的无向图中,不存在于不连通的无向图和有向图中.
也就是说,极大连通子图和极小连通子图适用条件是不一样的,尽管它们看起来貌似很接近.
下面先说无向图中的极大连通子图.无向图中的极大连通子图也叫连通分量.无向图可以分成两种类型:连通的无向图、不连通的无向图.连通的无向图只有一个极大连通子图,即它本身,因为不存在另一个连通的子图包含的点和边比它本身还要多,所以叫作极大连通子图.不连通的无向图可以拆分为若干个连通的无向图,如果我们在拆分时注意把能连通的点边都放在一个连通子图中,使这个连通子图足够大,以至于再多包含一个点或边它就变成不连通的了,我们称这个连通子图为极大连通子图,也叫连通分量.
下面说极小连通子图,极小连通子图只存在于连通的无向图中,也就是说该图中只有一个连通分量(极大连通子图),之所以说它极小,是因为极小连通子图只要求包含图中所有顶点及其比顶点数量少一个的边(且不能成环),也就是说如果给极小连通子图任意两个顶点间加入一条边,则必有环.
这里的极大和极小不是指一个意思,不要弄混了,极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的.
提一下有向图中的极大连通子图.
有向图可以分为强连通图、弱连通图、单向连通图、不连通图.极大连通子图一般只在强连通图中讨论,即强连通分量.至于有向图的这几种类型,
也就是说,极大连通子图和极小连通子图适用条件是不一样的,尽管它们看起来貌似很接近.
下面先说无向图中的极大连通子图.无向图中的极大连通子图也叫连通分量.无向图可以分成两种类型:连通的无向图、不连通的无向图.连通的无向图只有一个极大连通子图,即它本身,因为不存在另一个连通的子图包含的点和边比它本身还要多,所以叫作极大连通子图.不连通的无向图可以拆分为若干个连通的无向图,如果我们在拆分时注意把能连通的点边都放在一个连通子图中,使这个连通子图足够大,以至于再多包含一个点或边它就变成不连通的了,我们称这个连通子图为极大连通子图,也叫连通分量.
下面说极小连通子图,极小连通子图只存在于连通的无向图中,也就是说该图中只有一个连通分量(极大连通子图),之所以说它极小,是因为极小连通子图只要求包含图中所有顶点及其比顶点数量少一个的边(且不能成环),也就是说如果给极小连通子图任意两个顶点间加入一条边,则必有环.
这里的极大和极小不是指一个意思,不要弄混了,极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的.
提一下有向图中的极大连通子图.
有向图可以分为强连通图、弱连通图、单向连通图、不连通图.极大连通子图一般只在强连通图中讨论,即强连通分量.至于有向图的这几种类型,
看了 极大连通子图的概念是什么?它...的网友还看了以下:
吴韵同学把143只乒乓球放进两种盒子中,每个大盒子装12个,每个小盒子装5个,恰好装完.那么大盒子 2020-05-13 …
张红同学把143只乒乓球放进大、小两种盒子中,每个大盒子装12只,每只小盒子装5只,恰好装完.那么 2020-05-13 …
吴韵同学把143只乒乓球放进两种盒子中,每个大盒子装12个,每个小盒子装5个,恰好装完.那么大盒子 2020-05-13 …
等差数列{an}中,a3=8,a7=20.若数列{1/an*an+1}的前n项和为4/25.则n的 2020-06-18 …
有三头大狮子和三头小狮子,它们分别为父子.他们来到河边,要渡河,河边有一条船.小狮子和大狮子在一块 2020-06-19 …
这么冷的天,昼夜温差这么大,蚊子怎么还没有死光啊?这不科学! 2020-07-04 …
吴韵同学把143只乒乓球放进两种盒子中,每个大盒子装12个,每个小盒子装5个,恰好装完.那么大盒子 2020-07-15 …
吴韵同学把143只乒乓球放进两种盒子中,每个大盒子装12个,每个小盒子装5个,恰好装完.那么大盒子 2020-07-15 …
吴韵同学把143只乒乓球放进两种盒子中,每个大盒子装12个,每个小盒子装5个,恰好装完.那么大盒子 2020-07-15 …
为什么植物下表皮叶绿体大?注意是为什么大,别答非所问哦~不是为什么多 2020-11-29 …