Graph8/图论 Chapter 7 Graphs 图论 图/ Graph: 可直观地表示离散对象之间的相 互关系,研究它们的共性和特性,以 便解决具体问题。 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 1 Chapter 7 Graphs 图 论 图/Graph： 可直观地表示离散对象之间的相 互关系，研究它们的共性和特性，以 便解决具体问题
71图的概念 Introduction of Graph 72图的术语/ Graph Terminology 73图的表示与同构/ Representing Graph and graph Isomorphism 74连通性/ Connectivity 7.5欧拉道路与哈密尔顿道路/ Euler and hamilton paths 7.6最短道路问题/ hortest path problem 77平面图/ Planar graphs 78图的着色/ Graph Colorinsok eren chen, nIv
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 2 7.1 图的概念/Introduction of Graph 7.2 图的术语/Graph Terminology 7.3 图的表示与同构/ Representing Graph and Graph Isomorphism 7.4 连通性/Connectivity 7.5 欧拉道路与哈密尔顿道路/ Euler and Hamilton Paths 7.6 最短道路问题/Shortest Path Problem 7.7 平面图/Planar Graphs 7.8 图的着色/Graph Coloring
Graph8/图论 71图的概念/ ntroduction of Graph [定义]图 V是一个非空有限集,E是V上的一个二元关 系,有序对(V,E)称为有向图/ Directed Graph 若将E中的有序对看成是无序的(即将e=(a,b) 看成e={a,b}),则称(V,E)为无向图 / Undirected Graph。有向图和无向图统称为图 / Graph,记为G g =(v, E) 2/24/202111:16PM Deren Chen Zhejiang univ 3
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 3 7.1 图的概念/Introduction of Graph [定义]图 Ｖ是一个非空有限集，Ｅ是Ｖ上的一个二元关 系，有序对（Ｖ，Ｅ）称为有向图/Directed Graph。 若将E中的有序对看成是无序的（即将e=(a,b) 看 成 e={a,b} ） ， 则 称 （ Ｖ ， Ｅ ） 为 无向图 /Undirected Graph。有向图和无向图统称为图 /Graph ，记为G 。 G = （Ｖ，Ｅ）
Graph8/图论 定义顶点: V中的元素称为顶点,用带标记的 点表示,也称为结点 Vertices 定义边: 在有向图G中,若e=(a,b)∈E,e称为G的 有向边/ directed edge。用由a到b带箭头的线把 a和b连起来; 在无向图G中,若e=(a,b)∈E,e称为G的 无向边/ undirected edge。a、b间用连线连结, 有向边和无向边统称为G的边/edge 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 4 [定义]顶点： Ｖ中的元素称为顶点，用带标记的 点表示，也称为结点/Vertices。 [定义]边： 在有向图G中，若e=（ａ，ｂ）∈Ｅ，e称为G的 有向边/directed edge。用由ａ到ｂ带箭头的线把 ａ和ｂ连起来； 在无向图G中，若e=（ａ，ｂ）∈Ｅ，e称为G的 无向边/undirected edge 。a、ｂ间用连线连结， 有向边和无向边统称为G的边/edge
Graph8/图论 定义]图的分类 对图G=(V,E)。若对于任意的(a,b) ∈E,a≠b,则称图G为简单图/ Simple graph. 对图G=(V,E)。若允许E是一个重集,则 称图G为重图/ Multigraph。其相同的元素称为重 边 对图G=(V,E)。若G既允许是重图又允许 是非简单图,则称图G为拟图/ Pseudograph 般的G称为线性图/ Linear Graph 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 5 [定义]图的分类 对图G=（Ｖ，Ｅ）。若对于任意的（ａ，ｂ） ∈Ｅ，a b,则称图G为简单图/Simple Graph。 对图G=（Ｖ，Ｅ）。若允许Ｅ是一个重集，则 称图G为重图/Multigraph。其相同的元素称为重 边。 对图G=（Ｖ，Ｅ）。若G既允许是重图又允许 是非简单图，则称图G为拟图/Pseudograph。 一般的G称为线性图/Linear Graph
Graph8/图论 72图的术语/ Graph terminology 定义相邻和关联: 在无向图G中,若e=(a,b)∈E,则称a 与b相邻 adjacent,或边e关联a、 b/incident或联结 a、b/ connecto a、b称为边e的端点或结束顶点 /endpoint. 在有向图G中,若e=(a,b)∈E,即箭头由 的起点 nitial vertex,b称为e的终点 termina/b a到b,称a相邻到b,或a关联或联结b。a称为c end vertex o 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 6 7.2 图的术语/Graph Terminology [定义]相邻和关联： 在无向图G中，若e=（ａ，ｂ）∈Ｅ，则称ａ 与b相邻/adjacent，或边e关联a、ｂ/incident或联结 a、b/connect。a、b称为边e的端点或结束顶点 /endpoint. 在有向图G中，若e=（ａ，ｂ）∈Ｅ，即箭头由 ａ到ｂ，称ａ相邻到ｂ，或a关联或联结b。a称为e 的起点/initial vertex，b称为e的终点/terminal or end vertex
Graph8/图论 定义]孤立顶点: 若a∈V,a不与其他顶点相邻,称 a为孤立顶点/ solated 定义自回路: 若(a,a)∈E,({a,a}∈E), 称边(a,a)({a,a})是自回路/oop。 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 7 [定义]自回路： 若（ａ，ａ）∈Ｅ，（{ａ，ａ}∈Ｅ）， 称边（ａ，ａ）（{ａ，ａ}）是自回路/loop。 [定义]孤立顶点： 若ａ∈Ｖ，ａ不与其他顶点相邻，称 ａ为孤立顶点/isolated
Graph8/图论 定义顶点的次: 在无向图G中,与a相邻的顶点的数目称 为a的次或度 /degree记为deg(a)或da) 在有向图G中,以a为终点的边的条数称 为a的入次或入度 /in-degree记为deg(a或d (a)。以a为起点的边的条数称为a的出次或出 度/ out-degree。记为deg(a或d+(a)。 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 8 [定义]顶点的次： 在无向图G中，与a相邻的顶点的数目称 为a的次或度/degree。记为deg(a)或d(a)。 在有向图G中，以a为终点的边的条数称 为a的入次或入度/in-degree。记为deg– (a)或d – (a)。以a为起点的边的条数称为a的出次或出 度/out-degree。记为deg+ (a)或d + (a)
Graph8/图论 定理1( Handshaking)l设无向图G= (V,E)有e条边,则G中所有顶点的次 之和等于e的两倍 证明思路:利用数学归纳法。 定理2]无向图中次为奇数的顶点个数 恰有偶数个。 证明思路:将图中顶点的次分类,再利用 定理1。 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 9 [定理1 (Handshaking)] 设无向图G= （V，E）有e条边，则G中所有顶点的次 之和等于e的两倍。 证明思路：利用数学归纳法。 [定理2] 无向图中次为奇数的顶点个数 恰有偶数个。 证明思路：将图中顶点的次分类，再利用 定理1
Graph8/图论 定理3]设有向图G=(V,E)有e条边, 则G中所有顶点的入次之和等于所有顶点 的出次之和,也等于e 证明思路:利用数学归纳法。 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 10 [定理3] 设有向图G=（V，E）有e条边， 则G中所有顶点的入次之和等于所有顶点 的出次之和，也等于e。 证明思路：利用数学归纳法