目录
17.1 平面图的基本概念
17.2 欧拉公式
17.3 平面图的判断
17.4 平面图的对偶图
17.1 平面图的基本概念
定义17.1 如果能将无向图G画在平面上使得除顶点外处处无边相交，则称G为可平面图，简称为平面图。画出的无边相交的图称为G的平面嵌入。无平面嵌入的图称为非平面图。
定理17.1 平面图的子图都是平面图，非平面图的母图都是非平面图。
定理17.2 设G为平面图，则在G中加平行边或环后所得的图还是平面图。
定义17.2 给定平面图G的平面嵌入，G的边将平面划分为若干个区域，每个区域都称作G的一个面，其中有一个面的面积无限，称作无限面或外部面，其余面的面的面积有限，称作有限面或内部面。包围每个面的所有边组成的回路组称作该面的边界，边界的长度称作该面的次数。
定理17.3 平面图所有面的次数之和等于边数的两倍。
定义17.3 设G为简单平面图，若在G的任意两个不相邻的两个顶点之间加一条边，所得图为非平面图，则称G为极大平面图。
定理17.4 极大平面图是连通的，并且当阶数大于等于3时没有割点个桥。
定理17.5 设G是 n（n≥3）阶简单连通的平面图，G为平面极大图当且仅当G的每个面的次数均为3。
定义17.4 若在非平面图G中任意删除一条边，所得的图为平面图，则称G为极小平面图。
和 都是极小非平面图。
17.2 欧拉公式
定理17.6（欧拉公式） 设连通平面图G的顶点数、边数和面数分别为n，m和r，则有
n - m + r = 2
定理17.7（欧拉公式的推广） 对于由k（k≥2）个连通分支的平面图G，有
n - m + r = k + 1
其中n，m，r分别为G的顶点数、边数和面数。
定理17.8 设G是连通的平面图，且每个面的次数至少为l（l≥3），则G的边数m与顶点数n有如下关系：
定理17.9 设平面图G有k（k≥2）个连通分支，各面的次数至少为l（l≥3），则边数m与顶点数n有如下关系：
定理17.10 设G是n（n≥3）阶m条边的极大平面图，则m = 3n - 6。
定理17.11 设G是简单平面图，则G的最小度 。
17.3 平面图的判断
定义17.5 设 e = （u ，v）为图G的一条边，在G中删除e，增加新的顶点w，使u，v均与w相邻，称作在G中插入2度顶点w。设w在G中的一个2度顶点，w与u，v相邻，删除w，增加新边（u，v），称作在G中消去2度顶点w。
若两个图 和 同构，或通过反复插入、消去2度顶点后同构，则称 与 同胚。
定理17.12（Kuratowski定理1） 图 G 是平面图当且仅当 G 中既不含与 同胚的子图，也不含与 同胚的子图。
定理17.13 （Kuratowski定理2） 图 G 是平面图当且仅当G中既没有可以收缩到 的子图，也没有可以收缩到 同胚的子图。
17.4 平面图的对偶图
定义17.6 设G是一个平面图的平面嵌入，构造图如下：在G的每一个面中放置一个顶点。设 e 为 G 的一条边，若 e 在 G 的面 与 的公共边界上，则作边 与 e 相交，且不与其他任何边相交。若 e 为 G 中的桥且在面 的边界上，则作以 为端点的环 。称作 为 G 的对偶图。
定理17.14 设平面图G是连通的， 是G的对偶图，，， 和 n，m，r 分别为 和G的顶点数、边数和面数，则
（1） = r
（2） = m
（3） = n
（4）设 的顶点 位于G的面 中，则
定理17.15 设平面图G有k（k≥1）个连通分支， 是G的对偶图， ，， 和 n，m，r 分别为 和G的顶点数、边数和面数，则
（1） = r
（2） = m
（3） = n
（4）设 位于G的面 中，则
定义17.17 设 是平面图G的对偶图，若 G，则称G为自对偶图。
在 n-1(n≥4)边形内放置一个顶点，连接这个顶点与 上的所有顶点。所得的 n 阶简单图称作 n 阶轮图，记作。n 为奇数的轮图称作奇阶轮图，n为偶数的轮图称作偶阶轮图。图17.10(c)中，实边图为 5阶轮图 。可以证明轮图都是自对偶图。文章来源：https://www.toymoban.com/news/detail-446174.html
本文由作者参考《离散数学（第2版）屈婉玲 著》 整理而成，仅用于期末考试复习用。文章来源地址https://www.toymoban.com/news/detail-446174.html
到了这里，关于离散数学复习---第十七章 平面图【概念版】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
