基本概念 离散数学一图论初步 南京大学计算机科学与技术系
基本概念 离散数学─图论初步 南京大学计算机科学与技术系
急售扇 内容提要 ING 。图的定义 ·用图建模 ·图的表示 ·图的运算 ·图的同构 2
内容提要 图的定义 用图建模 图的表示 图的运算 图的同构 2
&感 Konigsberg七桥问题 ·问题的抽象： 。用顶点表示对象“地块” 。用边表示对象之间的关系“有桥相连
Königsberg七桥问题 问题的抽象： 用顶点表示对象-“地块” 用边表示对象之间的关系-“有桥相连” C D A B A C B D 3
雪扇 图的定义Graph p常常省略，写作： G=(V,E) o 图G是一个三元组：G=(V,E, 。V是非空顶点集，E是边集，且V∩E=: ●mE→r,且e∈E.1≤l(e)s2.o(e)称为边e的端点集 。举例（数据中心、通信链接) 底特律 纽约 旧金山 丹佛 芝加哥 华盛顿 洛杉矶
图的定义 Graph 图G是一个三元组：G =(V, E, ) V是非空顶点集，E是边集，且 V ⋂ E = ； : E (V), 且e E. 1|(e)|2. (e)称为边 e 的端点集. 举例（数据中心、通信链接） 洛杉矶 旧金山 丹佛 芝加哥 华盛顿 纽约 底特律 常常省略，写作： G = (V, E) 4
&食嘉 图的定义（续) ·图G=(V,E,p)是简单图，如果 。每条边有2个端点，即：e∈E.lp(e川=2，并且 。不同边有不同端点集，即：如果e1≠e2,则p(ei)≠p(e2) ·图G=(V,E,φ)是伪图，如果 。存在一条只有1个端点的边，即：3eo∈E.p(eo=1,或者 。有两条边具有相同的端点集，即：3e≠e2p(e)=p(e2)
图的定义（续） 图G = (V, E, )是简单图，如果 每条边有2个端点，即： e E. |(e)| = 2，并且 不同边有不同端点集，即：如果e1 e2 ，则(e1 ) (e2 ) 图G = (V, E, )是伪图，如果 存在一条只有1个端点的边，即: e0E.|(e0 )| = 1，或者 有两条边具有相同的端点集，即: e1 e2 .(e1 )=(e2 ) 5