发布时间 : 星期一 文章基于图论的物流配送中心车辆调度系统设计与实现更新完毕开始阅读57171e1afad6195f312ba6ed
第二章 图的相关知识
第二章 图的相关知识
2.1图的定义及性质
定义1： 一个图G定义为一个有序对(V,E)。其中
(1)V 是一个非空集合，称为顶点集，其元素称为顶点或点；
(2) E是由V中的点组成的无序点对构成的集合，称为边集，其元素称为边， 且同一点对在E中可出现多次。
定义2： 一个图是一个三元组[V(G),E(G),f(g)]，其中V(G)是一个非空的结点集合，E(G)是边集合，f(g)是从边集合E到结点集合上的函数。
一个图可以用一个图形表示。若把图中的边e看作总是与两个结点关联，那么一个图亦可简记为G=(V,E),其中V是非空结点集，E是连接结点的边集。在一个图中，若两个结点由一条有向边或一条无向边关联，则这两个结点称为是邻接点。类似于邻接点的概念，关于同一结点的两条边称为邻接边。
定义3： 在图中G?(V,E)中，与结点v(v?V)关联的边数，称作该结点的度数，记作deg(v)。
由此我们知道，结点度数的总和等于边数的两倍。一个图由一个图形表示，由于图形的结点位置和连线长度都可以任意选择，故一个图的图形表示并不是唯一的。
定义4：在有向图中，射入一个结点的边数称为结点的入度，由一个结点射出的边数称为该结点的出度。结点的入度与出度之和就是该结点的度数。
由此我们知道，在任何有向图中，所有结点的入度之和等于所有结点的出度之和。因为每一条有向边必对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关联一条有向边。
定义5：含有平行边的任何一个图称为多重图G?(V,E)。不含平行边和环的图称为简单图。
定义6：简单图G?(V,E)中，若每一对结点间都有边相连，则称该图为完
- 8 -
第二章 图的相关知识
全图。有n个结点的无向完全图记做Kn。
2.2图的基本性质
图论是研究二元关系的一门学问,是计算机科学的理论基础,顶点和边是图的两个基本要素,一定的量反映一定质,顶点数和边数以及它们之间的数量关系在一定程度上决定了图的基本性质。
定理1 ：在任意一个图中，结点度数的总和等于边数的两倍,也即
?deg(v)?2E。
证明：因为每条边必关联两个结点，而一条边给予关联的每个结点的度数是1.因此在一个图中，结点度数的总和等于边数的2倍。
定理2：在任何图中，度数为奇数的结点必定是偶数个。
证明：设V1和V2分别是G中奇数度数和偶数度数的结点集，则由定理1，有： ?deg(v1)??deg(v2)??deg(v)?2E。
由于?deg(v2)是偶数之和，必为偶数；而2E是偶数，所以，?deg(v1)是偶数，即V1是偶数。
定理3：在任意有向图中，所有结点的入度之和等于所有结点的出度之和。 证明：因为每一条有向边必对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关联一条有向边，所以，有向图中各结点入度之和等于边数，各结点出度之和也等于边数，因此，任何有向图中，入度之和等于出度之和。
定理4 n个结点的无向完全图Kn的边数为n(n?1)/2。
证明：在Kn中，任意两点间都有边相连，n个结点中任意取两个点的组合
2数为：Cn?n(n?1)/2，故Kn的边数为E?n(n?1)/2。
如果在Kn中，对每条边任意确定一个方向，就该称该图为n个结点的有向完全图。显然，它的边数也是n(n?1)/2。给定任意一个含有结点的图，总可以把它补成一个具有同样结点的完全图，方法是把那些没有连上的边添加上去。
- 9 -
第二章 图的相关知识
2.3 着色问题
着色是指对二元图中的元素（顶点、边等）进行着色，即在满足一定的条件下，使得任意两个相邻的相同性质的元素的颜色不相同，并且使得所用颜色数最少（即在现实生活中所用资源最少）。
2.3.1 边着色
图G的k边着色，是k种色在E(G)上的一种匹配，即C是E(G)的一个k-划分。G的边色数是使G为k边可着色的最小的k，记为?'(G)。当?'(G)?k时，称G为k边色的。
2.3.2 顶点着色
一般而言，对图的顶点着色有如下定义：如果使用k种颜色把图G的每个顶点皆分配一种颜色，且使其邻顶点异色，则称此为对G的顶点正常k着色，图G的顶点的正常着色中所需要颜色数的最小值称为G的顶色数，简称色数,记之为
?(G)。色数为k的图称为k色图。
2.4算法复杂度的定义及其算法的效率度量
无论是求解一个图G的色数C(G)的算法，还是对一个给定的G进行正常k顶点着色算法、正常k边着色算法以及正常k全着色算法，都是NP完全问题。数较大时，用常规的方法很难得到图的正常k顶点着色、正常k边着色以及正常k全着色。于是，人们设想寻求更多简便的途径求得这些问题的算法。不管是从事数学研究的图论学者，还是从事电路与系统等工程技术方面研究的图论学者，或是其他领域内的科学家，对图的着色问题都表示了极大的兴趣与关注。
算法的复杂度是指执行算法所需的时间和空间的量。关于算法的复杂度主要有如下定义：
定义1：令f和g为从整数集合或实数集合到实数集合的函数，如果存在常数c和k，使得只要x>k，就有|f(x)|?c|g(x)|，则称f(x)是f(x)=O(bn),b?1，记作 f(x)=O(g(x))。
定理1：令f(x)=anxn?an?1xn?1?...a1x?a0，其中， a0，a1，......an-1，an 为
- 10 -
第二章 图的相关知识
实数,则f(x)=O(xn).
定理2：设f1(x)?O(g1(x)),f2(x)?O(g2(x)) ,则
f1(x)?f2(x)?O(max(g1(x)g2(x))).
定理3：设f1(x)?O(g1(x))，f2(x)?O(g2(x)),则
f1(x)f2(x)?O(g1(x)g2(x))
大O符号常用于估计一个特定的计算机过程或算法解题的操作步骤.做这些估计时常用的函数包括:1,logn,n,nlogn,n2,n!。
算法的效率度量有两种方式，一种是计算机按照算法解题所花费的时间，称为时间复杂性；另一种是计算机实现这一算法需要多大的内存，称为空间复杂性，空间复杂性与实现算法时使用的特定数据结构相关，故通常选择时间复杂性度量算法效率。
按匈牙利权威数学家Edmonds的定义，当一个判定问题D给定之后，若存在一个多项式P(t)，使得对于D的任何输入长为n的实例，可以在O(P(n))的时间内对这个实例给出答案，则称这种解答算法时间复杂度是合理的，称这 种算法为好算法或有效算法；否则（例如时间为O(kn),k?1）称相应的算法的时间复杂度式不可容忍的，称这种算法为无效算法或坏算法。
2.5本章小结
本部分主要介绍了该课题所用到的图论的基础知识，包括图的定义、图的性质、算法的复杂度的定义等，为解决停车场的停车位分配问题做好了铺垫。
- 11 -