无向图详解(清华)

《无向图详解(清华)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图的基本概念1736年数学家欧拉发表了第一篇图论论文，解诀了哥尼斯堡七桥问题。图论起源于一些数学游戏难题，如迷宫问题，匿门博弈问题，棋盘上马的行走路线，哥尼斯堡七桥问题等，在这些问题的研究基础上，又提出了著名的四色问题，哈密尔顿（环游世界）数学难题。1847年克希霍夫用图论分析电路网络，最早将图论应用于工程科学。图论的应用非常广泛，主要有运筹学、网络理论、信息论、控制论、博奕论及计算机科学等等。7.1无向图和有向图无向图集合，称为无序对，记为.定义1设为集合，则称为的无序积，记为由定义知：7

2、/7例1则定义2一个无向图是一个二元组，即，其中⑴是非空集合，称为的顶点集，中元素称为顶点或结点；⑵是无序积的一个多重子集，称为的边集，中的元素称为无向边或简称边。由定义知，图的边是的两个元素的无序对，称是的端点。当时，称为环。由于是多重集合，因此，的两个结点之间可能存在若干条不同的边，称这些边为平行边。7/7设，用小圆圈表示中顶点，若，则就在之间连线段表示边，即可画出图形来。例2设，的图形为为环，为平行边。设为无向图，若都是有穷集合，则称是有限图（下面只研究有限图）。若，则称为阶图。若，则称为零

3、图，若，且，则称为平凡图。7/7有条边的阶图也称图，因此图为零图，图为平凡图。设是无向图的边，则称结点是邻接的，称边关联结点。没有边关联的结点称为孤立点，称关联结点的边数（当边为环时，以两条边计算）为的度数，记为。称度数为1的顶点为悬挂顶点，它所对应的边为悬挂边。例如在例2中.7/7为孤立点，为悬挂点，为悬挂边。所以顶点的度数之和为12，恰好是边数的两倍。下面给出图中顶点度数与边数之间的关系。定理1（握手定理）设是图的结点，则证：在计算图的各个结点的度数时，每条边提供的度数为2，条边提供的度数为2

4、，所以不含环及平行边的图称为简单图，任意两个结点都有边相连的简单图称为完全图。阶完全图共有条边，每个结点的度数为.定义3设都是图，如果非空集合7/7，则称是的子图；如果，则称是的真子图；如果，则称是的生成子图。(1)(2)(3)(3)为(1)的生成子图，(2)为(1)的真子图。同构定义6设两个图，如果存在双射函数，使得对于任意的，当且仅当，并且与的重数相同，则称与同构，记为.7/7由于图形的结点位置和连线长度都可任意选择，同一个图可能画出不同的形状来，因而引出图同构的概念。例5下面的两个图是同构的

5、。7/7