离散数学图论省公共课一等奖全国赛课获奖课件.pptx

第七章图论第七章图论图论图论7.1图基本概念（1）定义:一个图G是一个三元组<V(G),E(G),ΦG>,其中V(G)为顶点集合,E(G)是边集合，ΦG是从边集E到结点偶对集合上函数。讨论定义：(a)V(G)={V1，V2，…，Vn}为有限非空集合,Vi称为结点,简称V是点集。(b)E(G)={e1，…，em}为有限边集合,ei称为边，每个ei是连结V中某两个顶点,称E为边集。(c)可用e＝<vi,vj>或e＝(vi,vj)，来表示图边，这么可把图简化成：Ｇ＝<Ｖ，Ｅ>。（2）每一条边都是无向边图称无向图。每一条边都是有向边图称有向图。例：对有向图可表示为：Ｇ＝〈Ｖ，Ｅ〉，其中Ｖ＝｛a、b、c、d｝Ｅ＝｛<a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c>｝则：Ｇ＝〈Ｖ，Ｅ〉=〈｛a，b，c，d｝，｛<a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c>｝〉（3）在一个图中，若两个结点有一条有向边或者一条无向边关联,则这两个结点成为邻接点。孤立结点：在一个图中不与任何结点相邻接结点，称为孤立结点。以下列图中结点v5。（4）零图：仅由孤立结点组成图称为零图。（5）平凡图：仅由一个孤立结点组成图称为平凡图。邻接边：关联于同一结点两条边称为邻接边。（6）自回路（环）：关联于同一结点一条边称为自回路。以下列图，中（c，c）是环（7）度数：在图G=<V，E>中，与结点v（vV）关联边数，称为该结点度数，记作deg（v）。约定：每个环在其对应结点上度数增加2。定理1：每个图中，结点度数总和等于边数两倍。即证：∵每条边必关联两个结点，而一条边给于关联每个结点度数为1。故上述定理成立。定理2：在任何图中，度数为奇数结点必定是偶数个。证：设V1和V2分别是G中奇数度数和偶数度数结点集，则由上述定理有：因为是偶数之和，必为偶数，而是偶数。故得是偶数，即是偶数。（8）入度，出度：在有向图中，射入一个结点边数称为该结点入度。由一个结点射出边数称为该结点出度。结点出度与入度和是该结点度数。定理：在任何有向图中，全部结点入度和等于全部结点出度之和。（9）连接于同一对结点间多条边称为是平行。定义：含有平行边任何一个图称为多重图。不含有平行边和环图称作简单图。（10）完全图：简单图G=<V，E>中，若每一对结点间都有边相连，则称该图为完全图。定理4：n个结点无向完全图边数为：证实：在有n个结点无向完全图中，任意两点间都有边连接，n个结点中任意取两点组合为：故有n个结点无向完全图边数为（11）补图：给定一个图G，由G中全部结点和全部能使G成为完全图添加边组成图，称为G相对于完全图补图，或简称为G补图。记作。以下列图，（a）和（b）互为补图。（12）子图：设图G=<V，E>，假如有图G=<V，E>，且EE，VV，则称G为G子图。以下列图，（b）、（c）都是（a）子图。（13）生成子图：假如G子图包含G全部结点，则称该子图为G生成子图。以下列图，（b）、（c）都是（a）生成子图。（14）．定义：设图G=<V，E>及图G=<V，E>，假如存在一一对应映射g：vi→vi且e=（vi，vj）是G一条边，当且仅当e=（g（vi），g（vj））是G一条边，则称G与G同构，记作G≌G。两个图同构充要条件是：两个图结点和边分别存在着一一对应关系，且保持关联关系。两图同构一些必要条件：（1）结点数目相同。（2）边数相等。（3）度数相同结点数目相同这几个条件不是两个图同构充分条件。下两图，满足上述三个条件，但并不一样构7.2路与回路路其它概念（1）V0和vn分别称作路起点与终点。（2）一条路中全部边数目称作路长度。（3）若V0=vn则路称作回路。（4）一条路中全部边均不相同，则此路称作迹。（5）一条路中全部结点均不相同，则此路称作通路。（6）对于回路，除V0=vn外，其余结点均不相同，则此路称作圈。路表示方法：(a)结点表示法：(b)边表示法：例：给出有向图Ｇ，求起始于１，终止于３路定理：在一个含有n个结点图中，假如从结点vj到结点vk存在一条路，则从从结点vj到结点vk必存在一条小于n-1条边路。推论：在一个含有n个结点图中，假如从结点vj到结点vk存在一条路，则从从结点vj到结点vk必存在一条条边数小于n通路。无向图结点连通性[定义]设图Ｇ为无向图，且，若从vi到vj存在任何一条路径话，则称vi到vj是连通。有向图结点可达性[定义]设图Ｇ为简单有向图，且，若从vi到vj存在任何一条路径话，则称vi到vj是可达。图连通性：（1）连通性与非连通性：一个无向图，假如它任何两结点间均是连通，则称图G是连通，不然是非连通。一个有向图，忽略边方向后得到无向图，若是连通，则称该有向图为连通图，不然称非连通图。（2）强连通，单