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

基本概念 离散数学一图论初步 南京大学计算机科学与技术系

基本概念 离散数学─图论初步 南京大学计算机科学与技术系

内容提要 ● 图的定义 ·图模型 ·图的术语 ●几种特殊的图 ·二部图（偶图） ·图的运算 ·图结构上的经典问题

内容提要  图的定义  图模型  图的术语  几种特殊的图  二部图 （偶图）  图的运算  图结构上的经典问题

Konigsberg七桥问题 ·问题的抽象： 。用顶点表示对象“地块” ·用边表示对象之间的关系“有桥相连

Königsberg七桥问题  问题的抽象：  用顶点表示对象-“地块”  用边表示对象之间的关系-“有桥相连” C D A B A C B D

图的定义 图G是一个三元组：G=(V,E,p) 。V是非空顶点集，E是边集，且V∩E=中； 。p:E→P(V),且e∈E.1≤lp(e)川s2.p(e)称为边e的端点集 ● 举例（数据中心、通信链接) 底特律 纽约 旧金山 丹佛 芝加哥 华盛顿 洛杉矶

图的定义  图G是一个三元组：G =(V, E, ϕ)  V是非空顶点集，E是边集，且V⋂E=φ；  ϕ: E  Ρ(V), 且∀e∈ E. 1≤|ϕ(e)|≤2. ϕ(e)称为边e的端点集.  举例（数据中心、通信链接） 洛杉矶 旧金山 丹佛 芝加哥 华盛顿 纽约 底特律

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

图的定义（续）  图G = (V, E, ϕ)是简单图，如果  每条边有2个端点，即： ∀e∈ E. |ϕ(e)| = 2，并且  不同边有不同端点集，即：如果e1≠ e2 ，则ϕ(e1) ≠ ϕ(e2)  图G = (V, E, ϕ)是伪图，如果  存在一条只有1个端点的边，即: ∃e0∈E.|ϕ(e0)| = 1，或者  有两条边具有相同的端点集，即:∃ e1≠ e2.ϕ(e1)=ϕ(e2)

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

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

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

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

图模型 ·交通网络 。航空、公路、铁路 ·信息网络 。万维网图(Web Graph) 。引用图(Citation Graph) ·社会网络 。熟人关系图 ·合作图，好莱坞图 。呼叫图 ·体育（循环赛的图模型)

图模型  交通网络  航空、公路、铁路  信息网络  万维网图（Web Graph）  引用图（Citation Graph）  社会网络  熟人关系图  合作图，好莱坞图  呼叫图  体育（循环赛的图模型）

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

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

握手定理 ●无向图G有m条边，n个顶点y,ym ∑dy,)=2m i=1 ·推论：无向图中奇数度顶点必是偶数个

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