离散数学图论部分市公开课一等奖省赛课获奖课件.pptx

第四部分图论;图论问题起源;陆地

岛屿岛屿

陆地;当初人们热衷于这么游戏：构想从任一个地方出发经过每座桥一次且仅一次后回到原地,这是否可能?但屡次实践都发觉不行。

1727年欧拉朋友向欧拉提出了这个问题是否有解？

1736年欧拉用图论方法处理了这个问题,写了第一篇图论论文,成为图论创始人。

以后称此问题为哥尼斯堡七桥问题。

;但在此之后100年间，没有大进展。

直到Kirchhoff(克希霍夫)用树理论处理了电网络问题。这些结果引发了人们重视,图论研究进入了一个发展时期。

直到1920年,科尼格(Konig)撰写了许多图论方面论文。在1936年科尼格(Konig)发表了第一本图论书籍《有限图与无限图理论》,总结了200年来图论研究主要结果。

今后50年,图论经历了一场爆炸性发展,成为数学科学中一门独立学科。

;几十年来图论在理论上和应用上都得到很大发展,尤其是在近30多年来因为计算机广泛应用而又得到飞跃发展。

在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少结果，对计算机学科中操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛应用。

这里主要讨论图基本概念和算法,为今后学习和研究打下基础。

;本章首先给出图、简单图、完全图、子图、路和图同构等概念，接着研究了连通图性质和规律，给出了邻接矩阵、可达性矩阵、连通矩阵和完全关联矩阵定义。最终介绍了欧拉图与哈密尔顿图。

;图定义;;;;图相关概念和要求;;;;含平行边图称为多重图；

既不含平行边也不含环图称为简单图。

本书主要讨论简单图相关结论。;设G=V,E为无向图，ek=vi,vj∈E,则称vi,vj为ek端点，ek与vi或ek与vj是彼此关联。

无边关联顶点称为孤立点。若一条边所关联两个顶点重合，则称此边为环。

vi≠vj，则称ek与vi或ek与vj关联次数为1，若vi=vj，则称ek与vi关联次数为2；若vi不是ek端点，则称ek与vi关联次数0。;设G=V,E为无向图，vi,vj∈V,ek,el∈E,

若存在一条边e以vi,vj端点，即e=(vi,vj)则称vi与vj是彼此相邻。简称相邻。

(2)若ek与el最少有一个公共端点，则称ek与el是彼此相邻。简称相邻。

设D=V,E为有向图,vi,vj∈V,ek,el∈E,若

ek=vi,vj,除称vi,vj是ek端点外，还称vi为ek

起点，vj为ek终点，并称vi邻接到vj,vj邻

接于vi。

;顶点度

设G=V,E为一无向图，vi∈V,称vi作为边端点次数之和为vi度数，简称为度，记作deg(vi)（或d(vi)）。

设D=V,E为一有向图，vj∈V,称vj作为边始点次数之和,为vj出度，记作d+(vj);称vj作为边终点次数之和,为vj入度，记作d-(vj);称d+(vj)+d-(vj)为vj度数，记作d(vj)。

称度数为1顶点为悬挂顶点,它所对应边为悬挂边。;例：在上图(1)中,d(v1)=4,d(v2)=4,

d(v5)=0,……,

在图(2)中,d+(v1)=2,d-(v1)=1,d(v1)=3

d+(v2)=1,d-(v2)=3,d(v2)=4,……;

在无向图G中,令

△(G)=max{d(v)|v∈V(G)};

?(G)=min{d(v)|v∈V(G)}

称△(G)和?(G)分别为G最大度和最小度。

在有向图D中,可类似定义△(D)、?(G)。另外,令

△+(G)=max{d+(v)|v∈V(D)}

?+(G)=min{d+(v)|v∈V(D)}

△-(G)=max{d-(v)|v∈V(D)}

?-(G)=min{d-(v)|v∈V(D)}

分别为D最大出度、最小出度、最大入度、最小入度。简记作△、?、△+、?+、△-、?-。;;握手定理

设G=V,E为无向图或有向图，

V={v1,v2,…,vn},|E|=m(m为边数)则;设G=?V,E?是有向图，v?V，射入(出)结点v边数称为结点v入(出)度。记为deg－(v)(deg＋(v))。显然，任何结点入度与出度和等于该结点度数，即deg(v)=deg－(v)+deg＋(v)。

定理：在有向图中，全部结点入度和等于全部结点出度和。