无向图

来自计算思维百科
跳转至: 导航搜索
无向图1.png

对于一张图,如果边没有方向就称为无向图。

基本概念

一个无向图G是一个二元组<V,E>,其中:

1.V是一个非空有穷集合,称为G的顶点集,V中元素称为顶点或结点。

2.E是无序积V&V的一个多重子集,称为G的边集,E中元素称为无向边或简称边。

直观来说,若一个图中每条边都是无方向的,则称为无向图。

即不含平行边也不含环的无向图称为无向简单图。

设G=<V,E>是n阶无向简单图,若G中任何顶点都与其余n-1个顶点相邻,则称G为n阶无向完全图。

应用范围

无向图能用来直观地表示事物之间的关系,常用于求解最短路径问题。

使用方法及步骤

用小圆圈或者实心点表示顶点,用连接两个顶点的线段表示边,其中顶点的位置、线段的曲直及是否相交都无关紧要。

应用案例

应用1-线路安排

案例:

某班班长要组织一次班游,计划从学校出发,终点定在人民公园。希望尽量找到两地之间的最短路径以避免不必要的麻烦。

解决步骤:

此时,画出无向图可以帮助我们直观简便地找到最短路径。以各个街道站点作为顶点,用线段连接相通的两个站点,线段上标出该路段的长度,最后找到总长度最少的一个方案。

下面假设两地间经过以下站点来画出具体无向图:

无向图2.png

由图比较可得:图中红色路径长度为2+4+3=9,为最短路径

应用2-交际圈

案例:

你的朋友圈中有A、B、C、D、E、F、G等人,而A、B、C、D、E、F、G中AC,AE,CE,BF,BG,FG,DG两两相互认识,此时,我们可以用无向图来表示两两之间的关系,两者认识可用线段连接。

解决步骤:

可画出无向图表示各自之间的关系,可以很容易看出G具有比较广泛的交际圈。

无向图3.png

可以体现的计算思维

用无向图来解决问题体现了计算思维的抽象思想,把事物之间的关系抽象成图,从而使得问题清晰易懂,对解决问题有很大的帮助。