离散数学图论-图的基本概念.pptxVIP

图 论;七座桥所有的走法一共有7！=5040种。 1736年，在经过一年的研究之后，29岁的欧拉提交了《哥尼斯堡七桥》的论文，圆满解决了这一问题，同时开创了数学新分支---图论。;图 论;一、图的概念;2） 定义2 一个有向图是一个有序的二元组V，E，记作D，其中 (1) V ≠ ? 称为顶点集，其元素称为顶点或结点． (2)E为边集，它是笛卡儿积 VⅹV的有穷多重子集，其元素称为有向边，简称边(弧)． 有向图D=V,E 其中 V＝｛v1,v2,v3 ｝ 边集合E＝｛v1,v2,v2,v1, v2,v1,v2,v3,v3,v3 v3,v3｝ （与前面的关系的图表示相当）;3、有关图的术语 1）用G表示无向图，D表示有向图。 有时用V(G)，E(G)分别表示G的顶点集和边集。 2）用|V(G)|，|E(G)|分别表示G的顶点数和边数 若｜V(G)｜＝n，则称G为n阶图。对有向图有相同定义。 3）在图G中，若边集E(G)＝?，则称G为零图 若G为n阶图，则称G为n阶零图，记作Nn，特别是称N1为平凡图 4）在用图形表示一个图时，若给每个结点和每一条边均指定一个符号（字母或数字），则称这样的图为标定图。 5) 常用ek表示边(vi，vj)( 或vi，vj ) 设G＝V，E 为无向图，ek = (vi，vj)∈E， 则称vi，vj为ek的端点， ek与vi、vj是彼此相关联的． 起、终点相同的边称为环 不与任何边关联的结点称为孤立点（包括有向图);6）邻接： 边的相邻：ek，el∈E．若ek与el至少有一个公共端点， 则称ek与el是相邻的 顶点的相邻：若?et∈E，使得et = vi，vj， 则称vi为et的始点，vj为et的终点， 并称vi邻接到vj，vj邻接于vi 两个结点为一条边的端点，则称两个结点互为邻接点， 也称边关联于这两个结点，或称两个结点邻接于此边。 7）平行边： 在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数． 在有向图中，关联一对顶点的有向边如果多于1条，并且它们的方向相同，则称这些边为平行边． 8）多重图和简单图：含平行边的图称为多重图 既不含平行边也不含环的图称为简单图．（主要讨论简单图） ;4、结点的度 1) 定义4 设G＝V，E为无向图，? v ∈V，称v作为边的端点的次数之和为v的度数，简称为度，记作dG(v)， 简记为d(v)，即为：结点v 所关联的边的总条数 关于有向图D＝V，E 有： ?v∈V，称v作为边的始点的次数之和为v的出度，记作d+(v)， 称v作为边的终点的次数之和为v的入度，记作d-(v) 称d+(v)+ d-(v)为 v的度数，记作dD(v). 2) 称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边 根据结点的度数可将结点分为： 度为偶数(奇数)的顶点称为偶度顶点(奇度顶点). 一个环提供的度为2（有向图的环提供入度1和出度1） ;3）定义：?(G) = max{d(v)|v∈V(G)} 为图G中结点最大的度 δ(G) = min{d(v)|v∈V(G)} 为图G中结点最小的度 简记为?、δ 定义： ?－(D) = max{d－(v)|v∈V(D)} 为图D中结点最大的入度 ?＋(D) = max{d＋(v)|v∈V(D)} 为图D中结点最大的出度 δ-(D) = min{d－(v)|v∈V(D)} 为图D中结点最小的入度 δ＋(D) = min{d＋(v)|v∈V(D)} 为图D中结点最小的出度 5、握手定理（欧拉） 1)定理1 设G＝V,E为任意无向图,V＝{v1，v2，…，vn},｜E｜ = m， 则 ∑d(vi) ＝ 2m (所有结点的度数值和为边数的2倍) 证: G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边共提供2m度 2) 定理2 设D＝V,E为任意有向图,V＝{v1，v2，…，vn},|E| = m ， 则 ∑d+(vi) = ∑d-(vi) = m． 且∑d(vi)＝2m 3) 推论 任何图(无向的或有向的)中，奇度顶点的个数是偶数