南邮离散数学第7章图论

《南邮离散数学第7章图论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图论图论中有许多现代应用的古老题目。瑞士数学家欧拉在18世纪引进了图论的基本思想。利用图解决了哥尼斯堡七桥问题。图可以用来解决许多领域的问题。例如：用图来确定能否在平面电路板上实现电路。用图来区分分子式相同但结构不同的两种化学物。用边上带权值的图来解决诸如寻找交通网络里两个城市间最短通路的问题。用图来安排考试等等。随着科技的发展，图论在解决运筹学、网络理论、信息论、控制论、博弈论等问题时，发挥了巨大的作用。第七章　图论图的基本概念路与回路图的矩阵表示欧拉图与哈密尔顿图1、图的定义及表示图由结点和连接两个结点之间的连线组成。

2、连线的长度和结点的位置是无关紧要的。几乎每一门可以想象的学科里都有问题可以用图模型来解决。例如：可以用图来表示生态环境里不同物种的竞争；可以用图来表示在组织里谁影响谁，以及用图来表示比赛结果；旅行商问题；地球着色问题等。一个简单的例子：大城市之间的高速公路系统建模：可以把各个城市看成结点，城市之间存在高速公路，则认为这两个城市之间有连线，这样可以构成一个简单的图7-1图的基本概念2、图的表示法三元组表示G=：V(G)-非空的结点集合；E(G)-边集合；φG-边集合E到结点无序偶（有序偶）集合上的函数。

3、7-1图的基本概念图可简记为G=V(G)={a,b,c,d}E(G)={e1,e2,e3,e4,e5,e6}φG(e1)=(a,b),φG(e2)=(a,c),φG(e3)=(b,d),φG(e4)=(b,c),φG(e5)=(d,c),φG(e6)=(a,d).左右为同一图形3、图的一些基本概念（1）无向边：与结点无序偶关联的边，用(a,b)表示有向边：与结点有序偶关联的边，用表示；表明是从a到b的有向边孤立结点：无邻接点的结点7-1图的基本概念无向边：(a,b),(b,c),(b,d),(c,d),(i,

4、l),(k,l)有向边：,,,,,（2）无向图：图中每一边都为无向边有向图：图中每一边都为有向边混合图：图中既有有向边，也有无向边平凡图：仅由一个孤立结点构成的图7-1图的基本概念（3）邻接点：由一条有向边或一条无向边相关联的两结点邻接边：关联于同一结点的两条边平行边：连接于同一对结点的多条边自回路（环）：关联于同一结点的一条边（既可看作是有向边，也可作无向边）7-1图的基本概念（4）结点的度数图G=

5、为2。7-1图的基本概念deg(a)=2deg(b)=3deg(c)=2deg(d)=2deg(e)=5（4）结点的度数在有向图中，定义入度、出度的概念入度：射入一个结点的边的条数，记为deg-(v)；出度：由一个结点射出的边的条数，记为deg+(v)；入度与出度之和为该结点的度数：deg(v)=deg+(v)+deg-(v)7-1图的基本概念deg+(e)=2,deg-(e)=1,deg(e)=3deg+(f)=1,deg-(f)=2,deg(f)=3deg+(g)=deg-(g)=1,deg(g)=2deg+(h)=deg

6、-(h)=1,deg(h)=2（4）结点的度数最大度：最小度：7-1图的基本概念Δ(G)=5δ(G)=27-1图的基本概念定理:结点度数总和等于边数的两倍，即:证明：每条边关联两个结点一条边给相关的每个结点的度数为1因此，在图中，结点度数总和等于边数的两倍。7-1图的基本概念定理:度数为奇数的结点必定是偶数个证明：设V1、V2分别为G中奇数度数点集和偶数度数点集，则：7-1图的基本概念定理：有向图中所有结点的入度之和等于所有结点的出度之和证明：一条边对应一个入度和一个出度一个结点若具有一个出度或入度，则必关联边所以入度之和等于边

7、数，出度之和也等于边数（5）多重图：含有平行边的图简单图：不含有平行边和环的图完全图：每一对结点之间都有边关联的简单图有向完全图：完全图中每条边任意确定一个方向所得的图7-1图的基本概念定理：n个结点的无向（有向）完全图Kn的边数为n(n-1)/2证明：在完全图中，每个结点的度数应为n－1，则n个结点的度数之和为n(n-1)，因此

8、E

9、＝n(n-1)/2（6）子图：7-1图的基本概念生成子图：包含G中所有结点的子图（7）补图：G’是G的子图，若G’’=，使得E’’＝E-E’，且V’’中仅包含E’’的边所关联的结

10、点（V’’中无孤立结点），则称G’’是G’相对于G的补图7-1图的基本概念图(c)是图(b)相对于图(a)的补图问：若G’’是G’相对于G的补图，是否一定有G’是G’’相对于G的补图？即G’’和G’互为补图？不是，补图中不包含孤立结点(c)(b)(a)（7）补图