fbpx
维基百科

瓦格纳定理

行進 22, 2024

在图论中，瓦格纳理论（英語：Wagner's theorem）是平面图的禁图表征，以Klaus Wagner的命名。 该定理说：当且仅当有限图的子式不包含完全图K5 或完全二分图K3,3 时候，那么该图就是平面的。

K5 (左) 和 K3,3 (右) 是非平面彼得森图的图子式 (彩色小圆圈和黑色边，删除红色顶点，收缩每个黄色圆圈内的边)。
两个平面图以及瓦格纳图的“clique-sum”，创建无K5图。

这是图子式论最早的结果之一，也是罗伯逊–西摩定理（Robertson-Seymour theorem）的先驱。

库拉托夫斯基定理的关系 编辑

瓦格纳1937年发表了证明。[1] 库拉托夫斯基以前1930年出版了自己库拉托夫斯基理论。[2]

根据该定理，当且仅当图的子图的细分不包含那些禁图K5 和 K3,3。

瓦格纳定理意味着库拉托夫斯基，所以是更普遍的。[3]

参考资料 编辑

  1. ^ Wagner, K., Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 1937, 114: 570–590, doi:10.1007/BF01594196 
  2. ^ Kuratowski, Kazimierz, (PDF), Fund. Math., 1930, 15: 271–283 [2019-04-25], （原始内容 (PDF)存档于2018-07-23） （法语） .
  3. ^ Bondy, J. A.; Murty, U.S.R., Graph Theory, Graduate Texts in Mathematics 244, Springer: 269, 2008, ISBN 9781846289699 .

行進 22, 2024
瓦格纳定理, 此條目翻譯品質不佳, 2023年3月31日, 翻譯者可能不熟悉中文或原文語言, 也可能使用了機器翻譯, 請協助翻譯本條目或重新編寫, 并注意避免翻译腔的问题, 明顯拙劣的翻譯請改掛, href, template, html, class, redirect, title, template, href, wikipedia, html, class, redirect, title, wikipedia, 提交刪除, 在图论中, 瓦格纳理论, 英語, wagner, theorem, 是平面图的禁图. 此條目翻譯品質不佳 2023年3月31日 翻譯者可能不熟悉中文或原文語言 也可能使用了機器翻譯 請協助翻譯本條目或重新編寫 并注意避免翻译腔的问题 明顯拙劣的翻譯請改掛 a href Template D html class mw redirect title Template D d a a href Wikipedia CSD html G13 class mw redirect title Wikipedia CSD G13 a 提交刪除 在图论中 瓦格纳理论 英語 Wagner s theorem 是平面图的禁图表征 以Klaus Wagner的命名 该定理说 当且仅当有限图的子式不包含完全图K5 或完全二分图K3 3 时候 那么该图就是平面的 K5 左 和 K3 3 右 是非平面彼得森图的图子式 彩色小圆圈和黑色边 删除红色顶点 收缩每个黄色圆圈内的边 两个平面图以及瓦格纳图的 clique sum 创建无K5图 这是图子式论最早的结果之一 也是罗伯逊 西摩定理 Robertson Seymour theorem 的先驱 库拉托夫斯基定理的关系 编辑瓦格纳1937年发表了证明 1 库拉托夫斯基以前1930年出版了自己库拉托夫斯基理论 2 根据该定理 当且仅当图的子图的细分不包含那些禁图K5 和 K3 3 瓦格纳定理意味着库拉托夫斯基 所以是更普遍的 3 参考资料 编辑 Wagner K Uber eine Eigenschaft der ebenen Komplexe Math Ann 1937 114 570 590 doi 10 1007 BF01594196 Kuratowski Kazimierz Sur le probleme des courbes gauches en topologie PDF Fund Math 1930 15 271 283 2019 04 25 原始内容 PDF 存档于2018 07 23 法语 Bondy J A Murty U S R Graph Theory Graduate Texts in Mathematics 244 Springer 269 2008 ISBN 9781846289699 取自 https zh wikipedia org w index php title 瓦格纳定理 amp oldid 77010561, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。