概念introduction modeling组合与图论.pptx

3/9/20255:51AMDerenChen,ZhejiangUniv.17.1图的概念/IntroductionofGraph7.2图的术语/GraphTerminology7.3图的表示与同构/RepresentingGraphandGraphIsomorphism7.4连通性/Connectivity7.5欧拉道路与哈密尔顿道路/EulerandHamiltonPaths7.6最短道路问题/ShortestPathProblem7.7平面图/PlanarGraphs7.8图的着色/GraphColoring

3/9/20255:51AMDerenChen,ZhejiangUniv.27.5EulerandHamiltonPathKonigsberg(哥尼斯堡)七桥问题问题：能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地。

3/9/20255:51AMDerenChen,ZhejiangUniv.3Euler(欧拉)1736年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向重图，问题化为图论中简单道路的问题：[定义]欧拉道路（回路）：Ｇ＝（Ｖ，Ｅ），称包含Ｅ中所有边的简单道路为欧拉道路/EulerPath/E道路。包含Ｅ中所有边的简单回路为欧拉回路/EulerCircuit/E回路。

3/9/20255:51AMDerenChen,ZhejiangUniv.4[定理1]（欧拉定理）：没有次为０的孤立顶点的无向图存在欧拉道路的充要条件是：(1)图是连通的；(2)图中奇次顶点个数是０个或2个。

3/9/20255:51AMDerenChen,ZhejiangUniv.5证明：必要性：若存在欧拉道路，且没有０次顶点，则每个顶点都有边关联，而边又全在欧拉道路上，故所有顶点都连通。除了起点，终点外，欧拉道路每经过一个顶点，使顶点的次增加２，故只有起点和终点才可能成为奇次顶点，而一个奇次顶点是不可能的，当无奇次顶点时，是欧拉回路。充分性：若(1），(2)成立,构造欧拉道路.

3/9/20255:51AMDerenChen,ZhejiangUniv.6若图Ｇ存在奇次顶点，任取一个作为起点，若不存在，则任取一个顶点作为起点。若此图有ｎ条边，总次为２ｎ。每进入或离开一个顶点，让此顶点的次减１，由于除了两个（或没有）奇次顶点外，其余顶点次为偶数，只要进得去，一定出得来，直至进入另一个奇次顶点（或起点）作为终点。这样构造的是简单道路，如果经过所有的边，即得到一条欧拉道路。不然，记走过的简单道路为ｐ1，ｐ1上顶点集Ｖ1，边集Ｅ1，Ｇ1＝（Ｖ1，Ｅ1）是Ｇ的子图。

3/9/20255:51AMDerenChen,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重复上述过程，由于Ｅ边有限，故存在欧拉道路。

3/9/20255:51AMDerenChen,ZhejiangUniv.8例1：（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）

3/9/20255:51AMDerenChen,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）

3/9/20255:51AMDerenChen,ZhejiangUniv.10（4）从E出发回到E的回路（E，F，G，I，J，E），加入到P1中