资源描述：
《苏XI友无密码课件第7章图的基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四部分图论图论是研究由线连接的点集的理论,它起源于18世纪.1736年欧拉(Euler)研究了著名的哥尼斯堡七桥问题.由此开创了一个新的数学分支—图论.在19世纪和20世纪的前半期,图论主要研究一些游戏问题,诸如迷宫问题、博弈问题和棋盘上马的行走路线问题等.1847年,基尔霍夫(Kirchhoff)应用图论的方法来分析电网络,奠定了现代网络理论的基础.1936年,哥尼格发表了第一本图论专著,从此,图论成为一门独立的学科.北京林业大学信息学院苏喜友1第四部分图论图论的应用范围很广,它不但能应用于自然科学,也能应用于社会科学.例如,它可应用于电信网络、
2、电力网络、运输能力、开关理论、编码理论、控制论、反馈理论、随机过程、可靠性理论、化学化合物的辨认、计算机的程序设计、故障诊断、人工智能、印刷电路板设计、图案识别、地图着色、情报检索,还可应用于语言学、社会结构、经济学、运筹学、兵站学、遗传学等方面.北京林业大学信息学院苏喜友2Chap.7图的基本概念§1无向图和有向图§2通路、回路、图的连通性§3图的矩阵表示北京林业大学信息学院苏喜友3§1无向图和有向图一、图的定义Def.1设A是一个非空集合,x,y∈A,称{x,y}为A上的无序偶(对),记作(x,y).如,(a,c),(c,a),(a,b),(a,
3、a)都是集合{a,b,c}上的无序偶,且(a,c)=(c,a).Def.2无向图G(Graph)是一有序对‹V,E›,即G=‹V,E›,其中V是非空集合,E是V上的无序对的多重集合,分别称V和E是无向图G的顶点集和边集.V中元素称为顶点或结点,E中元素称为无向边或简称为边.北京林业大学信息学院苏喜友4§1无向图和有向图Def.3有向图D是一有序对‹V,E›,即D=‹V,E›,其中V是非空集合,E是V上的有序对的多重集合,分别称V和E是有向图D的顶点集和边集.V中元素称为顶点或结点,E中元素称为有向边或简称为边(或弧).一般情况下,图均以图形形式表示.
4、如,北京林业大学信息学院苏喜友5§1无向图和有向图术语与说明：(1)当不需要区分无向图和有向图时,我们统称为图,用G表示.G既可表示无向图,也可表示有向图,但D只能表示有向图.(2)V(G),E(G)分别表示图G的顶点集和边集.V(G)和E(G)都是有限集的图,称为有限图,否则称为无限图.本课程只讨论有限图.(3)一个有n个顶点和m条边的图称为(n,m)图或n阶图.(4)若E(G)=φ,称G为零图.只有一个顶点的图称为平凡图.北京林业大学信息学院苏喜友6§1无向图和有向图(5)设ek=(vi,vj)(或ek=‹vi,vj›),则称vi和vj是邻接的(
5、或相邻的),vi和vj是边ek的端点,ek与vi(或vj)彼此相关联.若vi=vj,则称ek与vi(或vj)的关联次数为2,若vi≠vj,则称ek与vi(或vj)的关联次数为1,若ek与vi不关联,则称ek与vi的关联次数为0.关联同一顶点的两条边称为相邻的.无边关联的顶点称为孤立点.对于有向边ek=‹vi,vj›,称vi是ek始点,vj是ek的终点,ek关联于vi,ek关联到vj,vi邻接到vj,vj邻接于vi.北京林业大学信息学院苏喜友7§1无向图和有向图(6)如果一条边的两个端点重合,则称这条边为自回路或自环(环).关联于同一对顶点的边若多于一
6、条(对于有向图,边的方向相同),则称这些边为平行边.平行边的条数称为重数.(7)含有平行边的图称为多重图.不含平行边的图,即非多重图称为线图.不含平行边和环的图,即无环的线图称为简单图.北京林业大学信息学院苏喜友8§1无向图和有向图二、顶点的度数Def.4(1)设G=‹V,E›是无向图,v∈V,v作为边的端点的次数称为v的度数,简称为度,记作d(v).(2)设D=‹V,E›是有向图,v∈V,v作为边的始点的次数称为v的出度,记作d+(v),v作为边的终点的次数称为v的入度,记作d-(v);v的出度和入度之和称为v的度数,记作d(v),即d(v)=d+
7、(v)+d-(v).(3)度数为1的顶点称为悬挂点,悬挂点所关联的边称为悬挂边.北京林业大学信息学院苏喜友9§1无向图和有向图称(G)=max{d(v)
8、v∈V)},(G)=min{d(v)
9、v∈V}分别为图G的最大度数和最小度数.称+(D)=max{d+(v)
10、v∈V)}为有向图D的最大出度;+(D)=min{d+(v)
11、v∈V)}为有向图D的最小出度;-(D)=max{d-(v)
12、v∈V)}为有向图D的最大入度;-(D)=min{d-(v)
13、v∈V)}为有向图D的最小入度.北京林业大学信息学院苏喜友10§1无向图和有向图Th.1(握手
14、定理)设G=‹V,E›是具有顶点集V={v1,v2,…,vn}的(n,m)图,则证.图中任何一条边均有两个端
