[原创]多阶曲面上图的对偶图

雷明85639720

[watermark]

多阶曲面上图的对偶图
雷  明
（二○一二年七月二十五日）
在平面（球面）图中有图的线图、全图和平面图的对偶图等图值函数，在多阶曲面上的图也就应该有相应的线图、全图和对偶图。对于线图和全图来说，其密度都与原图的最大度有关，且原图的最大度可能是无穷的，其线图和全图一定也是可以嵌入到任何亏格曲面上的图。对于对偶图来说，它只是与面与面的相邻关系有关，平面图的对偶图仍然是平面图，二者的亏格是相同的。现在要问，多阶曲面上的图的对偶图的亏格是不是仍然与其原图的亏格也相同呢。
1、亏格为0的平面图的对偶图

我们先看看平面图中的四个完全图K1、K2、K3和K4的对偶图（如图1），可以看出平面图的对偶图仍是平面图。
2、亏格为1的非平面图的对偶图
再看看嵌入亏格为1的环面上的图K3,3、K5、K6和K7的对偶图（如图2），可以看出他们的对偶图仍是非平面图，亏格还是1,没有变化（图2 的a、b、c、d，e、f、g、h和i、j、k、l分别是K3,3、K5、K6和K7原图在环面上嵌入的展开图、对偶图的平面画法和对偶图在环面上嵌入的展开图）。

3、通过以上两图可以看出，亏格为0的平面图的对偶图仍是亏格为0的平面图，亏格为1 的非平面图的对偶图也仍是亏格为1的非平面图。且有v对偶＝f原图，f对偶＝v原图和e对偶＝e原图的关系。现在我们要问，是不是任何亏格的图的对偶图的亏格仍与原图的亏格相同呢。如何进行证明呢。
4、分析
㈠  对图1进行分析：
①　K4的密度是4，是嵌入亏格为0的平面（球面）中图的最大密度。K4的顶点数是v＝4，面数是f＝4，边数是e＝（4×3）/ 2＝6，正好等于3v－6＝3×4－6＝6，这是密度为4的K4图可嵌入亏格为0的曲面(球面，平面)的最大边数。K4的对偶图的顶点数v对偶＝f原图＝4，其对偶图也是一个K4图，边数仍是e对偶＝e原图＝6，不大于可嵌入亏格为0的曲面（球面，平面）的最大完全图K4的边数6，一定是可以嵌入到平面（球面）上去的。
②　K3的密度是3，v＝3，f＝2，e＝3，其对偶图的顶点数是v对偶＝f原图＝2，对偶图是一个3—重的K2图，有3条边，即e对偶＝e原图＝3，小于可嵌入亏格为0的曲面（球面，平面）的最大完全图K4的边数6，也一定是可以嵌入到平面（球面）上去的。
③　K2、K1的对偶图更是能嵌入到平面（球面）上去的。
㈡　对图2 的分析：
①  K7的密度是7，是嵌入亏格为1的曲面中图的最大密度。其v＝7，e＝（7×6）/ 2＝21，也正好等于3v－6＝3×7＝21，这就是密度为7的K7图可嵌入亏格为1的轮胎面（环面）的最大边数。用欧拉公式v＋f＝e＋2（1－n）求其嵌入亏格为1 的曲面中的面数f＝21－7＝14，K7对偶图的顶点数v对偶＝f原图＝14，其对偶图的边数仍是e对偶＝e原图＝21，不大于可嵌入亏格为1的轮胎面（环面）的最大完全图K7的边数21，一定是可以嵌入到轮胎面（环面）上去的。
②  K6的密度是6，v＝6，e＝（6×5）/ 2＝15，用欧拉公式求其嵌入亏格为1 的曲面中的面数f＝15－6＝9，其对偶图的顶点数是v对偶＝f原图＝9，对偶图仍有15条边，即e对偶＝e原图＝15，小于可嵌入亏格为1的轮胎面（环面）的最大完全图K7的边数21，也一定是可以嵌入到轮胎面（环面）上去的。
③　K5的密度是5，v＝5，e＝（5×4）/ 2＝10，用欧拉公式求其嵌入亏格为1 的曲面中的面数f＝10－5＝5，其对偶图的顶点数是v对偶＝f原图＝5，对偶图仍有10条边，即e对偶＝e原图＝10，也小于可嵌入亏格为1的轮胎面（环面）的最大完全图K7的边数21，也一定是可以嵌入到轮胎面（环面）上去的。
④  K3,3图的密度是2，v＝6，e＝9，用欧拉公式求其嵌入亏格为1 的曲面中的面数f＝9－6＝3，其对偶图的顶点数是v对偶＝f原图＝3，对偶图仍有9条边，即e对偶＝e原图＝9，也小于可嵌入亏格为1的轮胎面（环面）的最大完全图K7的边数21，也一定是可以嵌入到轮胎面（环面）上去的。
5、证明
亏格大于等于2 的曲面，用赫渥特多阶曲面上的地图着色公式计算出完全图的顶点数之差最多是1，多数情况下还是0。它不象亏格为1 的曲面可嵌入的完全图的顶点数小于等于7与亏格为0的曲面可嵌入的完全图的顶点数小于等于4之差等于3（大于1），中间有K5、K6和K7三种完全图的情况,而只有一种完全图，或都是两种亏格曲面可嵌入的最大完全图是相同的。如亏格为2 的曲面可嵌入的完全图的顶点数小于等于8，与亏格为1 的曲面可嵌入的完全图的顶点数小于等于7之差就是1，就只有K8一种完全图；又如亏格为7 和6 的曲面可嵌入的完全图的顶点数之差就是0，两种曲面可嵌入的最大完全图都是K12，且这样的情况随曲面亏格的增大，是越来越多的。现在就采用以上对具体图分析的方法来对一般情况进行证明。
可以说，曲面的亏格大于等于2时，曲面的亏格向上增大1,可嵌入其中的最大完全图的顶点数最多只能增加1个，有时曲面的亏格尽管增大了，但可嵌入其中的最大完全图的顶点数却并不增加，而且这种情况也随曲面亏格的增大，也越来越多。在顶点数大于等于8的完全图中，既是完全图又是极大图的完全图更是少得可怜，所以说在这些完全图中，绝大多数完全图的边数是小于该完全图所能嵌入的曲面所能嵌入的图的最大边数的。这就是说，完全图Kv的边数v（v－1）/ 2一定是小于等于完全图Kv所能嵌入的曲面所能嵌入的图的最大边数3v＋6（n－1）的，即有v（v－1）/ 2≤3v＋6（n－1），完全图Kv的对偶图的边数又等于原完全图Kv的边数v（v－1）/ 2，所以该完全图Kv的对偶图的边数也就永远不会大于该曲面所能嵌入的最大完全图Kv的边数。
图的边数不会大于曲面所能嵌入的最大完全图的边数，该图也就一定能够嵌入到该曲面中去。
这就证明了嵌入亏格大于等于2的曲面上的图的对偶图也是同亏格的图，也一定能嵌入到该亏格的曲面上。
6、结论
亏格是0的平面图能嵌入到亏格是0的曲面（球面，平面）上，亏格是1的图能嵌入到亏格是1 的曲面（环面，轮胎面）上，亏格大于等于2的图能嵌入到与其亏格相同的曲面（多阶曲面）上。总括起来就可得到任何亏格曲面上的图的对偶图都可嵌入到与其亏格相同的曲面上，且对偶图与原图的亏格是相同的。

