第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=(<xy> EAAyEB} 有序对:<X,y>≠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,y> |x∈A∧y∈B} 有序对: <x,y>≠<y,x> 无序积: 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=<V,E>, (1)V≠,顶点结点 (vertex/noe 2)多重集EcV&V,边(eoge/link) W F G=<V,E> 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=<V,E>, (1) V≠∅, 顶点,结点(vertex / node) (2) 多重集E⊆V&V, 边(edge / link) 例: G=<V,E>,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=<V,E>, (1)V≠,顶点结点 (vertex/noe 2)多重集EcXV,边eoge/ink/arc) +s D=<V, E> V=a, b, c d, e), E=( <a, a>, ab>,<ab>,<b,a>,<b,c>,c,d>(b0) 山起点)终点 <UY> e c 《集合论与图论》第14讲
《集合论与图论》第14讲 5 有向图(directed graph) 有向图(digraph): D=<V,E>, (1) V≠∅, 顶点,结点(vertex / node) (2) 多重集E⊆V×V, 边(edge / link / arc) 例: D=<V,E>,V={a,b,c,d,e}, E={ <a,a>, <a,b>,<a,b>,<b,a>,<b,c>,<c,d>,(d,b) }. a b c d e u(起点) v(终点) <u,v>