3图论 图基本概念9 14整理ppt.ppt

第四部分 图论 第 十四 章 图的基本概念 一、图的概念 1、无序积定义：设A，B为任意的两个集合， 称 ｛｛a，b｝ ┃ a∈A ∧b∈B ｝为A与B的无序积，记作A B 2、图的定义 1） 定义1 一个无向图是一个有序的二元组 V，E ，记作G，其中 (1) V ≠ ? 称为顶点集，其元素称为顶点或结点． (2) E称为边集，它是无序积V＆V的多重子集，其元素称为无向边， 简称为边． 无向图G = V，E 其中 V＝｛v1,v2,v3,v4 ｝ 边集合E＝｛(v1,v2), (v2,v3),(v3,v2), (v3,v1),(v2,v2),(v2,v2), (v1,v2),｝ 园括号表示无向边 2） 定义2 一个有向图是一个有序的二元组V，E，记作D，其中 (1) V ≠ ? 称为顶点集，其元素称为顶点或结点． (2)E为边集，它是笛卡儿积 V ⅹ V的有穷多重子集，其元素称为有向边， 简称边(弧)． 有向图D=V，E 其中 V＝｛v1,v2,v3 ｝ 边集合E＝｛v1,v2,v1,v2,v2,v3,v3,v2,v2,v2 ,v1,v3,v3,v1｝ 尖括号 （与前面的关系的图表示相当） 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) 常用ek表示无向边(vi，vj)( 或有向边vi，vj ) 设G＝V，E 为无向图，ek = (vi，vj)∈E， 则称vj，vj为ek的端点， ek与vi、vj是彼此相关联的． 起终点相同的边称为环 不与任何边关联的结点称为孤立点（包括有向向图) 5）邻接： 边的相邻：ek，el∈E．若ek与el至少有一个公共端点，则称ek与el是相邻的 顶点的相邻： 若?et∈E，使得et = vi，vj， 则称vi为et的始点，vj为et的终点， 并称vi邻接到vj，vj邻接于vi 两个结点为一条边的端点，则称两个结点互为邻接点， 也称边关联于这两个结点，或称两个结点邻接于此边。 6）平行边： 在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数． 在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(也就是它们的方向相同)，则称这些边为平行边． 7）多重图和简单图：含平行边的图称为多重图 既不含平行边也不含环的图称为简单图．（主要讨论简单图） 4、结点的度 1）定义4 设G＝V，E为无向图，? v ∈V，称v作为边的端点次数之和为v的度数，简记为度记作d G(v)， 简记为dG(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中结点最大的入度