第十四章图的基本概念.ppt

棋盘上马的行走路线问题 在中国象棋中，马走“日”字，即每步从 1×2 矩形的一个顶点跳到相对的顶点。如图，马从M（3，2）一次只能跳到A、B、C、D、E、F、G、H中的任何一个位置。 问题：马能否从棋盘上任意一点出发，不重复、不遗漏地走遍整个棋盘（即每一点都走到并且只到一次）？ 棋盘上马的行走路线问题 将马目前所在位置涂成白色，用涂色的方法，将棋盘上的点分为黑、白相间的两类 环游世界各国的问题 英国数学家哈密顿于1859年以游戏的形式提出：把一个正十二面体的二十个顶点看成二十个城市，要求找出一条经过每个城市恰好一次而回到出发点的路线。这条路线就称“哈密顿圈”。一百多年来，对哈密顿问题的研究，促进了图论的发展。 四色猜想 问题：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色 用数学语言表示，即：“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字” 图论 图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的作用 第一节：图 无序积：设A，B为任意的两个集合，称 {{a,b} | a∈A且b∈B} 为A与B的无序积，记做AB 无向图：一个无向图G是一个二重组V(G),E(G), 其中V(G)为有限非空结点（或叫顶点）集合, E(G)是边的集合，它是无序积VV的多重子集，其元素为无向边，简称边。 有向图：一个有向图G是一个二重组V(G),E(G), 其中V(G)为有限非空结点（或叫顶点）集合, E(G)是边的集合，它是笛卡儿乘积V×V的多重子集，其元素为有向边，简称边。 可图化 例：判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？ (5,5,4,4,2,1) (5,4,3,2,2) (3,3,3,1) (d1,d2,…,dn), d1d2…dn≥1, 且 为偶数 (4,4,3,3,2,2) 通路和回路 例： 1. 无向完全图Kn（n≥3）中有几种非同构的圈？ 2. 无向完全图K3的顶点依次标定为a，b，c. 在定义意义下K3中有多少 不同的长度为3的圈？ 点连通度、边连通度的关系 对于任何无向图G，有 图的矩阵表示 A(D)中所有元素之和为D中长度为1的通路的条数 对角线元素之和为D中长度为1的回路的条数 考虑：A(D)的n次幂表示什么？ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 图的矩阵表示 讨论定义： （1）若图D的邻接矩阵中的元素为0和1，又称为布尔矩阵。 （2）图D的邻接矩阵中的元素的次序是无关紧要的，只要进行行和行、列和列的交换，则可得到相同的矩阵。 图的矩阵表示 （3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵； 若图是自反的，则主对角线的元素均为1； 若图是对称的，则对于i和j有aij=aji，主对角线的元素不论。 图的矩阵表示 （4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0； （5）在有向图的邻接矩阵中： ①行中1的个数就是行中相应顶点的出度 ②列中1的个数就是列中相应顶点的入度 d+(1)=1,d-(1)=2 d+(2)=2,d-(2)=2 d+(3)=3,d-(3)=1 d+(4)=1,d-(4)=2 图的矩阵表示 *矩阵的计算（有向图中）： 设： 令 其含义为： ①若ai1×a1j＝1，则表示有i→1→j长度为2的通路； ②A2表示i和j之间具有长度为2的不同通路的条数， A3表示i和j之间具有长度为3的不同通路的条数， A4表示i和j之间具有长度为4的不同通路的条数。 例 从2→1有二条长度为2的通路； 从3→1有二条长度为3的通路; 从2→1有二条长度为4的通路； 图的矩阵表示 定理14.11：设Ｇ＝＜Ｖ，Ｅ＞，|V|=ｎ，A为G的邻接矩阵，则Am的元素表示（i ,j）之间具有长度为m的不同通路数，（i ,j）表示矩阵Am中的一个记入值。（长度为m的路径条数） 推论：设Ｇ＝＜Ｖ，Ｅ＞，|V|=ｎ，二个顶点之间的距离d(vi,vj)可以从A1,A2,…, An中去求得，当（i ,j）记入值不为零且矩阵的幂次最小时，这个幂次即是d(vi,vj) 。 由推论1可以求得一个图的距离矩阵。 例 图的矩阵表示 推论：Bn = A1＋A2＋…＋An表示i到j之间的长度小于等于n的所有通路数，