北京大学：《离散数学》系列课程之一《集合论与图论》第14讲 图的基本概念

第14讲图的基本概念 秦1预备知识,无向图,有向图,相邻,关联 2度握手定理,度数列,可(简单)图化 3图同构 秦4.图族 《集合论与图论》第14讲

《集合论与图论》第14讲 1 第14讲 图的基本概念 1.预备知识,无向图,有向图,相邻,关联 2.度,握手定理,度数列,可(简单)图化 3.图同构 4.图族

图论参考书 w+ Graph Theory, R Diestel, Springer, 1997, 157.5/D566(有只读电子版) 现代图论(影印版,科学出版社 Springer, 2001,(0157.5/B638m/2001 离散数学及其应用, 机械工业出版社, 离散数学 Dade Mabe 及其旋用 2002.2004 adss APl 《集合论与图论》第14讲

《集合论与图论》第14讲 2 图论参考书 Graph Theory, R.Diestel,Springer,1997, (O157.5/D566) (有只读电子版) 现代图论(影印版),科学出版社-Springer, 2001, (O157.5/B638m/2001) 离散数学及其应用, 机械工业出版社, 2002, 2004

预备知 春有序积:AXB=( EAAyEB} 有序对:≠y,X 静无序积:AB={(Xy)X∈Ay∈B 无序对:(xy)=(yX) 多重集:{ a.a.a. bbc}=ab;c} 重复度:a的重复度为3,b的为2,c的为1 《集合论与图论》第14讲

《集合论与图论》第14讲 3 预备知识 有序积: A×B={ |x∈A∧y∈B} 有序对: ≠ 无序积: A&B={ (x,y) |x∈A∧y∈B} 无序对: (x,y)=(y,x) 多重集: {a,a,a,b,b,c}≠{a,b,c} 重复度: a的重复度为3, b的为2, c的为1

无向图( undirected graph) 无向图( graph:G=, (1)V≠,顶点结点 (vertex/noe 2)多重集EcV&V,边(eoge/link) W F G= Va, b, c, d e E={(aa),(a,b)、ab,b,c),(c,d),(b,d)} e c 《集合论与图论》第14讲

《集合论与图论》第14讲 4 无向图(undirected graph) 无向图(graph): G=, (1) V≠∅, 顶点,结点(vertex / node) (2) 多重集E⊆V&V, 边(edge / link) 例: G=,V={a,b,c,d,e}, E={(a,a),(a,b),(a,b),(b,c),(c,d),(b,d)}. a b c d e u v (u,v)

有向图( directed graph) 有向图( digraph):D=, (1)V≠,顶点结点 (vertex/noe 2)多重集EcXV,边eoge/ink/arc) +s D= V=a, b, c d, e), E=( , ab>,,,,c,d>(b0) 山起点)终点 e c 《集合论与图论》第14讲

《集合论与图论》第14讲 5 有向图(directed graph) 有向图(digraph): D=, (1) V≠∅, 顶点,结点(vertex / node) (2) 多重集E⊆V×V, 边(edge / link / arc) 例: D=,V={a,b,c,d,e}, E={ , ,,,,,(d,b) }. a b c d e u(起点) v(终点)

n阶图,零图,平凡图,空图。 若G=,则VG)=V,E(G=E 静若D=以V,E>,则V(D)=V,E()=E 阶图( (order-n graph):(G)=n 有限图( inite graph): V(G)|<∞ 秦零图(u‖! graph):E=,N 鲁平凡图( trival graph):1阶零图,N 空图( empty graph):V=E=, 《集合论与图论》第14讲

《集合论与图论》第14讲 6 n阶图,零图,平凡图,空图 若G=, 则V(G)=V, E(G)=E 若D=, 则V(D)=V, E(D)=E n阶图(order-n graph): |V(G)|=n 有限图(finite graph): |V(G)|<∞ 零图(null graph): E=∅, Nn 平凡图(trival graph): 1阶零图, N1 空图(empty graph): V=E=∅, ∅

标定图,非标定图,基图 壽标定图( abeled graph):顶点或边带标记 非标定图 unlabeled graph:顶点或边不 带标记 基图(底图):有向图去掉边的方向后得到 的无向图 a d 《集合论与图论》第14讲

《集合论与图论》第14讲 7 标定图,非标定图,基图 标定图(labeled graph): 顶点或边带标记 非标定图(unlabeled graph): 顶点或边不 带标记 基图(底图): 有向图去掉边的方向后得到 的无向图 a b c d

相邻( (adjacent),关联( incident) 相邻(邻接)( adjacent:点与点,边与边 豢邻接到,邻接于:u邻接到ν,V邻接于u以 关联( (incident):点与边· 关联次数: 秦环(0p):只与一个顶点关联的边 孤立点( solated vertex):· 平行边( parallel edge) 《集合论与图论》第14讲

《集合论与图论》第14讲 8 相邻(adjacent),关联(incident) 相邻(邻接)(adjacent): 点与点,边与边 邻接到,邻接于: u邻接到v, v邻接于u 关联(incident):点与边 关联次数: 环(loop):只与一个顶点关联的边 孤立点(isolated vertex): 平行边(parallel edge): ? 1 1 +1 -1 2 u v

邻域( neighborhood 邻域:N()={uueV(G)(u,)∈E(G)Auzy 闭( closed)邻域:N(v)=N(y{vy 关联集:I()={ee与v关联} 后继:ID()= uuEVDE(D)Au=1 前驱:D()={ uUEV(D)uv>∈E(D)八u 邻域:Ne()=ID)() 闭邻域:ND(v)=ND(v){v 《集合论与图论》第14讲

《集合论与图论》第14讲 9 邻域(neighborhood) 邻域: NG(v)={u|u∈V(G)∧(u,v)∈E(G)∧u≠v} 闭(closed)邻域: 关联集: IG(v) = { e | e与v关联 } 后继:ΓD+(v)={u|u∈V(D)∧∈E(D)∧u≠v} 前驱:ΓD-(v)={u|u∈V(D)∧∈E(D)∧u≠v} 邻域: NG(v)=ΓD+(v)∪ΓD-(v) 闭邻域: N (v) N (v) {v} G = G ∪ N (v) N (v) {v} D = D ∪

顶点的度数( legree/valence) 度d):与v关联的边的次数之和 出度d+(0):与v关联的出边的次数之和 鲁入度d(0):与v关联的入边的次数之和 度dD)=db)+d() (d,d) 《集合论与图论》第14讲

《集合论与图论》第14讲 10 顶点的度数(degree/valence) 度dG(v): 与v关联的边的次数之和 出度dD+(v): 与v关联的出边的次数之和 入度dD-(v): 与v关联的入边的次数之和 度dD(v) = dD+(v) + dD-(v) 0 3 3 4 0,0 1,2 (d+,d-) 2,1 2,2