南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 18 图论基本概念

1 图论-基本概念

图论 - 基本概念 1

回顾 2 口内容1：布尔代数 口满足结合、分配、同一、交换、补律；有补分配格 口内容2：有限布尔代数表示定理 口任意布尔代数同构于其原子构成集合的幂集代数系统

 内容1：布尔代数  满足结合、分配、同一、交换、补律；有补分配格  内容2：有限布尔代数表示定理  任意布尔代数同构于其原子构成集合的幂集代数系统 2 回顾

本节提要 3 口内容1：图的定义 ▣内容2：图的应用 口内容3：图的表示 ▣内容4：图的同构

本节提要  内容1：图的定义  内容2：图的应用  内容3：图的表示  内容4：图的同构 3

图的定义Graph 常常省略，写作： 4 G=(V,E) 图G是一个三元组：G=(V,E, 口V是非空顶点集，E是边集，且V∩E=; 口p:E→P),且Ve∈E.1≤|go(e)≤2.p(e)称为边e的端点集. 口举例（数据中心、通信链接） 底特律 纽约 旧金山 丹佛 芝加哥 华盛顿 洛杉矶

图的定义 Graph  图G是一个三元组：G =(V, E, )  V是非空顶点集，E是边集，且V ⋂ E = ；  : E → (V), 且e E. 1|(e)|2. (e)称为边e 的端点集.  举例（数据中心、通信链接） 洛杉矶 旧金山 丹佛 芝加哥 华盛顿 纽约 底特律  常常省略，写作： 4 G = (V, E)

图的定义（续) 5 图G=(V,E,p)是简单图，如果 口每条边有2个端点，即：e∈E.lp(e)川=2，并且 口不同边有不同端点集，即：如果e1≠e2,则p(ei)≠p(e2) 口图G=(V,E,p)是伪图，如果 口存在一条只有1个端点的边，即：3eo∈E.lp(eo)川=1，或者 口有两条边具有相同的端点集，即：3e1≠e2p(e1)=p(c2)

图的定义（续）  图G = (V, E, )是简单图，如果  每条边有2个端点，即：e E. |(e)| = 2，并且  不同边有不同端点集，即：如果e1 e2 ，则(e1 )  (e2 )  图G = (V, E, )是伪图，如果  存在一条只有1个端点的边，即: e0E.|(e0 )| = 1，或者  有两条边具有相同的端点集，即: e1 e2 .(e1 )=(e2 ) 5

图的定义（续） 6 口伪图（包含环或者多重边)示例 底特律 纽约 旧金山 丹佛 芝加哥 华盛顿 洛杉矶

图的定义（续）  伪图（包含环或者多重边）示例 洛杉矶 旧金山 丹佛 芝加哥 华盛顿 纽约 底特律 6

图的定义（有向图） 7 口有向图G是一个三元组：G=(V,E,φ) 口V是非空顶点集，E是有向边（弧)集，且V∩E=中； 口p:E→V×V,若p(e)=(u,v),则u和v分别称为e的起点和终点. 举例（简单有向图） 底特律 纽约 旧金山丹佛 芝加哥 华盛顿 洛杉矶

图的定义（有向图）  有向图G是一个三元组：G= (V, E, )  V是非空顶点集，E是有向边（弧）集，且V⋂E=；  :E→VV,若(e)=(u, v), 则u和v分别称为e的起点和终点.  举例（简单有向图） 洛杉矶 旧金山 丹佛 芝加哥 华盛顿 纽约 底特律 7

图的术语 8 口无向图G=(V,E,p),φ(e)={u,} ▣u和v在G里邻接（相邻） ▣e关联（连接）顶点u和v 图G中顶点v的度，deg(v),dc() 口与该顶点关联的边数，环为顶点的度做出双倍贡献。 底特律 纽约 旧金山 丹佛 芝加哥 华盛顿 洛杉矶

 无向图G = (V, E, ), (e)={u, v}  u和v在G里邻接（相邻）  e关联（连接）顶点u和v  图G中顶点v的度, deg(v)， dG (v)  与该顶点关联的边数，环为顶点的度做出双倍贡献。 洛杉矶 旧金山 丹佛 芝加哥 华盛顿 纽约 底特律 8 图的术语

握手定理 9 ▣无向图G有m条边，n个顶点V1,Vn ∑dy,)=2m 1 ▣推论：无向图中奇数度顶点必是偶数个

 无向图G有m条边，n个顶点v1 , …vn .  推论：无向图中奇数度顶点必是偶数个。 d v m n i i ( ) 2 1  = = 9 握手定理

图的术语（续） 10 ▣有向图G=(V,E,p),p(e)=(u,v) 口u是e的起点，v是e的终点 口假设u≠V,u邻接到v,v从u邻接 口有向图中顶点的出度和入度 口dg+(v)=以v为始点的边的条数，degt(v) 口dg(v)=以v为终点的边的条数，deg(v) 口有向图中各顶点的出度之和等于入度之和。 Σveydeg((v)=∑vey deg()=El 口有向图的底图

 有向图G =(V, E, ), (e)=(u, v)  u是e的起点，v是e的终点  假设 uv，u邻接到v，v从u邻接  有向图中顶点的出度和入度  dG + (v) = 以v为始点的边的条数，deg+ (v)  dG - (v) = 以v为终点的边的条数，deg- (v)  有向图中各顶点的出度之和等于入度之和。 vVdeg+ (v) = vV deg- (v) =|E|  有向图的底图 10 图的术语（续）