向边，称是4的始点，；是的终点；并称是巴，的直接前趋，，是：的直接后继。 如果：是无向边，则称，，是的两个端点。全部白有向边构成的图叫有向图；只由无 向边织成的图叫无向图：既有有向边又有无向边构成的图称为混合图。例如图1.4(a)是 有向图.()是无向图，()是混合图。在图G中，只与-一个结点相关联的边称为自环，在同 一对结点之间可以存在多条边，称之为重边。含有重边的图叫多重图。比如图1.4(a)(b) 中a1,e,分别是白环，a:a:和eer分别是重边， (a) (b) (c) 图1.4 定义1.1.2G一(V.E)的某结点v所关联的边数称为该结点的度，用d()表示。如 果v带有白环，则自环对d()的贡献为2。 例如图1.4(a)中，d()=5,d(2)=2,d(v3)=5,d(4)=4。(b)中，d(v)=5,d (2)=3,d(v)=5,d(v)=5。有向图中由于各边都是有向边，因此每个结点v还有其正 度(d()和负度(d(v)),d*(v)的值是以v为始点的边的数目，d(v)是以v为终点的 边的数目。显然有d·(v)十d()=d(u)。 定义1.1.3任意两结点间最多只有一条边，且不存在自环的无向图称为简单图。 以下所说的图在不加说明的情况下指的是无向图。 没有任何边的简单图叫空图，用N,表示：任何两结点间都有边的简单图称为完全 图，用K。表示。K.中每个结点的度都是n一1。 图(G具有以下基本性质。 性质【.1.1·设G-(V,E)有n个结点，m条边，则 >d()=2m。 -EV(G) 证明：血于每条边e=(u,)对结点和v度的贡献各为1，因此m条边对全部结点 度的总贡献就是2m。 性质1.1.2G中度为奇数的结点必为偶数个， 证明：G中任结点的度或为偶数或为奇数，设V,是度为偶的结点集，V。是度为奇 的结点集。于是有 d(e)÷≥d(o)=2m, 因此4®)为偶数.即V中含有阀数个结点. 性质1.1.3有向图G中正度之和等于负度之和。 这是因为每条边对结点的正、负度贡献各为1。 ·2