个性化阅读
专注于IT技术分析

图Graph的类型

点击下载

1.空图:空图定义为仅包含孤立顶点的图。

示例:图中所示的图为空图, 并且这些顶点是孤立的顶点。

图Graph的类型

2.无向图:无向图G由一组顶点V和一组边E组成。该边集包含无序顶点对。如果(u, v)∈E, 那么我们说u和v由边连接, 其中u和v是集合V中的顶点。

示例:设V = {1, 2, 3, 4}, E = {(1, 2), (1, 4), (3, 4), (2, 3)}。绘制图形。

解决方案:可以通过多种方式绘制图形。

其中两个如下:

图Graph的类型

3.多重图形:如果在一个图形中允许在同一组顶点之间有多个边, 则称为多重图形。换句话说, 它是具有至少一个环或多个边的图。

图Graph的类型

4.有向图:有向图或有向图G被定义为无序对(V, E), 其中V是称为顶点的点集, E是边的集合。图G中的每个边都分配了一个方向, 并用有序对(u, v)标识, 其中u是初始顶点, v是结束顶点。

示例:考虑图G =(V, E), 如图2所示。确定图G的顶点集和边集。

图Graph的类型

解:图G =(V, E)的顶点和边集如下

G = {{1, 2, 3}, {(1, 2), (2, 1), (2, 2), (2, 3), (1, 3)}}。

5.无向完全图:n个顶点的无向完全图G =(V, E)是其中每个顶点彼此连接的图, 即, 边存在于每对不同的顶点之间。用Kn表示。具有n个顶点的完整图将具有边。

示例:绘制无向完整图k4和k6。

解决方案:图1中显示了k4的无向完整图, 图2中显示了k6的无向完整图。

图Graph的类型

6.连接图和断开图:

连通图:如果存在从任何顶点u到v的路径(反之亦然), 则称为连通图。

断开连接的图:如果其两个顶点之间没有路径, 则该图称为断开连接。

示例:考虑图5所示的图形。确定图形是否为

(a)断开图

(b)连接图。

另外, 编写其连接的组件。

图Graph的类型

解:

(i)图中所示的图是一个断开的图, 其连接的组件是

{V1, V2, V3, V4}, {V5, V6, V7, V8}和{V9, V10}。

(ii)图中所示的图是一个断开图, 其连接的组件是

{V1, V2}, {V3, V4}, {V5, V6}, {V7, V8}, {V9, V10}和{V11, V12}。

图Graph的类型

(iii)图中所示的图是连通图。

图Graph的类型

7.连接的组件:如果图G的子图不包含在连接的G的更大子图中, 则该图的子图称为G的连接组件。通过列出其顶点来定义。

示例:考虑图5所示的图形。确定其连接的组件。

图Graph的类型

解决方案:该图的连接组件为{a, b, c}, {d, e, f}, {g, h, i}和{j}。

8.有向完成图:n个顶点上的有向完成图G =(V, E)是其中每个顶点通过箭头连接到其他每个顶点的图。用Kn表示。

示例:绘制有向完整图形K3和K5。

解决方案:将顶点数放置在适当的位置, 然后从每个顶点到每个其他顶点绘制一个箭头, 如图所示:

图Graph的类型
图Graph的类型

9.互补图:图G的补码定义为具有与图G中相同数量的顶点, 并且在且仅当在图中不相关的两个顶点连接的图。

示例:考虑图5所示的图形G。找到该图的补码。

图Graph的类型

解决方案:上图的补图如图:

图Graph的类型

10.标记图:如果图的G =(V, E)的边缘用某些名称或数据标记, 则称为标记图。因此, 我们可以将这些标签写在其边缘集中的有序对的位置。

示例:图中显示的图形被标记为图形。

G = {{a, b, c, d}, {e1, e2, e3, e4}}

图Graph的类型

11.加权图:如果图G的每个边都分配了正数w(称为边的权重e), 则图G =(V, E)称为加权图。

示例:图中所示的图是加权图。

图Graph的类型

赞(0)
未经允许不得转载:srcmini » 图Graph的类型

评论 抢沙发

评论前必须登录!