图的基本概念及其矩阵表示.ppt

《图的基本概念及其矩阵表示.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学大连理工大学软件学院陈志奎2/128第9章图的基本概念及其矩阵表示论3/128图论（GraphTheory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如下图所示，A、B、C，D表示陆地。4/128图论的起源哥尼斯堡七桥问题：17世纪的东普鲁士有一座哥尼斯堡（Konigsberg）

2、城，城中有一条普雷格尔（Pregel）河，全城共有七座桥将河中的岛及岛与河岸联结起来，如下图所示，a,b,c,d表示陆地。从四块陆地的任何一块出发，怎样通过且仅通过每座桥一次，最终回到出发地点？5/128图论的起源1736年瑞士大数学家列昂哈德•欧拉（LeonhardEuler）解决了这一问题，他用了科学研究中最一般的方法——抽象。用四个字母a,b,c,d表示四块陆地，并用7条线表示7座桥，从而将七桥问题抽象为图的问题，寻找经过图中每边一次且仅一次的回路，后来人们把有这样回路的图称为欧拉图。6/128图论的起源欧拉证明了这个问题没有解

3、，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论的创始人。欧拉被称为图论之父，1736年也被称为“图论元年”。图论部分共分为三章：图的基本概念及其矩阵表示，几种图的介绍，树。本章将首先讨论图论中的一些基本概念，继之阐述图的基本性质，而后介绍图的矩阵表示方法。7/128主要内容图的基本概念子图和图的运算路径、回路、连通性图的矩阵表示欧拉图哈密尔顿图二部图、平面图网络树基础知识特殊图8/1289.1图的基本概念图是由一些顶点和连接这些顶点的一些边所组成的离散结构。根据连接顶点对的边的种类和数目

4、的不同，图有多种类型。几乎每一门可以想到的学科，都有用图模型来解决的问题。9/128图的种类(1)如果，则称为无向图。(2)如果，则称为有向图。无论是无向图还是有向图，都统称为图，其中V的元素称为图G的结点，E的元素称为图G的边，图G的结点数目称为图的阶。可以用几何图形表示上面定义的图。用小圆圈表示结点。在无向图中，若，就用连接结点v1和v2的无向线段表示边e。在有向图中，若，就用v1指向v2的有向线段表示边e。10/128图的基本概念定义：设无向图，，(1)如果，则称e与v1(或v2)互相关联。e连接v1和v2，v1和v2既是e的起

5、点，也是e的终点，也称v1和v2为点邻接。(2)如果两条不同的边e1和e2与同一个结点关联，则称e1和e2为边邻接。也就是说，共边的点称为点邻接；共点的边称为边邻接。11/128图的基本概念定义：设有向图。如果，则称e连接v1和v2，e与v1(或v2)互相关联，分别称v1和v2是e的起点和终点，也称v1和v2邻接。例：无向图e1连接v1和v2，v1和v2邻接，e1和e2邻接。12/128图的基本概念例：有向图v2和v1分别是e1的起点和终点，v2与v1邻接。13/128图的基本概念定义：设图,e1和e2是G的两条不同的边。(1)如果与

6、e1关联的两个结点相同，则称e1为自圈(或称环和回路)。(2)如果，则称e1与e2平行。(3)如果图G没有自圈，也没有平行边，则称G为简单图。(4)如果图G没有自回路，有平行边，则称G为多重边图。(5)如果图G既有自回路，又有平行边，则称G为伪图。14/128图的种类例：中国主要城市通讯图15/128图的种类类型边允许平行边允许自环简单图无向否否多重图无向是否伪图无向是是有向图有向否是有向多重图有向是是16/128度定义：。如果G是无向图，G中与v关联的边和与v关联的自回路的数目之和称为v的度(或次)，记为。如果G是有向图，G中以v为

7、起点的边的数目称为v的出度，记为；G中以v为终点的边的数目称为v的入度，记为；v的出度与入度之和称为v的度，记为。注意，在计算无向图中结点的度时，自回路要考虑两遍，因为自回路也是边。17/128度例：计算下图中各结点的度。18/128度定理：在无向图中，所有节点的度数之和等于边数的2倍。证：因为每条边给图G带来两度，设图G有m条边，所以图G共有2m度，等于图G的所有结点的度数之和。定理：在有向图中，所有顶点的度数之和等于边的2倍；所有顶点的入度之和等于所有节点的出度之和，都等于边数。度例：结点的度。19/12820/128结点定义：度

8、数为奇数的结点称为奇结点，度数为偶数的结点称为偶结点。定理：任何图都有偶数个奇结点。定义：度为0的结点称为孤立结点，度为1的结点称为端点。21/128一些特殊的简单图零图：结点都是孤立结点的图称为零图。平凡图：一阶零图称