内容提要 ● 图的定义 ·图模型 ·图的术语 ●几种特殊的图 ·二部图(偶图) ·图的运算 ·图结构上的经典问题
内容提要 图的定义 图模型 图的术语 几种特殊的图 二部图 (偶图) 图的运算 图结构上的经典问题
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) 社会网络 熟人关系图 合作图,好莱坞图 呼叫图 体育(循环赛的图模型)