雷  明
二○一二年七月二十五日于长安

APB先生

下面引用由雷明85639720在 2012/07/27 10:11pm 发表的内容：
(水印部分不能引用)
-=-=-=-=- 以下内容由 雷明85639720 在  时添加 -=-=-=-=-
多阶曲面上图的对偶图
雷  明
...

雷明85639720

我是在学习、探索、研究多阶曲面上的图的对偶图与原图的亏格是否相同的问题呢，与你们的回复贴是没有什么关系的。雷明

APB先生

[这个贴子最后由APB先生在 2012/07/29 07:28am 第 2 次编辑]


楼主曾说过俺的点线化是已有的对偶图； 点线化=对偶图 ？
以下是楼主的图

雷明85639720

我的图不对吗，那不就是平面图的对偶图吗。你的点化线的实质不就是这个吗。但我这里只是谈的是对偶图，并没有谈及着色的问题呀。雷明

APB先生

在点线化中，一个点代表一个闭区域，一条线连接二个点代表这二个点相邻，也即代表二个闭区域相邻，有共同的分界线。

雷明85639720

APB先生，我不知你说的这些问题与我这里的多阶曲面上图的对偶图有什么关系。

APB先生

下面引用由雷明85639720在 2012/07/29 09:55pm 发表的内容：
APB先生，我不知你说的这些问题与我这里的多阶曲面上图的对偶图有什么关系。

雷明网友：你的对偶图，一个点的对偶图还是一个点；二点一线的对偶图是一点一线；三点三线的对偶图是二点三线；四点六线的对偶图还是四点六线；……。按照你的“二点一线的对偶图是一点一线”的逻辑，四点六线的对偶图还是四点六线还对吗？是不是要变成二点六线了。抱歉，我不懂你的对偶原则。
我的点线化与你的对偶图没有什么关系。

雷明85639720

先生，请你先好好的学习一下图论里的关于对偶图的定义，再来看一看我画的K1图、K2图、K3图、K4图的对偶图画得对不对。我还要说一遍，我这里谈的是多阶曲面上图的对偶图的问题，不是在谈着色的问题，请你不要西拉东扯了。雷明