4图论 图基本概念9 21.ppt

例：给定有向图D，4个顶点7条边 邻接矩阵为 上次课主要内容 一、图的概念 1、图的定义 定义1 一个无向图是一个有序的二元组 V，E ，记作G，其中 (1) V ≠ ? 称为顶点集，其元素称为顶点或结点． (2) E称为边集，它是无序积V＆V的多重子集，其元素称为无向边， 简称为边． 无向图G = V，E V＝｛v1,v2,v3 ｝ 边集合E＝｛(v1,v2),(v3,v2)…｝ 园括号表示无向边 定义2 一个有向图是一个有序的二元组V，E，记作D，其中 (1) V ≠ ? 称为顶点集，其元素称为顶点或结点． (2)E为边集，它是笛卡儿积 V V的多重子集，其元素称为有向边， 简称边(弧)． 有向图D=V，E V＝｛v1,v2,v3 ｝ 边集合E＝｛v1,v2,v1,v2…｝ 尖括号表示有向边 边也可以用字母ek表示 有向图的基图—将其有向边的方向去掉所得的无向图 2、 节点与边的关联性 设G＝V，E 为无向图，ek = (vi，vj)∈E， 则称vj，vj为ek的端点， ek与vi、vj是彼此相关联的． 不与任何边关联的结点称为孤立点（包括有向图) 3、邻接 (1)边的相邻：ek，el∈E．若ek与el至少有一个公共端点，则称ek与el是相邻的 (2)顶点的相邻： 若?et∈E，使得et = vi，vj， 并称vi邻接到vj，vj邻接于vi 两个结点为一条边的端点，则称两个结点互为邻接点 4、平行边： 在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数． 在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(也就是它们的方向相同)，则称这些边为平行边． 5、多重图和简单图：含平行边的图称为多重图 既不含平行边也不含环的图称为简单图． 二、结点的度 1）定义4 设G＝V，E为无向图，? v ∈V，称v作为边的端点次数之和为v的度数，简记为度记作d G(v)， 简记为d(v)即为：结点v 所关联的边的总条数 关于有向图D＝V，E 有： ?v ∈V，称v 作为边的始点的次数之和为v的出度，记作d+(v)， 称v作为边的终点的次数之和为v的入度，记作d-(v)， 称d+(v) + d-( v)为 v的度数，记作d (v) 2）度为偶数(奇数)的顶点称为偶度(奇度)顶点 3、握手定理（欧拉） 1)定理1 设G＝V,E为任意无向图,V＝{v1，v2，…，vn},｜E｜ = m， 则 ∑d(vi) ＝ 2 m (所有结点的度数值和为边数的2倍) 2) 定理2 设D＝V,E为任意有向图,V＝{v1，v2，…，vn},|E| = m ， 则 ∑d+(vi) ＝ ∑ d-(vi) = m． 且∑d(vi)＝2 m 3) 推论 任何图(无向的或有向的)中，奇度顶点的个数是偶数 4) 结点的度数序列 (1) 设G＝V，E为一个n阶无向图，V＝{v1，v2，…，vn} 称d(v1)，d(v2)， …，d(vn) 为G的度数列 条件：奇度数的结点个数应该是偶数个 （2）序列的可图化： d=(d1,d2,…dn) 对一个整数序列d,若存在以n个顶点的n阶无向图G，有d(vi)=di 称该序列是可图化的 （3）定理 设非负整数列d＝(d1，d2，…，dn)，则d是可图化的当且仅当 ∑di = 0 (mod 2) (序列之和必须是偶数) （4）由于简单图中没有平行边及环 结论：n个结点的简单图中结点的最大度数（△（G)）应小于等于n-1 每个结点至多与其他n-1个结点相邻 三、图的同构 定义 设G1＝Vl，E1 ，G2=V2，E2为两个无向图(两个有向图)， 若存在双射函数f：V1 → V2 顶点的一一对应 对于? vi，vj∈V1