资源描述：
《图论资料图的基本概念--第一章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第1章图的基本概念本章内容1图2通路与回路3图的连通性4图的矩阵表示5图的运算1.1图的基本概念图的定义图的一些概念和规定简单图和多重图顶点的度数与握手定理图的同构完全图与正则图子图与补图无序积与多重集合设A，B为任意的两个集合，称{{a,b}
2、a∈A∧b∈B}为A与B的无序积，记作A&B。可将无序积中的无序对{a,b}记为(a,b)，并且允许a＝b。无论a,b是否相等，均有(a,b)＝(b,a)，因而A&B＝B&A。元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的
3、重复度。例如在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2,3,1,1。笛卡尔积设A，B为任意的两个集合，称{
4、a∈A∧b∈B}为A与B的笛卡尔积，记作AXB。笛卡尔积中的是有序对。只有a,b相等的时候才有(a,b)＝(b,a).也只有A=B时才有AXB＝BXA。定义1一个无向图是一个有序的二元组,记作G，其中（1）V≠称为顶点集，其元素称为顶点或结点。（2）E称为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。定义2一个有
5、向图是一个有序的二元组，记作D，其中（1）V≠称为顶点集，其元素称为顶点或结点。（2）E为边集，它是笛卡儿积V×V的多重子集，其元素称为有向边，简称边。无向图和有向图说明可以用图形表示图，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。例1.1例1.1(1)给定无向图G＝，其中V＝{v1,v2,v3,v4,v5}， E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.(
6、2)给定有向图D=，其中V＝{a,b,c,d}， E＝{,,,,,,}。画出G与D的图形。图的一些概念和规定G表示无向图，但有时用G泛指图(无向的或有向的)。D只能表示有向图。V(G)，E(G)分别表示G的顶点集和边集。若
7、V(G)
8、＝n，则称G为n阶图。若
9、V(G)
10、与
11、E(G)
12、均为有限数，则称G为有限图。若边集E(G)＝，则称G为零图，此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为平凡图。
13、在图的定义中规定顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为。标定图与非标定图、基图将图的集合定义转化成图形表示之后，常用ek表示无向边(vi,vj)（或有向边），并称顶点或边用字母标定的图为标定图，否则称为非标定图。将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的;任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。关联与关联次数、环、孤立点设G＝为无向图
14、，ek＝(vi,vj)∈E，称vi,vj为ek的端点，ek与vi或ek与vj是彼此相关联的。若vi≠vj，则称ek与vi或ek与vj的关联次数为1。若vi＝vj，则称ek与vi的关联次数为2，并称ek为环。任意的vl∈V，若vl≠vi且vl≠vj，则称ek与vl的关联次数为0。设D＝为有向图，ek＝∈E，称vi,vj为ek的端点。若vi＝vj，则称ek为D中的环。无论在无向图中还是在有向图中，无边关联的顶点均称为孤立点。相邻与邻接设无向图G＝，vi，vj∈V，e
15、k，el∈E。若et∈E，使得et＝(vi，vj)，则称vi与vj是相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。设有向图D＝，vi，vj∈V，ek，el∈E。若et∈E，使得et＝，则称vi为et的始点，vj为et的终点，并称vi邻接到vj，vj邻接于vi。若ek的终点为el的始点，则称ek与el相邻。邻域设无向图G＝，v∈V，称{u
16、u∈V∧(u,v)∈E∧u≠v}为v的邻域，记做NG(v)。称NG(v)∪{v}为v的闭邻域，记做NG
17、(v)。称{e
18、e∈E∧e与v相关联}为v的关联集，记做IG(v)。设有向图D＝，v∈V，称{u
19、u∈V∧∈E∧u≠v}为v的后继元集，记做Г+D(v)。称{u
20、u∈V∧∈E∧u≠v}为v的先驱元集，记做Г-D(v)。称Г+D(v)为v的出邻域,Г-D(v)为v的入邻域.Г+D(v)∪Г-D(v)为v的邻域，记做ND(v)。称ND(v)∪{v}为v的闭邻域，记做ND(v)。举例NG(v1)＝Г+D(d)＝{v2，v5}NG(v1)＝{v1，v2，v5}IG(v1)
