本次课主要内容 图的宽直径简介 (一)、敏格尔定理 (二)、图的宽直径相关概念 (三)、一些主要研究结果简介
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2 本次课主要内容 (一)、敏格尔定理 (二)、图的宽直径相关概念 图的宽直径简介 (三)、一些主要研究结果简介
(一)、敏格尔定理 敏格尔定理是图的连通性问题的核心定理之一，它 描述了图的连通度与连通图中不同点对间的不相交路的 数目之间的关系。 定义1设u与v是图G的两个不同顶点，S表示G的 顶点子集或边子集，如果u与v不在G-S的同一分支上 称S分离u和v。 例如： {u1,u4},{u12u1u4,u4u}分离点u2与u6
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 敏格尔定理是图的连通性问题的核心定理之一，它 描述了图的连通度与连通图中不同点对间的不相交路的 数目之间的关系。 (一)、敏格尔定理 定义1 设u与v是图G的两个不同顶点，S表示G的一个 顶点子集或边子集，如果u与v不在G-S的同一分支上， 称S分离u和v。 例如： u6 u5 u2 u3 u4 u1 ｛u1, u4｝, ｛u1u2, u1u4, u4u5｝分离点u2与u6
定理1（敏格尔1902-1985）(1)设x与y是图G中的两个 不相邻点，则G中分离点x与y的最少点数等于独立的（区，y) 路的最大数目； (2)设x与y是图G中的两个不同顶点，则G中分离点x与 y的最少边数等于G中边不重的（区，y)路的最大数目。 例如： 在该图中，独立的x,y)路最大条数是2，分离点x与y 的最小分离集是{u,u2},包含两个顶点
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 定理1 (敏格尔1902---1985) (1) 设x与y是图G中的两个 不相邻点，则G中分离点x与y的最少点数等于独立的(x, y) 路的最大数目； (2)设x与y是图G中的两个不同顶点，则G中分离点x与 y的最少边数等于G中边不重的(x, y)路的最大数目。 例如： x u4 y u3 u2 u1 在该图中，独立的(x ,y)路最大条数是2，分离点x与y 的最小分离集是｛u1, u2｝, 包含两个顶点
又在该图中，边不重的x,y)路最大条数是2，分离点x 与y的最小边分离集是{xu1,xu2},包含两条边。 该定理是图论中，也是通信理论中的最著名的定理之 一， 是由奥地利杰出数学家Mengeri在1927年发表的。 敏格尔(1902--1985)早年显示出数学物理天赋，1920 年入维也纳大学学习物理，次年，由于参加德国物理学家 Hans Hahn的“曲线概念的新意”讲座，而把兴趣转向了 数学。因为Has提到当时没有满意的曲线概念定义，包括 大数学家康托、约当，豪斯道夫等都尝试过，没有成功
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 x u4 y u3 u2 u1 又在该图中，边不重的(x ,y)路最大条数是2，分离点x 与y的最小边分离集是｛xu1, xu2｝, 包含两条边。 该定理是图论中，也是通信理论中的最著名的定理之 一，是由奥地利杰出数学家Menger在1927年发表的。 敏格尔(1902---1985）早年显示出数学物理天赋，1920 年入维也纳大学学习物理，次年，由于参加德国物理学家 Hans Hahn的“曲线概念的新意”讲座，而把兴趣转向了 数学。因为Hans提到当时没有满意的曲线概念定义，包括 大数学家康托、约当，豪斯道夫等都尝试过，没有成功
而且，认为不可能彻底解决。但是，尽管作为几乎没有数 学背景的本科生，通过自己的努力，敏格尔还是解决了该 问题。由此，他就转向曲线和维数理论的研究。 敏格尔本科期间，身体很差，父母双亡。但在1924年 在Hahn指导下完成了他的研究工作。1927年做了维也纳 大学几何学首席教授，同年，发表了“一弧定理”，即 敏格尔定理。 1930年，敏格尔来到匈牙利布达佩斯做访问，当时哥 尼正在写一本书，要囊括图论中的所有知名定理。敏格尔 向他推荐自己的定理，但哥尼最初不相信他，认为敏格尔 定理一定不对，花了一个晚上找反例试图否定敏格尔定理， 但没有成功，于是要了敏格尔的证明，终于把敏格尔定理 加在了他的著作的最后一节。 敏格尔被认为是20世纪最杰出数学家之一
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 而且，认为不可能彻底解决。但是，尽管作为几乎没有数 学背景的本科生，通过自己的努力，敏格尔还是解决了该 问题。由此，他就转向曲线和维数理论的研究。 敏格尔本科期间，身体很差，父母双亡。但在1924年 在Hahn指导下完成了他的研究工作。1927年做了维也纳 大学几何学首席教授，同年，发表了“n—弧定理”，即 敏格尔定理。 1930年，敏格尔来到匈牙利布达佩斯做访问，当时哥 尼正在写一本书，要囊括图论中的所有知名定理。敏格尔 向他推荐自己的定理，但哥尼最初不相信他，认为敏格尔 定理一定不对，花了一个晚上找反例试图否定敏格尔定理， 但没有成功，于是要了敏格尔的证明，终于把敏格尔定理 加在了他的著作的最后一节。 敏格尔被认为是20世纪最杰出数学家之一