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

7.1图的概念/IntroductionofGraph7.2图的术语/GraphTerminology7.3图的表示与同构/RepresentingGraphandGraphIsomorphism7.4连通性/Connectivity7.5欧拉道路与哈密尔顿道路/EulerandHamiltonPaths7.6最短道路问题/ShortestPathProblem7.7平面图/PlanarGraphs7.8图的着色/GraphColoring7.5EulerandHamiltonPathEuler(欧拉)1736年对这个问题给出了否定的回答。将河岸和小岛作为图的顶点七座桥为边构成一个无向重图问题化为图论中简单道路的问题：[定理1]（欧拉定理）：没有次为０的孤立顶点的无向图存在欧拉道路的充要条件是：(1)图是连通的；(2)图中奇次顶点个数是０个或2个。证明：必要性：若存在欧拉道路且没有０次顶点则每个顶点都有边关联而边又全在欧拉道路上故所有顶点都连通。除了起点终点外欧拉道路每经过一个顶点使顶点的次增加２故只有起点和终点才可能成为奇次顶点而一个奇次顶点是不可能的当无奇次顶点时是欧拉回路。若图Ｇ存在奇次顶点任取一个作为起点若不存在则任取一个顶点作为起点。若此图有ｎ条边总次为２ｎ。每进入或离开一个顶点让此顶点的次减１由于除了两个（或没有）奇次顶点外其余顶点次为偶数只要进得去一定出得来直至进入另一个奇次顶点（或起点）作为终点。这样构造的是简单道路如果经过所有的边即得到一条欧拉道路。若Ｇ2＝（Ｖ2Ｅ2）是Ｇ1的关于Ｇ的余图Ｅ2＝Ｅ－Ｅ1但Ｖ1∩Ｖ2≠φ否则Ｇ不连通设Ｃ∈Ｖ1∩Ｖ2从Ｃ出发用上面方法作Ｇ2的简单回路ｐ2回到Ｃ这能做到。因为作好ｐ1后留下顶点的次都是偶次。若ｐ1∪ｐ2经过所有边则欧拉道路是ｐ1走到Ｃ时先把ｐ2走完最后走完ｐ1的余下道路。若ｐ1∪ｐ2仍未经过所有边将ｐ1∪ｐ2视为ｐ1重复上述过程由于Ｅ边有限故存在欧拉道路。例1：（3）Ｇ1＝（Ｖ1Ｅ1）Ｖ1＝{ABCDEGJ}Ｅ1＝{（AB）（BC）（AC）（CD）（CE）（DE）（EG）（GJ）}Ｇ2＝（Ｖ2Ｅ2）Ｅ2＝{（EF）（FG）（EJ）（GH）（GI）（IJ）（HI）}Ｖ2＝{EFGHIJ}E∈（Ｖ1Ｖ2）（4）从E出发回到E的回路（EFGIJE）加入到P1中Ｐ1＝（ACEFGIJEABCDGJ）（5）还有未经过的边重复上述过程从G出发（GHIG）再加入即得欧拉道路。说明：哥尼斯堡七桥问题由于四个顶点都是齐次的不可能有欧拉道路。例８个顶点均为3次至少要４笔。[推论]（欧拉定理）：没有次为０的孤立顶点的无向图存在欧拉回路的充要条件是：(1)图是连通的；(2)图中没有奇次顶点。定理2（有向图的欧拉定理）：不含出/入次为０的孤立顶点的有向图具有欧拉道路的充要条件是：(1）弱连通；(2)除了可能有２个顶点一个入次比出次大１一个出次比入次大１其余顶点出次等于入次。推论不含出/入次为０的孤立顶点的有向图具有欧拉回路的充要条件是：（1）弱连通；（2）所有顶点出次等于入次。Hamilton(哈密顿)道路问题：１８５９年发明的一种游戏。在一个实心的正十二面体20个顶点标上世界著名大城市的名字要求游戏者从某一城市出发遍历各城市一次最后回到原地。这就是“绕行世界”问题。即找一条经过所有顶点（城市）的基本道路（回路）。[定义]哈密顿道路/回路：Ｇ＝（ＶＥ）G中经过Ｖ中所有顶点的基本道路称为哈密顿道路/HamiltonPath简称Ｈ道路。Ｇ＝（ＶＥ）G中经过Ｖ中所有顶点的基本回路称为哈密顿回路/HamiltonCircuit简称Ｈ回路。图Ａ每个顶点都是奇次的不存在欧拉道路但有Ｈ道路。图Ｂ存在欧拉道路不存在Ｈ道路。[定理3]：设Ｇ＝（ＶＥ）是ｎ个顶点的简单图如果任何一对顶点的次之和≥ｎ－１则Ｇ中一定有Ｈ道路（n>=2）。2、用归纳法证明Ｇ中存在Ｈ道路：(1)任取一条边（Ｖ1Ｖ2）是含２个顶点的基本道路。(2)如果已有ｐ个顶点的基本道路（Ｖ1Ｖ2…Ｖp）（ｐ≤ｎ－１）必能构造ｐ＋１个顶点的基本道路。ａ）如果在Ｖ－｛Ｖ1Ｖ2…Ｖp｝中存在与Ｖ1或Ｖp相邻的顶点则基本道路自然可以扩充一个顶点。ｂ）如果Ｖ1Ｖp仅与｛Ｖ1Ｖ2…Ｖp｝中顶点相邻则｛Ｖ1Ｖ2…Ｖp｝必可适当排列形成回路。如果Ｖ