平面图对偶图的相关研究论文

1.若图G=(V, E)存在着一种图形表示，使得将它画在平面上后没有两个结点重合，每条边不自身相交且没有两条边在它们公共关联的结点以外相交，则称G是具有平面性的图，或简称为平面图。 2.若图G是平面图，则G的任何子图都是平面图。 3.若图G是非平面图，则G的任何母图也都是非平面图。 4.Kn (n ≥ 5)和K3,n(n≥3)都是非平面图 5.面；边界；度；外部面 6.面度之和等于边数m的2倍，即 1.设G是一个面数为f的(n, m)连通平面图，则                                     n - m + f = 2 2.对于具有k（ k≥2）个连通分支的平面图G，有                                     n - m + f = k + 1 3.设G是一个阶数大于2的(n, m)连通简单平面图，则                                     m ≤ 3n - 6 4.在任何简单连通平面图中，至少存在一个其度不超过5的结点 5.围长：图包含的最短圈的长度 6.设G是一围长 g大于2的(n, m)连通平面图，则                                  7. 和 都是非平面图 1.Kuratowski定理：一个图是平面图，当且仅当它不包含与 和 的细分图同构子图。 1.对偶图；存在着对偶图是一个图为平面图的充分必要条件 2.对于G和 存在 ,在面内的顶点的点度等于面的面度(f为面数) 3.若对偶图与本身同构，则称对偶图为自对偶图。 1.着色：使无环图相邻结点有不同的颜色 2.若G是k可着色的，但不是(k - 1)可着色的，就称G为k色图，k称为色数，记为 。 3. 当且仅当G是零图。 4. 5.设G中至少含一条边，则 ,当且仅当G为二部图。 6.对于任何的图G，均有 7.面着色， 8.地图G是k面可着色的，当且仅当它的对偶图 是k可着色的。 9.任何连通平面图都是可以5着色的。