图的基本概念教学

《图的基本概念教学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十四章　图的基本概念第四部分：图论七桥问题问题寻找走遍哥尼斯堡（KÖnigsberg）城的7座桥，且只许走过每座桥一次，最后又回到原出发点求解1736年瑞士大数学家欧拉（Leonhard•Euler）发表了关于“哥尼斯堡七桥问题”的论文（图论的第一篇论文）。他指出从一点出发不重复的走遍七桥，最后又回到原来出发点是不可能的。图论图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，如1736年欧拉（L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题棋盘上马的行走路线问题在中国

2、象棋中，马走“日”字，即每步从1×2矩形的一个顶点跳到相对的顶点。如图，马从M（3，2）一次只能跳到A、B、C、D、E、F、G、H中的任何一个位置。问题：马能否从棋盘上任意一点出发，不重复、不遗漏地走遍整个棋盘（即每一点都走到并且只到一次）？棋盘上马的行走路线问题将马目前所在位置涂成白色，用涂色的方法，将棋盘上的点分为黑、白相间的两类环游世界各国的问题英国数学家哈密顿于1859年以游戏的形式提出：把一个正十二面体的二十个顶点看成二十个城市，要求找出一条经过每个城市恰好一次而回到出发点的路线。这条路线就称“哈密顿圈”。一百多年来，对哈密顿问题的研究，促进了图论的发展。

3、四色猜想问题：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色用数学语言表示，即：“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字”图论图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的作用第十四章　图的基本概念第一节：图第二节：通路、回路、图的连通性第三节：图的矩阵表示和运算第一节：图无序积：设A，B为任意的两个集合，称{{a,b}

4、a∈A且b∈B}为A与B的无序积，记做A&B无向图：一个无向图G是一个二重组

5、(G),E(G)>,其中V(G)为有限非空结点（或叫顶点）集合,E(G)是边的集合，它是无序积V&V的多重子集，其元素为无向边，简称边。有向图：一个有向图G是一个二重组,其中V(G)为有限非空结点（或叫顶点）集合,E(G)是边的集合，它是笛卡儿乘积V×V的多重子集，其元素为有向边，简称边。下面定义一些专门名词：（１）通常用G表示无向图，D表示有向图，但G也可以泛指图。V(G)，E(G)分别表示G的顶点集和边集。

6、V(G)

7、,

8、E(G)

9、分别表示G的顶点数和边数，若

10、V(G)

11、＝n，则称G为n阶图。（２）若

12、V(G)

13、,

14、E(G)

15、均为有限数，则

16、称G为有限图。（３）若图G中，边集为空，则称之为零图，若G为n阶图，则称之为n阶零图，记为Nn，N1称为平凡图。（4）顶点集为空的图记为空图。第一节：图一些定义（5）称顶点或边用字母标定的图为标定图，否则成为非标定图。另外，将有向边改为无向边后的图称为原图的基图。（6）设G=为无向图，ek=(vi,vj)∈E,则称vi,vj为ek的端点，ek与vi或ek与vj是彼此关联的。若vi≠vj，则称ek与vi或ek与vj的关联次数为1，若vi=vj，则称ek与vi的关联次数为2，并称为环。任意的vl∈V，若vl≠vi且vl≠vj，则称ek与vl的关联次数为0。一些

17、定义（7）设无向图G=，vi,vj∈V，ek,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相邻。一些定义（8）设无向图G=，对所有的v∈V称为v的邻域，记为NG(v)，并称NG(v)∪{v}为v的闭邻域，记为。称为v的关联集，记为IG(v)。设有向图G

18、=，对所有的v∈V，称为v的后继元素。称为v的先驱元素。称两者之并为v的邻域，记为ND(v)。称ND(v)∪{v}，v的闭邻域。一些定义定义14.3在无向图中，关联一对顶点的无向边如果多于一条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于一条，并且这些边的始点和终点相同，则称这些边为平行边。含平行边的图称为多重图，即不含平行边也不含环的图称为简单图。一些定义非多重图称为线图。由定义可见，简单图是没有环和平行边的图。一些定义定义14.4：在无向图中，任意点其作为边的端点次数之和称为该点的度数，记为dG(v).在有向图