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