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

Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.17.1图的概念/IntroductionofGraph7.2图的术语/GraphTerminology7.3图的表示与同构/RepresentingGraphandGraphIsomorphism7.4连通性/Connectivity7.5欧拉道路与哈密尔顿道路/EulerandHamiltonPaths7.6最短道路问题/ShortestPathProblem7.7平面图/PlanarGraphs7.8图的着色/GraphColoring祛痘图论8/19/20193:06AMDerenChen,ZhejiangUniv.27.5EulerandHamiltonPathKonigsberg(哥尼斯堡)七桥问题问题：能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地。ACBDGraphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.3Euler(欧拉)1736年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向重图，问题化为图论中简单道路的问题：[定义]欧拉道路（回路）：Ｇ＝（Ｖ，Ｅ），称包含Ｅ中所有边的简单道路为欧拉道路/EulerPath/E道路。包含Ｅ中所有边的简单回路为欧拉回路/EulerCircuit/E回路。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.4[定理1]（欧拉定理）：没有次为０的孤立顶点的无向图存在欧拉道路的充要条件是：(1)图是连通的；(2)图中奇次顶点个数是０个或2个。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.5证明：必要性：若存在欧拉道路，且没有０次顶点，则每个顶点都有边关联，而边又全在欧拉道路上，故所有顶点都连通。除了起点，终点外，欧拉道路每经过一个顶点，使顶点的次增加２，故只有起点和终点才可能成为奇次顶点，而一个奇次顶点是不可能的，当无奇次顶点时，是欧拉回路。充分性：若(1），(2)成立,构造欧拉道路.Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.6若图Ｇ存在奇次顶点，任取一个作为起点，若不存在，则任取一个顶点作为起点。若此图有ｎ条边，总次为２ｎ。每进入或离开一个顶点，让此顶点的次减１，由于除了两个（或没有）奇次顶点外，其余顶点次为偶数，只要进得去，一定出得来，直至进入另一个奇次顶点（或起点）作为终点。这样构造的是简单道路，如果经过所有的边，即得到一条欧拉道路。不然，记走过的简单道路为ｐ1，ｐ1上顶点集Ｖ1，边集Ｅ1，Ｇ1＝（Ｖ1，Ｅ1）是Ｇ的子图。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.7若Ｇ2＝（Ｖ2，Ｅ2）是Ｇ1的关于Ｇ的余图，Ｅ2＝Ｅ－Ｅ1，但Ｖ1∩Ｖ2≠φ，否则Ｇ不连通，设Ｃ∈Ｖ1∩Ｖ2，从Ｃ出发，用上面方法作Ｇ2的简单回路ｐ2回到Ｃ,这能做到。因为作好ｐ1后，留下顶点的次都是偶次。若ｐ1∪ｐ2经过所有边，则欧拉道路是ｐ1走到Ｃ时，先把ｐ2走完，最后走完ｐ1的余下道路。若ｐ1∪ｐ2仍未经过所有边，将ｐ1∪ｐ2视为ｐ1重复上述过程，由于Ｅ边有限，故存在欧拉道路。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.8例1：ABCDEFGHIJ（1）顶点的次：A(3),B(2),C(4),D(2),E(6),F(2),G(6),H(2),I(4),J(3）。其中奇次顶点A，J（2）从A出发，走一条道路（A,C,E,A,B,C,D,E,G,J）Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.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∈（Ｖ1Ｖ2）Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.10（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），再加入即得欧拉道路。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.11说明：哥尼斯堡七桥问题，由于四个顶点都是齐次的，不可能有欧拉道路。应用与推广：（1）一笔画问题；（2）如果齐次顶点个数为2K个，此问题是K笔画问题。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.12例８个顶点均为3次，至少要４笔。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.13[推论]（欧拉定理）：没有次为０的孤立顶点的无向图存在欧拉回路的充要条件是：(1)图是连通的；(2)图中没有奇次顶点。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.14定理2（有向图的欧拉定理）：不含出/入次为０的孤立顶点的有向图具有欧拉道路的充要条件是：(1）弱连通；(2)除了可能有２个顶点，一个入次比出次大１，一个出次比入次大１，其余顶点出次等于入次。推论不含出/入次为０的孤立顶点的有向图具有欧拉回路的充要条件是：（1）弱连通；（2）所有顶点出次等于入次。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.15Hamilton(哈密顿)道路问题：１８５９年发明的一种游戏。在一个实心的正十二面体，20个顶点标上世界著名大城市的名字，要求游戏者从某一城市出发，遍历各城市一次，最后回到原地。这就是“绕行世界”问题。即找一条经过所有顶点（城市）的基本道路（回路）。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.16[定义]哈密顿道路/回路：Ｇ＝（Ｖ，Ｅ），G中经过Ｖ中所有顶点的基本道路称为哈密顿道路/HamiltonPath，简称Ｈ道路。Ｇ＝（Ｖ，Ｅ），G中经过Ｖ中所有顶点的基本回路称为哈密顿回路/HamiltonCircuit，简称Ｈ回路。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.17AB图Ａ每个顶点都是奇次的，不存在欧拉道路，但有Ｈ道路。图Ｂ存在欧拉道路，不存在Ｈ道路。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.18[定理3]：设Ｇ＝（Ｖ，Ｅ）是ｎ个顶点的简单图，如果任何一对顶点的次之和≥ｎ－１，则Ｇ中一定有Ｈ道路（n=2）。证明：1、Ｇ一定连通，否则Ｇ分为二个不连通的分图Ｇ1，Ｇ2，其中Ｇ1有ｎ1个顶点，Ｇ2有ｎ2个顶点，Ｇ1中每个顶点次≤ｎ1－１，Ｇ2中每个顶点次≤ｎ2－１，从Ｇ1中取一个顶点，Ｇ2中取一个顶点，这一对顶点之和≤ｎ1－１＋ｎ2－１＝ｎ1＋ｎ2－２＝ｎ－２＜ｎ－１，与定理的假设矛盾。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.192、用归纳法证明Ｇ中存在Ｈ道路：(1)任取一条边（Ｖ1，Ｖ2），是含２个顶点的基本道路。(2)如果已有ｐ个顶点的基本道路（Ｖ1，Ｖ2，…，Ｖp），（ｐ≤ｎ－１）必能构造ｐ＋１个顶点的基本道路。ａ）如果在Ｖ－｛Ｖ1，Ｖ2，…Ｖp｝中存在与Ｖ1或Ｖp相邻的顶点，则基本道路自然可以扩充一个顶点。ｂ）如果Ｖ1，Ｖp仅与｛Ｖ1，Ｖ2，…，Ｖp｝中顶点相邻，则｛Ｖ1，Ｖ2，…，Ｖp｝必可适当排列，形成回路。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.20如果Ｖ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的边去掉，就形成一个环，如下图所示。111,,,21kiiiVVV111,,,21kiiiVVVGraphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.21VxVkVk-1VjVj-1V1V2Vj-2Vp又由Ｇ的连通性，总可在Ｖ－｛Ｖ1，Ｖ2，…，Ｖp｝中找到一个点Ｖx，与｛Ｖ1，Ｖ2，…，Ｖp｝中某一顶相邻，不妨与Ｖk相邻，Ｖk≠Ｖ1，Ｖk≠Ｖp，连上Ｖx与Ｖk的边，去掉Ｖk-1到Ｖk的边，可以从Ｖk-1为起点，一直走到Ｖk，再到Ｖx，这是一条ｐ＋１个顶点的基本道路。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.22如果ｐ＋１＜ｎ，仍继续扩充基本道路内的顶点，直至达到ｎ。注意:此定理条件显然不是必要条件，如ｎ≥６的ｎ边形，二个顶点次之和＝４，４＜ｎ－１，而ｎ边形显然有Ｈ道路。[推论]：Ｇ＝（Ｖ，Ｅ）是ｎ≥３的简单图，若任何一对顶点的次之和≥ｎ，则Ｇ必有哈密顿回路。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.23由于推论条件也必满足定理3条件，存在Ｈ道路，可类似于定理一的方法找到一条回路。[定理4]：有向完全图一定存在Ｈ道路。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.24小结1、E图：简单道路+所有边2、H图：基本道路+所有顶点Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.25进一步的思考1、E图/H图的应用2、E图/H图的判定Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.26要判别一个图不存在Ｈ道路，Ｈ回路，也不是很容易的，只能对无向图给出一些必要条件：（1）Ｈ道路存在必要条件：１）连通２）至多只能有二个顶点的次＜２，其余顶点的次≥２。bcdaGraphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.27（2）Ｈ回路存在必要条件：对Ｖ的任一非空真子集Ｓ，Ｇ－Ｓ的连通分图个数≤|Ｓ|。Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.28AA2BBA1BAABBBAB解：取Ｓ＝｛A1，A2｝Graphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.29G－Ｓ存在3个分图根据H道路存在的必要条件之二，可知：H道路不存在。AA2BBA1BAABBBABGraphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.30应用问题之一：Knight’stour应用问题之二：GrayCode应用问题之三：TowerofHanoiGraphs/图论8/19/20193:06AMDerenChen,ZhejiangUniv.31练习pp.48616，36、38、55