第9章图

9.2图的基本概念

--定义9.2.1 无序积的定义：如果A和B是任意的集合，那么称集合A&B={(a,b)}a∈A，b∈B} 叫做A和B的无序积，里面的元素 (a,b) 就是无序对。

与序偶不同，无序对没有顺序，也就是说(a,b)=(b,a)。之所以引入这个概念，是为了引出后面更好定义无向图，下面引出图的定义：

--定义9.2.2 图的定义：一个图是一个序偶<V,E>,记为G=<V,E>。

对序偶中元素的理解：首先V就是一个图中点的集合，元素Vi称为结点，也叫做点；而E就是边的集合。其次是结点对也有可能是有序的或者无序的，如果结点是有序的，假如v、u两个结点间有从v指向u的边，即结点间有序，那么边就称为有向边，则结点记为e=<v,u>,此时称u是始点，v是终点。如果无序，则点记为e=(u,v),边称为无向边。

有了关于图的一些基本概念，下面就有图的三种表示方法：

1.集合表示：即G=<V,E>

2.图形表示：如下图 3.邻接矩阵的表示方法：

--定义9.2.3 设图G=<V,E>,其中V={v1,v2,v3,v4...},假设结点已经有了从v1到vn的次序，则n阶方阵AG=(aij)n * n 称为G的邻接矩阵。其中aij=1，(v1,vj)∈E，否则aij=0