资源描述：
《08图论a_图的基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、程序设计基础离散数学高级语言程序设计•2007春季秋季程序设计基础离散数学高级语言程序设计•2007春季秋季C++图论C++图论主要内容图的基本概念n一个图G是一个三重组，其中V(G)图基本概念是一个非空的结点（顶点）集合，E(G)是边的集n图的基本概念合，ΦG是从边集E到结点偶对集合上的函数。顶点的度数一个图可以用一个图形表示。n顶点的度数G=〈V(G),E(G),Φ〉Gn图的同构图的同构V(G)={a,b,c,d}E(G)={e1,e2,e3,e4,e6,e7}n图的运算图的运算
2、ΦG(e1)=(a,b),Φ(e2)=(a,c),Gn图的子图与补图ΦG(e3)=(b,d),子图与补图Φ(e4)=(b,c),GΦ(e5)=(d,c),GΦ(e6)=(a,d),GΦ(e7)=(b,b)。SEI1SEIG2程序设计基础离散数学高级语言程序设计•2007春季秋季程序设计基础离散数学高级语言程序设计•2007春季秋季C++图论C++图论图的基本概念图的基本概念n定义中的结点偶对可以是有序的，也可以是无序n每一条边都是有向边的图称为有向图；每一条边都图基本概念的。若边e所对应的偶对(a,b)是有序的
3、，即序偶图基本概念是无向边的图称为无向图；如果在图中一些边是有，则称e是有向边。有向边简称弧，a称为弧e向边，而另一些边是无向边，则称这个图是混合顶点的度数的始点，b称为弧e的终点，统称为e的端点。称e是顶点的度数图。关联于结点a和b的，结点a和b是邻接的。若边e所n约定：表示有向边，(a,b)表示无向边，[a,b]图的同构对应的偶对(a,b)是无序的，则称e是无向边。无向图的同构既表示有向边又表示无向边。于是图的三元组表达边简称棱，除无始点和终点概念外，其它与有向边形式可以变为二元组形式G
4、=，其中E为偶对图的运算相同。图的运算集合，隐含表示图中的边。n把无向图中每一条边都看成两条方向不同的有向子图与补图子图与补图边，无向图就成为有向图；把有向图中每条有向边都看成无向边，就成为无向图。通常称这个无向图是该有向图的底图。SEI3SEI4程序设计基础离散数学高级语言程序设计•2007春季秋季程序设计基础离散数学高级语言程序设计•2007春季秋季C++图论C++图论图的基本概念图的基本概念n在图中，不与任何结点邻接的结点称为孤立结点。n赋权图G是一个三重组或四重组图基本概念全由孤
5、立结点构成的图称为零图。关联于同一结点图基本概念，其中V是一个非空的结点集合，E是的一条边称为自回路，自回路的方向不定。边的集合，f是定义在V上的函数，g是定义在E上顶点的度数n在有向图中，两结点间（包括结点自身间）若同始顶点的度数的函数。点和同终点的边多于一条，则这几条边称为平行图的同构边。在无向图中，两结点间（包括结点自身间）若图的同构3a如左图所示：V={a,b,c},多于一条边，则这几条边称为平行边。两结点a和be1E={e1,e2,e3},图的运算间互相平行的边的条数称为边[a,b]
6、的重数。仅有一图的运算6e3条边时，重数为1，无边时重数为0。8f(a)=3,f(b)=4,f(c)=5,子图与补图n含有平行边的图称为多重图。非多重图称为线图。子图与补图4g(e1)=6,g(e2)=7,g(e3)=8。7无自回路的线图称为简单图。be25c多重图要用三元组形式表示，线图则可以不用。SEI5SEI61程序设计基础离散数学高级语言程序设计•2007春季秋季程序设计基础离散数学高级语言程序设计•2007春季秋季C++图论C++图论顶点的度数顶点的度数n在有向图中，对于任何结点v，以v为始点的边的条
7、n设G是一个(n,m)图，它的结点集合为数称为结点v的引出次数（或出度），记为deg+(v);图基本概念图基本概念V={v1,v2,...,vn}，则以v为终点的边的条数称为结点v的引入次数（或入n度），记为deg-(v)；结点v的引出次数和引入次数顶点的度数顶点的度数ådeg(vi)=2m之和称为结点v的次数（或度数），记为deg(v)。i=1图的同构n在无向图中，结点v的次数是与结点v相关联的边的图的同构条数，也记为deg(v)。孤立结点的次数为0。在有向图中，可以写成nn图的运算以后把具有n个结点和m条边
8、的图简称为(n,m)图。图的运算+-ådeg(vi)+ådeg(vi)=2mn各结点的次数均相同的图i=1i=1子图与补图称为正则图，各结点的次子图与补图数均为k时，称为k－正则图。右图为彼得森图。SEI7SEI8程序设计基础离散数学高级语言程序设计•2007春季秋季程序设计基础离散数学高级语言程序设计•2007春季秋季C++图论C++图论顶点的度数图的同构n在图中，次数为奇数的结点必
