[音乐] 嗨，欢迎回来。
在这儿呢，我们接下来再介绍另外一种特殊的图， 称之为平面图。
那什么是平面图？ 啊，我们看到的一个图的画法有很多种，
实际上我们从这个同构图上就已经发现了，
两个图明明是一样的图，但是呢它的画法呢，可以看起来好像 特别地不一样。
比如说五边形和五角星，啊，这两个呢实际上是同构的图，但是画起来呢其实 完全不一样。
那么而且呢，就是像是五边形或者五角星， 那么就也会引发另外一个问题，就说一个图，
是否能够画成任意两条边都不会相交的那个 样子。
你看像五角星的五个顶点，那么它的这个五条边呢，
都是交错在一起的，但是如果把它做一个同构的变化，
那么它就会变成一个五边形，啊，那么五边形呢，它就，所有的边它不会交错在一起。
也就说，这个边除了在顶点处汇集之外，不会呢交叉在一起。
那所以呢这个问题就在于说，一个图我能 有不同的、
各种各样的画法，那么是否存在一种画法， 能够画成任意的两条边都不会相交的这样子。
那么，如果说， 可以这么做，那么这称之为平面图。
那么，平面图它实际的应用有很多，比如说其中的一个我们比较熟悉的，
就是印刷电路板，啊，我们学过这个物理当中的电子电路都知道，这个
无线电的电子电路的它有一个电原理图，比如说我们这，这个例子里头， 左下角它就是一个电原理图。
那么原理图呢偏向于说， 把这个各个元器件它的这个连接呢，
元器件排列得比较整齐一些， 然后，而且呢为了排列整齐起见，它有的时候这些
这个电子电路，电子元件之间的这个连线呢，它会交错在一起，那么交错在一起，
为了表示它们之间是不会连通的，可能会有一些画法呢，就会画成
像一座桥一样跨过去，那么一个跨，表示它们是不会相交的。
那么如果是相交的话，那么它会特意地 用一个粗的圆点来表示，它们是接在一起的，对吧？
但是如果，这个电原理图是可以这么画，但是如果 你变成了实际的这个产品，变成印刷电路板的时候，
那么显然，你就不可能像纸上画这个线 一样，说我做一个跨过去的，说表示这个不相交。
我们知道，电路板呢，是通过这个铜箔板腐蚀出来的，那么腐蚀了以后，
那么，你如果只要有两根线是交错在一起， 那么它必然会是连通的，啊，除非你
再焊一条飞线啊，从这儿，从一个地方跳过去，那么就脱离了这个二维平面了，进入到第三维
飞过去，对，这个这个术语叫做飞线，那么飞线的存在呢实际上
会大大地降低产品的这个稳定性以及降低它的性能。
所以呢，尽量会避免飞线。
那么所以呢，在从电原理图到这个印刷 电路板，那么实际上呢，就是这个图的平面的
画法，让它不该交错的这个线，它不能够交错在一起。
这是一个印刷电路板这样的应用。
那么当然还有一些其它的应用，比如说在矿山
里边，这个矿洞到、 到仓库，那么可能有很多矿洞，
那么还有呢，比如说有两三个仓库， 那么有一些矿洞都要，要运车、
运煤到这个仓库里去， 那么他们就要布设这个轨道，那么轨道呢怎么布设，让这个轨道之间
不会交错，那么这个也是一个平面图的问题。
那么按照形式化的定义，严格地定义出来，什么是一个平面图呢？
就说如果一个无向图G，它可以在一个平面上图 示出来，并且呢各条边仅仅在顶点处相交的话，
那么就把这种图称作为平面图，否则呢，就是非平面图。
我们注意到呢，有两个最小的非平面图，
一个呢叫做K5，就是5的完全图，5个顶点的完全图，K5。
还有呢一个，另外一个叫K3,3，那么从这个名字
上可以看出来，它是完全二分图，或者叫 对，它是一个完全二分图。
那么，x呢等于3，然后y呢也 等于3，这么一个完全二分图。
那么，它们呢都是正则图， 就是完全图它肯定是一个正则图，那么K3,3呢，也是一个正则图。
而且它们的特点都是最小化，那么在哪个方面最小呢？
都是任意去掉一条边，它就变成了平面图，也就说它的是最小的非平面图。
最小呢，体现在什么？K5是顶点数最小的 非平面图，而且K3,3呢，是边数最少的非平面图。
那么我们来看看这两个图长得什么样子。
啊，上面这个就是K5， K5呢，它是一个，里边是一个五角星，外面是一个五边形。
那么，它是无论如何都画不成这个平面的这个样子，不会说 嗯，两两都不会交错。
但是呢，我们发现，只要去掉一条边，比如说这个蓝色的这条边去掉它，
那么这样呢，我们就可以通过把，有一条，其中的这条边给它挪到外边去，
然后把另外一条，这个绿色的边，再挪到外面来， 变成了这个最右边的这样画法，那么它就是一个平面图了。
对吧？那么下面这一系列呢，是K3,3， K3,3呢是一个二分图，上面有三个顶点，下面有三个顶点，
然后它的这个任意两个顶点之间呢都有连接， 那么它也是一个非平面图。
那么同样的，如果我把 这个蓝色的这条线给它去掉，那么这样呢，我就可以
挪动三根线，红、 绿、
蓝这三根线，给它挪到外，外围来， 那么它也可以成为一个平面图。
所以这是一个K5，一个K3,3，从这两个例子呢，我们可以看到，
第一呢是顶点数最少的非平面图，一个呢是边数最少的非平面图，而且呢，我们也见识到
一个平面图怎么样从边交错，变成了 这个边不交错的这种形式，就画成平面图的那样子。
那么平面图的判定呢，它有一个等价条件， 也并不是特别的难。
那么这是在1930年被发现的，
它说G或者G的子图，在作任何的同胚操作以后，它得到的图，
如果它不会以K5或者K3,3作为子图的话， 那么这个图就是一个平面图。
那什么是同胚操作呢？ 同胚就是说，在原图的边上，
增加或者说删除二度的节点，二度顶点，
那么随意地增加或者删除二度顶点，因为我们知道增加或者删除二度顶点， 它是不影响这个图的平面性质。
比如说下面这个例子， 它原来有四个顶点，这四个顶点当然都是二度的，我们可以任意地去掉两个， 变成中间这样。
那么在这个边上呢，又可以增加上，再增加 3个，变成左边这个。
那么这两个变化都是属于 同胚操作，那么所以呢，这个平面图的这个
判定它的等价条件就是这样。
陈斌副教授
