******图论*图论部分第5章图的基本概念第6章特殊的图第7章树*第5章图的基本概念5.1无向图及有向图5.2通路,回路和图的连通性5.3图的矩阵表示5.4最短路径,关键路径和着色*5.1无向图及有向图无向图与有向图顶点的度数握手定理简单图完全图子图补图*无向图多重集:元素可以重复出现的集合无序积:A?B={(x,y)|x?A?y?B}定义无向图G=V,E,其中(1)顶点集V是非空有穷集合,其元素称为顶点(或简称顶)(2)边集E为V?V的多重子集，其元素称为无向边，简称边.例如右图G=V,E中，V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}*有向图定义有向图D=V,E,其中(1)顶点集V是非空有穷集合,其元素称为顶点(2)边集E为V?V的多重子集，其元素称为有向边，简称边.当用无向边代替D中有向边所得的图称为D的基图:如右图D=V,E中，V={a,b,c,d}E={a,a,a,b,a,b,a,d,c,b,d,c,c,d}图的数学定义与图形表示,在同构意义下一一对应*常用术语一般以G表示无向图、D表示有向图,也常用G泛指无向图和有向图.以V(G),E(G),V(D),E(D)明确G或D的顶点集,边集.n阶图:n个顶点的图零图:E=?（没有边的图）平凡图:1阶零图（只有一个顶点而无边的图）空图:V=?*顶点和边的关联与相邻定义若e=(u,v)为无向图G=V,E的一条边,称顶u,v为e的端点，e与u(v)关联.当u?v,则称e与u(v)的关联次数为1;若e仅关联顶u,称作环,此时e与u的关联次数为2;当w非e端点,则e与w的关联次数为0.无边关联的顶称为孤立点.定义有无向图G=V,E,u,v?V,e,e??E,若(u,v)?E,则称顶u,v相邻;若边e、e?至少有一公共端点,则称e,e?相邻.对有向图，类似定义：若e=?u,v?是有向图的一条边,称u是e的始点,v是e的终点,u邻接到v,v邻接于u.*顶点的度数(无向图)设G=V,E为无向图,v?V v的度(数)d(v):v作为G中边的端点次数之和悬(挂)顶点:度数为1的顶点悬(挂)边:与悬挂顶点关联的边G的最大度?(G)=max{d(v)|v?V}G的最小度?(G)=min{d(v)|v?V}例如右图，d(v5)=3,d(v2)=4,d(v1)=4,?(G)=4,?(G)=1,v4是悬挂顶点,e7是悬挂边,e1是环*顶点的度数(有向图)设D=V,E为有向图,v?V,v的出度d+(v):v作为边的始点次数之和v的入度d?(v):v作为边的终点次数之和v的度数(度)d(v):v作为边的端点次数之和即d(v)=d+(v)+d-(v)D的最大出度?+(D)=max{d+(v)|v?V}最小出度?+(D)=min{d+(v)|v?V}最大入度??(D)=max{d?(v)|v?V}最小入度??(D)=min{d?(v)|v?V}最大度?(D)=max{d(v)|v?V}最小度?(D)=min{d(v)|v?V}*例例有向图D如右： d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,?+(D)=4,?+(D)=0, ??(D)=3,??(D)=1,?(D)=5,?(D)=3.*图论基本定理——握手定理定理无向图或有向图中，所有顶点度数总和为边数的2倍；对于有向图，所有顶点入度之和等于出度之和恰等于边数.证：G的每条边（包括环）均有两端点，因此在计算各顶点度数之和时，每边均提供2度，m条边共提供2m度；有向图的每条边提供1入度和1出度,故所有顶点入度之和等于出度之和等于边数.推论