课程设置 图的基本概念 欧拉图与哈密顿图 树 平面图 支配集、覆盖集、独立集、匹配与着色 东南大学计算机科学与工程学院 同的出学 图论
图的基本概念 欧拉图与哈密顿图 树 平面图 支配集、覆盖集、独立集、匹配与着色
图论的由来七桥问题 ■世界上最多产的数学家 ■“分析的化身 ■除雅各比外无人企及的算 法大师 ■可在任何条件下工作终因 为过分劳累双目失明 ■因应用数学而备受各国政 府追捧 ■临死一刻仍保持科研风格 1707-1783 是否存在一条路线,可不重复地走遍七座桥。这就是哥尼斯堡七 A 桥问题1735年,有几名大学生写信给欧拉。欧拉在亲自观察了哥 尼斯堡七桥后,认真思考走法,但始终没能成功,于是他怀疑七 桥问题是不是原本就无解。1736年,在经过一年的研究之后,29 岁的欧拉提交了《哥尼斯堡七桥》的论文,圆满解决了这一问题, 同时开创了数学新一分支一一图论。 东南大学计算机科学与工程学院 同的出学 图论
世界上最多产的数学家 “分析的化身” 除雅各比外无人企及的算 法大师 可在任何条件下工作,终因 为过分劳累双目失明 因应用数学而备受各国政 府追捧 临死一刻仍保持科研风格 1707-1783 是否存在一条路线，可不重复地走遍七座桥。这就是哥尼斯堡七 桥问题. 1735年，有几名大学生写信给欧拉。欧拉在亲自观察了哥 尼斯堡七桥后，认真思考走法，但始终没能成功，于是他怀疑七 桥问题是不是原本就无解。 1736年，在经过一年的研究之后，29 岁的欧拉提交了《哥尼斯堡七桥》的论文，圆满解决了这一问题， 同时开创了数学新一分支——图论
图论的由来—四色问题 1852年,一位英国大学生发现了一种有趣的现象:“看 来,每幅地图都可以用四种颜色着色,使得有共同边界 的国家都被着上不同的颜色。”这个现象能不能从数学 上加以严格证明呢?他和在大学读书的弟弟决心试一试。 兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠, 可是研究工作没有进展。 1852年10月23日,他的弟弟就这个问题的证明请教了他的老师、著名数学家德,摩根,摩根也没有 能找到解决这个问题的途径,于是写信向自己的好友、著名数学家汉密尔顿爵士请教。汉密尔顿 接到摩尔根的信后,对四色问题进行论证。但直到1865年汉密尔顿逝世为止,问题也没有能够解 决。自此之后百年,无人能解决该问题,因此成为世界三大数学猜想之 1976年,两位美国数学家在伊利诺伊大学的BM360机上分1482种情况检查,历时1200个小时,作 了100亿个判断,证明了四色定理。并分别与1989年和1998年修正了部分瑕疵之后,宣告彻底解决 该问题。 东南大学计算机科学与工程学院 同的出学 图论
1852年，一位英国大学生发现了一种有趣的现象：“看 来，每幅地图都可以用四种颜色着色，使得有共同边界 的国家都被着上不同的颜色。”这个现象能不能从数学 上加以严格证明呢？他和在大学读书的弟弟决心试一试。 兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠， 可是研究工作没有进展。 1852年10月23日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德·摩根，摩根也没有 能找到解决这个问题的途径，于是写信向自己的好友、著名数学家汉密尔顿爵士请教。汉密尔顿 接到摩尔根的信后，对四色问题进行论证。但直到1865年汉密尔顿逝世为止，问题也没有能够解 决。自此之后百年，无人能解决该问题，因此成为世界三大数学猜想之一。 1976年，两位美国数学家在伊利诺伊大学的IBM360机上分1482种情况检查，历时1200个小时，作 了100亿个判断，证明了四色定理。并分别与1989年和1998年修正了部分瑕疵之后，宣告彻底解决 该问题
图论的由来路线选择问题 汉密尔铡周游世界问题 1859年,威廉·汉密尔顿爵士在给他朋友的一封信中,首先谈 到关于十二面体的一个数学游戏:能不能在图中找到一条回路 使它含有这个图的所有结点?他把每个结点看成一个城市,联 结两个结点的边看成是交通线。于是他的问题就是能不能找到 旅行路线,沿着交通线经过每个城市恰好一次,再回到原来的 出发地,他把这个问题称为周游世界问题。 中国邮递员问题 简单来说,邮递员问题就是在一个已知的地区,邮差要设法找到 条最短路径,可以走过此地区所有的街道,且最后要回到出发 点,中国邮递员问题由管梅谷教授在1960年提出,而美国国家标 准和技术研究院(NIST)的 Alan Go I dman首先将此问题命名为 · 中国邮路问题 东南大学计算机科学与工程学院 同的出学 图论
1859年，威廉·汉密尔顿爵士在给他朋友的一封信中，首先谈 到关于十二面体的一个数学游戏：能不能在图中找到一条回路， 使它含有这个图的所有结点？他把每个结点看成一个城市，联 结两个结点的边看成是交通线。于是他的问题就是能不能找到 旅行路线，沿着交通线经过每个城市恰好一次，再回到原来的 出发地，他把这个问题称为周游世界问题。 简单来说，邮递员问题就是在一个已知的地区，邮差要设法找到 一条最短路径，可以走过此地区所有的街道，且最后要回到出发 点，中国邮递员问题由管梅谷教授在1960年提出，而美国国家标 准和技术研究院（NIST）的 Alan Goldman 首先将此问题命名为 中国邮路问题
第十四章图的基本概念 ●第一节:图 ●第二节:通路、回路、图的连通性 ●第三节:图的矩阵表示和运算 东南大学计算机科学与工程学院 图论 2024 同的出学
第十四章 图的基本概念 ⚫第一节：图 ⚫第二节：通路、回路、图的连通性 ⚫第三节：图的矩阵表示和运算 2021/2/2
图的基本概念 无序积:设A,B为任意的两个集合,称{ab}|a∈A且 b∈B为A与B的无序积,记做A&B 定义141:一个无向图G是个二重组,其中V(G为有限 非空结点(或叫顶点)集合E(G是边的集合它是无序积N&N的多 重子集,其元素为无向边 定义142:一个有间MGEG其中VG 为有限非空结点(或叫顶点)集合E)是边的集合,它 是笛卡儿乘积VV的多重子集,具元素为有向边,简称边。 东南大学计算机科学与工程学院 同的出学 图论
定义14.2：一个有向图G是一个二重组, 其中V(G) 为有限非空结点（或叫顶点）集合, E(G)是边的集合，它 是笛卡儿乘积V×V的多重子集，其元素为有向边，简称边。 无序积：设A，B为任意的两个集合，称{{a,b} | a∈A且 b∈B}为A与B的无序积，记做A&B. 定义14.1：一个无向图G是一个二重组, 其中V(G)为有限 非空结点（或叫顶点）集合, E(G)是边的集合，它是无序积V&V的多 重子集，其元素为无向边，简称边
图的基本术语 通常用G表示无向图,D表示有向图,但G也可以泛指图。VG,EG 分别表示G的顶点集和边集。GE(G)分别表示G的顶点数和边数, 若V(G=n,则称G为n阶图。 若VGEG均为有限数,则称G为有限图 若图G中,边集为空,则称之为零图,若G为n阶图,则称之为n阶零 图记为Nn,N称为平凡图。顶点集为空的图记为空图。 4称页点或边用字母标定的图为标定图,否则称为非标定图。另外,将 有向边改为无向边后的图称为原图的基图。 5设G=为无向图,e=WM)∈E则称Wv为e的端点,e与v或ek 与v是彼此关联的。若≠v,则称e与V或e与V的关联次数为1,若 v=v,则称ek与v的关联次数为2,并称为环任意的v∈V,若≠v且 vV则称e与的关联次数为0
通常用G表示无向图，D表示有向图，但G也可以泛指图。V(G)，E(G) 分别表示G的顶点集和边集。|V(G)|,|E(G)|分别表示G的顶点数和边数， 若|V(G)|＝n，则称G为n阶图。 若|V(G)|,|E(G)|均为有限数，则称G为有限图。 若图G中，边集为空，则称之为零图，若G为n阶图，则称之为n阶零 图记为Nn，N1称为平凡图。顶点集为空的图记为空图。 称顶点或边用字母标定的图为标定图，否则称为非标定图。另外，将 有向边改为无向边后的图称为原图的基图。 设G=为无向图，ek=(vi ,vj )∈E,则称vi ,vj为ek的端点， ek与vi或ek 与vj是彼此关联的。若vi≠vj，则称ek与vi或ek与vj的关联次数为1，若 vi=vj，则称ek与vi的关联次数为2，并称为环。任意的vl∈V，若vl≠vi且 vl≠vj ，则称ek与vl的关联次数为0
图的基本术语 6设无向图G=,wv∈V,ee∈E。若有e=v),则称M与∨是 相邻的。若e与e至少有一个公共端点,则称e与e是相邻的。 有向图D=,Mv∈V,ee∈E。若有ekvy>,则e与M关 联,称为的始点,为的终点,并称邻接到,V等接于M,若e 的终点为e的始点,则称e与e相邻。 东南大学计算机科学与工程学院 同的出学 图论
设无向图G=，vi ,vj∈V， ek ,el∈E。若有ek=(vi ,vj )，则称vi与vj是 相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。 有向图D=，vi ,vj∈V，ek ,el∈E 。若有ek=，则ek与vi ,vj关 联，称vi为ek的始点，vj为ek的终点，并称vi邻接到vj，vj邻接于vi，若ek 的终点为el的始点，则称ek与el相邻。 Vi Vj Vl Vi
图的基本术语 设无向图G=,对所有的v∈V称 {uu∈∧(v)∈E入≠v} 为v的邻域,记为Ne(),并称N)∪记为v的闭邻域,记为N(V) 称{e|e∈E∧e与相关联}为v的关联集,记为l)。 设有向图D=,对所有的v∈V,称I(v)={u∈VA∈E入l≠v} 为的后继元素。称I(v)={∈V入∈E≠v为的先驱元素 称两者之并为v的邻域,记为Nv)称N()∪{},为v的闭邻域。 东南大学计算机科学与工程学院 同的出学 图论
设无向图G=，对所有的v∈V 称 { | ( , ) } u u V u v E u v 为v的邻域，记为NG(v)，并称NG(v) ∪{v}记为v的闭邻域，记为 N (v) G 称 { | } e e E e v 与 相关联 为v的关联集，记为IG(v) 。 设有向图D=，对所有的v∈V ，称 为v的后继元素。称 为v的先驱元素。 称两者之并为v的邻域，记为ND (v) 。称ND (v) ∪{v}，为v的闭邻域。 (v) {u | u V v,u E u v} D = + (v) {u | u V u,v E u v} D = −
平行边与多重图 定义143在无向图中,关联一对顶点的无向边如果多于一条, 则称这些边为平行边,平行边的条数称为重数。在 有向图中,关联一对顶点的有向边如果多于一条, 并且这些边的始点和终点相同,则称这些边为平行 边。含平行边的图称为多重图,即不含平行边也不 含环的图称为简单图。非多重图称为线图 东南大学计算机科学与工程学院 同的出学 图论
定义14.3 在无向图中，关联一对顶点的无向边如果多于一条， 则称这些边为平行边，平行边的条数称为重数。在 有向图中，关联一对顶点的有向边如果多于一条， 并且这些边的始点和终点相同，则称这些边为平行 边。含平行边的图称为多重图，即不含平行边也不 含环的图称为简单图。非多重图称为线图