离散数学第七章图

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

1、第七章图在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。图论起源于18世纪，它是研究由线连成的点集的理论。一个图中的结点表示对象，两点之间的连线表示两对象之间具有某种特定关系(先后关系、胜负关系、传递关系和连接关系等)。事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽

2、象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。7.1　图的基本概念7.1.1图的定义7.1.1.1无向图定义7.1.1　设A，B是任意集合。集合{(a,b)

3、aA且bB}称为A和B的无序积，记为A＆B。　　在无序积中，两个元素间的顺序是无关紧要的，即(a,b)＝(b,a)。定义7.1.2　无向图G是一个二元组，记作G＝，其中V是一个非空有限集合，其元素称为结点(顶点)。E是一个V＆V的多重子集，其元素称为边(无向边)。　　我们可用平面上的点来表示顶点，两点间的连线表示边，从而将任一个无向图用图形表示出来。［例7.1.1］　无向图G＝

4、，E>，其中V={a，b，c，d，e，f}，E={(a,b)，(a,c)，(a,d)，(b,b)，(b,c)，(b,c)，(b,d)，(c,d)}。7.1.1.2有向图定义7.1.3　有向图G是一个二元组，记作G＝，其中V是一个非空有限集合，其元素称为顶点，E是一个VV的多重子集，其元素称为有向边或弧，简称为边。9注：1)在有向图G＝中，若e=〈u，v〉，则称u和v为e的起点和终点；2)自回路既可看成是有向边又可看成是无向边；3)去掉有向图中边的方向得到的图称为该有向图的基图。［例7.1.2］　有向图G＝，其中V={a，b，c}，E={，<

5、a,a>，，，，}。7.1.1.3相关概念在无向图或有向图中，1）有限图与无限图；2）n阶图；

6、V

7、=n;3)零图E=Φ；4）平凡图（

8、V

9、=n，E=Φ）；5)对于无向图，若边e=(u,v)，则称u和v是边e的端点，称边e关联于u和v，若u=v，则称此为环，边与顶点的关联次数是0，1，2；至少有一条边相连的两个顶点相邻；至少一个公共顶点的两条边相邻6)对于有向图，若边e=，则称u和v是边e的端点，称u是边e的始点，v是边e的终点，称u邻接到v。7)关联于同一个顶点的边称为环（自回路）；若关联于同一对顶点的边多于一条时，称这些边为平行边，平行

10、边的条数称为边的重数；8)不与任何顶点邻接的顶点称为孤立点；含有平行边的图称为多重图，不含有平行边，也不含环的图称为简单图；7.1.2顶点的度数，握手定理定义7.1.4　(1)在无向图G=〈V，E〉中，v∈V。与v关联的边数称为v的度数，记为deg(v)；(2)在有向图G=〈V，E〉中，v∈V。以v为始点的边数称为v的出度，记为deg＋(v)；以v为终点的边数称为v的入度，记为deg－(v)；称deg(v)=deg＋(v)+deg－(v)称为v的度(数)。［例7.1.3］　9求例7.1.1中无向图每个顶点的度数；求例7.1.3中有向图每个顶点的出度、入度和度。注：若结点有自回路，则结点的度

11、数因此而增加2；若有向图的结点v有自回路，则它的出度和入度分别因此而增加1。孤立结点的度数为0。定理7.1.1(Euler握手定理)在图G=中,deg(v)=2

12、E

13、。推论7.1.1　任何图中度数为奇数的结点为偶数个。定理7.1.2　在有向图G=中有deg＋(v)=deg－(v)=

14、E

15、。度序列，出度序列，入度序列：定理7.1.3：度序列可图化的充要条件是度序列之和是偶数。［例7.1.4］（1）3，2，3，35，2，3，1，4，7可图化吗？（2）一知一个图有10条边，4个3度顶点，其余顶点的度数均小于等于2，问该图至少有几个顶点？7.1.3子图定义7.1.5　设图G=<

16、V，E>和G´=，（1）若V´Ｖ，Ｅ´Ｅ，则称Ｇ´是Ｇ的子图，记为G´G；（2）若G´G且V´Ｖ或Ｅ´Ｅ，则称Ｇ´是Ｇ的真子图，记为G´G；（3）若G´G且V´=V，则称Ｇ´是Ｇ的生成子图；（4）V´V，V´，以V´为顶点集，以所有端点均在V´中的G的边为边集的图称为由V´诱导出的Ｇ的子图；（5）E´E，E´，以E´为边集，以E´中的边的端点点为顶点集的图称为由E´诱导出的Ｇ的子图；［例7.1.5］　求例7