|
本章简介 图(Graph)是一种复杂的非线性结构在人工智能工程数学物理化学生物和计算机科学等领域中图结构有着广泛的 应用 本章先介绍图的概念再介绍图的存储方法及有关图的算法 图的二元组定义 图G由两个集合V和E组成记为 G=(VE) 其中 V是顶点的有穷非空集合 E是V中顶点偶对(称为边)的有穷集 通常也将图G的顶点集和边集分别记为V(G)和E(G)E(G)可以是空集若E(G)为空则图G只有顶点而没有边 有向图和无向图 有向图 若图G中的每条边都是有方向的则称G为有向图(Digraph) ()有向边的表示 在有向图中一条有向边是由两个顶点组成的有序对有序对通常用尖括号表示有向边也称为弧(Arc)边的始点称为弧尾 (Tail)终点称为弧头(Head) 【例】表示一条有向边v i 是边的始点(起点)v j 是边的终点因此和是两条不 同的有向边 ()有向图的表示 【例】下面(a)图中G 是一个有向图图中边的方向是用从始点指向终点的箭头表示的该图的顶点集和边集分别为 V(G )={v v v } E(G )={} 无向图 若图G中的每条边都是没有方向的则称G为无向图(Undigraph) ()无向边的表示 无向图中的边均是顶点的无序对无序对通常用圆括号表示 【例】无序对(v i v j )和(v j v i )表示同一条边 ()无向图的表示 【例】下面(b)图中的G 和(c)图中的G 均是无向图它们的顶点集和边集分别为 V(G )={v v v v } E(G )={(v l v )(v v )(v v )(v v )(v v )(v v )} V(G )={v v v v v v v } E(G )={(v v )(v l v )(v v )(v v )(v v )(v v )} 注意 在以下讨论中不考虑顶点到其自身的边即若(v v )或是E(G)中的一条边则要求v ≠v 此外不允 许一条边在图中重复出现即只讨论简单的图 图G的顶点数n和边数e的关系 ()若G是无向图则≤e≤n(n)/ 恰有n(n)/条边的无向图称无向完全图(Undireeted Complete Graph) ()若G是有向图则≤e≤n(n) 恰有n(n)条边的有向图称为有向完全图(Directed Complete Graph) 注意 完全图具有最多的边数任意一对顶点间均有边相连 【例】上面(b)图的G 就是具有个顶点的无向完全图 |
