平面图的图论

2026年09月21日 19:19

有2个网友回答

网友（1）：

在图论中，平面图是可以画在平面上并且使得不同的边可以互不交叠的图。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图K5 和完全二分图K3,3 是最“小”的非平面图。
离散数学【平面图】
*|欧拉公式：
1个联通分支：
顶点数 - 边数 + 面数 = 1 + 1　　推广到n个联通分支：　　顶点数 - 边数 + 面数 = 联通分支数 + 1　　*|握手定理对偶　　平面图所有面的次数和 = 2 x 边数完全图K5（五角星）和完全二分图K3,3 是【极小非平面图】.
　　【极大平面图】是【连通】的，并且阶数n≥3时，没有割点和桥　　设G是n（n≥3）阶【简单连通】的平面图，G为【极大平面图】<=>G的每个面的次数均为3.　　一个连通分支：　　设G是连通的平面图，且每个面的次数至少为l (l≥3)，则G的边数m与顶点数n有
m≤l*(n-2)/(l-1-1)　　推广到k个连通分支：　　m≤l *(n-k-1)/(l-2)(边数≤最小次数*(点数-连通分支数-1)/(最小次数-2))　　设G是n(≥3)阶m条边的【简单平面图】，则 m≤3n-6 (边数≤3x点数-6)　　设G是n(≥3)阶m条边的【极大平面图】，则m=3n-6 (边数=3x点数-6)　　设G是【简单平面图】，则G的最小度δ≤5
库拉托夫斯基定理
波兰数学家卡齐米日·库拉托夫斯基提出的一类禁忌准则（指满足某种条件的图就一定无法具有某个性质）中，也包括了平面图的情况。他提出的一个定理说明：
一个有限图（顶点数和边数有限的图）是平面图当且仅当它并不包含一个是（有五个顶点的完全图）或（三个顶点的二部图）的分割的子图。
其中，一个图A是另一个图B的分割是指：A是在B的基础上，在某些边的中间加上顶点

而得到的新的图。用图的同胚理论来说，就是：一个有限图是平面图当且仅当这个图不包含任何同胚于或的子图。
这个定理的一般化是罗伯森－西摩定理。
欧拉公式
一个平面图将平面分成若干个互不相通的封闭区域，以及图的外部的区域。其中，图的外面的区域称为图的外部面，而图里面每个被顶点和边分割出来的封闭并连通的区域称为图的内部面。围成每个面图的每个面至少对应着三条边。
平面图的顶点个数、边数和面的个数之间有一个以大数学家莱昂哈德·欧拉命名的公式：
V-E+F=C+1
其中，V是顶点的数目，E是边的数目，F是面的数目，C是组成图形的连通部分的数目。当图是单连通图的时候，公式简化为：
V-E+F=2

网友（2）：