基本概念 离散数学一图论初步 南京大学计算机科学与技术系
基本概念 离散数学─图论初步 南京大学计算机科学与技术系
内容提要 ● 图的定义 ·图模型 ·图的术语 ●几种特殊的图 ·二部图（偶图） ·图的运算 ·图结构上的经典问题
内容提要 图的定义 图模型 图的术语 几种特殊的图 二部图 （偶图） 图的运算 图结构上的经典问题
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=φ； ϕ:EV×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 ∑ = =