欧美韩国国货护肤彩妆精油药妆礼品

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祛痘 8/29/202217.5 Euler and Hamilton PathKonigsberg(哥尼斯

2、堡)七桥问题问题：能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地。8/29/20222 Euler(欧拉)1736年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向重图，问题化为图论中简单道路的问题：定义欧拉道路（回路）： （，），称包含中所有边的简单道路为欧拉道路/Euler Path/E道路。 包含中所有边的简单回路为欧拉回路/Euler Circuit/E回路。8/29/20223定理1（欧拉定理）： 没有次为的孤立顶点的无向图存在欧拉道路的充要条件是： (1)图是连通的； (2)图中奇次顶点个数是个或2个。8/29/20224证明： 必要性

3、： 若存在欧拉道路，且没有次顶点，则每个顶点都有边关联，而边又全在欧拉道路上，故所有顶点都连通。 除了起点，终点外，欧拉道路每经过一个顶点，使顶点的次增加，故只有起点和终点才可能成为奇次顶点，而一个奇次顶点是不可能的，当无奇次顶点时，是欧拉回路。充分性： 若(1），(2)成立,构造欧拉道路.8/29/20225 若图存在奇次顶点，任取一个作为起点，若不存在，则任取一个顶点作为起点。 若此图有条边，总次为。每进入或离开一个顶点，让此顶点的次减，由于除了两个（或没有）奇次顶点外，其余顶点次为偶数，只要进得去，一定出得来，直至进入另一个奇次顶点（或起点）作为终点。这样构造的是简单道路，如果经过所有的

4、边，即得到一条欧拉道路。 不然，记走过的简单道路为1，1上顶点集1，边集1，1（1，1）是的子图。8/29/20226 若2（2，2）是1的关于的余图，21，但12，否则不连通，设12，从出发，用上面方法作2的简单回路2 回到,这能做到。 因为作好1后，留下顶点的次都是偶次。若12经过所有边，则欧拉道路是1走到时，先把2走完，最后走完1的余下道路。 若12仍未经过所有边，将12视为1重复上述过程，由于边有限，故存在欧拉道路。8/29/20227例1：（1）顶点的次：A(3) , B(2) , C(4) , D(2) , E(6), F(2) , G(6) , H(2) , I(4) , J(3

5、）。其中奇次顶点A，J（2）从A出发，走一条道路 （A,C,E,A,B,C,D,E,G,J）8/29/20228（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）8/29/20229（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出

6、发，（G，H，I，G），再加入即得欧拉道路。8/29/202210说明： 哥尼斯堡七桥问题，由于四个顶点都是齐次的，不可能有欧拉道路。应用与推广： （1） 一笔画问题； （2） 如果齐次顶点个数为2K个，此问题是K笔画问题。 8/29/202211例个顶点均为3次，至少要笔。8/29/202212推论（欧拉定理）： 没有次为的孤立顶点的无向图存在欧拉回路的充要条件是： (1)图是连通的； (2)图中没有奇次顶点。8/29/202213定理2（有向图的欧拉定理）： 不含出/入次为的孤立顶点的有向图具有欧拉道路的充要条件是：(1）弱连通；(2) 除了可能有个顶点，一个入次比出次大，一个出次比入次大

7、，其余顶点出次等于入次。推论不含出/入次为的孤立顶点的有向图具有欧拉回路的充要条件是：（1）弱连通；（2）所有顶点出次等于入次。8/29/202214Hamilton(哈密顿)道路问题： 年发明的一种游戏。 在一个实心的正十二面体，20个顶点标上世界著名大城市的名字，要求游戏者从某一城市出发，遍历各城市一次，最后回到原地。 这就是“绕行世界”问题。即找一条经过所有顶点（城市）的基本道路（回路）。8/29/202215定义哈密顿道路/回路： （，），G中经过中所有顶点的基本道路称为哈密顿道路/Hamilton Path，简称道路。 （，），G中经过中所有顶点的基本回路称为哈密顿回路/Hamilt

8、on Circuit，简称回路。8/29/202216图 每个顶点都是奇次的，不存在欧拉道路，但有道路。 图存在欧拉道路，不存在道路。8/29/202217定理3：设（，）是个顶点的简单图，如果任何一对顶点的次之和，则中一定有道路（n=2）。证明： 1、一定连通，否则分为二个不连通的分图1，2，其中1有1个顶点，2有2个顶点，1中每个顶点次1，2中每个顶点次2，从1中取一个顶点，2中取一个顶点，这一对顶点之和1212，与定理的假设矛盾。8/29/2022182、用归纳法证明中存在道路： (1)任取一条边（1，2），是含个顶 点的基本道路。 (2)如果已有个顶点的基本道路 （1，2，p），（）

9、必能构造个顶点的基本道路。 ）如果在1，2，p中存在与1或p相邻的顶点，则基本道路自然可以扩充一个顶点。 ）如果1，p仅与1，2，p中顶点相邻，则1，2，p必可适当排列，形成回路。8/29/202219 如果1与p相邻，显然成了环。不然，由于1，p仅与1，2，p中顶点相邻，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的边去掉，就形成一个环，如下图所示。8/29/202220

10、 又由的连通性，总可在1，2，p中找到一个点x，与1，2，p中某一顶相邻，不妨与k相邻，k1，kp，连上x与k的边，去掉k-1到k的边，可以从k-1为起点，一直走到k，再到x，这是一条个顶点的基本道路。8/29/202221 如果，仍继续扩充基本道路内的顶点，直至达到。注意: 此定理条件显然不是必要条件，如的边形，二个顶点次之和，而边形显然有道路。推论： （，）是的简单图，若任何一对顶点的次之和，则必有哈密顿回路。8/29/202222 由于推论条件也必满足定理3条件，存在道路，可类似于定理一的方法找到一条回路。定理4： 有向完全图一定存在道路。8/29/202223小 结1、E图：简单道路+所有边2、H图：基本道路+所有顶点8/29/202224进一步的思考1、E图/H图的应用2、E图/H图的判定8/29/202225 要判别一个图不存在道路，回路，也不是很容易的，只能对无向图给出一些必要条件：（1）道路存在必要条件： ）连通 ）至多只能有二个顶点的次，其余顶点的次。bcda8/29/202226（2）回路存在必要条件： 对的任一非空真子集，的连通分图个数|。 8/29/202227