图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的类型】另外, 编写其连接的组件。
图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的类型

    推荐阅读