《图的概念introduction》由会员分享，可在线阅读，更多相关《图的概念introduction（31页珍藏版）》请在金锄头文库上搜索。
1、3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,1,7.1 图的概念/Introduction of Graph7.2 图的术语/Graph Terminology7.3 图的表示与同构/ Representing Graph and Graph Isomorphism7.4 连通性/Connectivity7.5 欧拉道路与哈密尔顿道路/ Euler and Hamilton Paths7.6 最短道路问题/Shortest Path Problem7.7 平面图/Planar Graphs7.8 图的着色/Graph Coloring,3/20/2
2、018 8:42 AM,Deren Chen, Zhejiang Univ.,2,7.5 Euler and Hamilton Path,Konigsberg(哥尼斯堡)七桥问题,问题：能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,3,Euler(欧拉)1736年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向重图，问题化为图论中简单道路的问题：,定义欧拉道路（回路）： （，），称包含中所有边的简单道路为欧拉道路/Euler Path/E道路。 包含中所有
3、边的简单回路为欧拉回路/Euler Circuit/E回路。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,4,定理1（欧拉定理）： 没有次为的孤立顶点的无向图存在欧拉道路的充要条件是： (1)图是连通的； (2)图中奇次顶点个数是个或2个。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,5,证明： 必要性： 若存在欧拉道路，且没有次顶点，则每个顶点都有边关联，而边又全在欧拉道路上，故所有顶点都连通。 除了起点，终点外，欧拉道路每经过一个顶点，使顶点的次增加，故只有起点和终点才可能成为奇次顶点，而一个奇次顶
4、点是不可能的，当无奇次顶点时，是欧拉回路。,充分性： 若(1），(2)成立,构造欧拉道路.,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,6,若图存在奇次顶点，任取一个作为起点，若不存在，则任取一个顶点作为起点。 若此图有条边，总次为。每进入或离开一个顶点，让此顶点的次减，由于除了两个（或没有）奇次顶点外，其余顶点次为偶数，只要进得去，一定出得来，直至进入另一个奇次顶点（或起点）作为终点。这样构造的是简单道路，如果经过所有的边，即得到一条欧拉道路。,不然，记走过的简单道路为1，1上顶点集1，边集1，1（1，1）是的子图。,3/20/2018 8:42
5、 AM,Deren Chen, Zhejiang Univ.,7,若2（2，2）是1的关于的余图，21，但12，否则不连通，设12，从出发，用上面方法作2的简单回路2 回到,这能做到。 因为作好1后，留下顶点的次都是偶次。若12经过所有边，则欧拉道路是1走到时，先把2走完，最后走完1的余下道路。 若12仍未经过所有边，将12视为1重复上述过程，由于边有限，故存在欧拉道路。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,8,例1：,（1）顶点的次：A(3) , B(2) , C(4) , D(2) , E(6), F(2) , G(6) , H(2)
6、, I(4) , J(3）。其中奇次顶点A，J（2）从A出发，走一条道路 （A,C,E,A,B,C,D,E,G,J）,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,9,（3）1（1，1） 1 A，B，C，D，E，G，J 1 （A，B），（B，C），（A，C），（C，D），（C，E），（D，E），（E，G），（G，J） 2（2，2） 2 （E，F），（F，G），（E，J）， （G，H），（G，I），（I，J），（H，I） 2 E，F，G，H，I，J E（12）,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,1
7、0,（4）从E出发回到E的回路（E，F，G，I，J，E），加入到P1中 1 （A，C，E，F，G，I，J，E，A，B，C，D，G，J）（5）还有未经过的边，重复上述过程 ，从G出发，（G，H，I，G），再加入即得欧拉道路。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,11,说明： 哥尼斯堡七桥问题，由于四个顶点都是齐次的，不可能有欧拉道路。,应用与推广： （1） 一笔画问题； （2） 如果齐次顶点个数为2K个，此问题是K笔画问题。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,12,例个顶点均为3次，至少
8、要笔。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,13,推论（欧拉定理）： 没有次为的孤立顶点的无向图存在欧拉回路的充要条件是： (1)图是连通的； (2)图中没有奇次顶点。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,14,定理2（有向图的欧拉定理）： 不含出/入次为的孤立顶点的有向图具有欧拉道路的充要条件是：(1）弱连通；(2) 除了可能有个顶点，一个入次比出次大，一个出次比入次大，其余顶点出次等于入次。推论不含出/入次为的孤立顶点的有向图具有欧拉回路的充要条件是：（1）弱连通；（2）所有顶点出次
9、等于入次。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,15,Hamilton(哈密顿)道路问题： 年发明的一种游戏。 在一个实心的正十二面体，20个顶点标上世界著名大城市的名字，要求游戏者从某一城市出发，遍历各城市一次，最后回到原地。 这就是“绕行世界”问题。即找一条经过所有顶点（城市）的基本道路（回路）。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,16,定义哈密顿道路/回路： （，），G中经过中所有顶点的基本道路称为哈密顿道路/Hamilton Path，简称道路。 （，），G中经过中所有顶点的基
10、本回路称为哈密顿回路/Hamilton Circuit，简称回路。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,17,图 每个顶点都是奇次的，不存在欧拉道路，但有道路。 图存在欧拉道路，不存在道路。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,18,定理3：设（，）是个顶点的简单图，如果任何一对顶点的次之和，则中一定有道路（n=2）。,证明： 1、一定连通，否则分为二个不连通的分图1，2，其中1有1个顶点，2有2个顶点，1中每个顶点次1，2中每个顶点次2，从1中取一个顶点，2中取一个顶点，这一对顶点之和
11、1212，与定理的假设矛盾。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,19,2、用归纳法证明中存在道路： (1)任取一条边（1，2），是含个顶 点的基本道路。 (2)如果已有个顶点的基本道路 （1，2，p），（） 必能构造个顶点的基本道路。 ）如果在1，2，p中存在与1或p相邻的顶点，则基本道路自然可以扩充一个顶点。 ）如果1，p仅与1，2，p中顶点相邻，则1，2，p必可适当排列，形成回路。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,20,如果1与p相邻，显然成了环。不然，由于1，p仅与1，2，p
12、中顶点相邻，1，p的次。不妨设1的次为，分别记相邻顶点为i1，i2，ik，它们前面的顶点（指在基本道路1，2，p中的序）为 ，p必与中某顶点相邻，否则p的次，1与p的次之和，与任一对顶点次之和矛盾。 不妨p与j-1相邻，1与j相邻。将1与j连起来，p与j-1连起来，并将j-1到j的边去掉，就形成一个环，如下图所示。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,21,又由的连通性，总可在1，2，p中找到一个点x，与1，2，p中某一顶相邻，不妨与k相邻，k1，kp，连上x与k的边，去掉k-1到k的边，可以从k-1为起点，一直走到k，再到x，这是一条个顶
13、点的基本道路。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,22,如果，仍继续扩充基本道路内的顶点，直至达到。注意: 此定理条件显然不是必要条件，如的边形，二个顶点次之和，而边形显然有道路。,推论： （，）是的简单图，若任何一对顶点的次之和，则必有哈密顿回路。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,23,由于推论条件也必满足定理3条件，存在道路，可类似于定理一的方法找到一条回路。,定理4： 有向完全图一定存在道路。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Un
14、iv.,24,小 结,1、E图：简单道路+所有边2、H图：基本道路+所有顶点,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,25,进一步的思考,1、E图/H图的应用2、E图/H图的判定,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,26,要判别一个图不存在道路，回路，也不是很容易的，只能对无向图给出一些必要条件：（1）道路存在必要条件： ）连通 ）至多只能有二个顶点的次，其余顶点的次。,b,c,d,a,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,27,（2）回路存在必要条件： 对的任一非空真子集，的连通分图个数|。,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,28,解：取A1， A2 ,3/20/2018 8:42 AM,Deren Chen, Zhejiang Univ.,
