三角形平面图的若干性质探讨

作者：徐肇銮; 郭秀山; 杨文荣

来源：河北工业大学学报, 2016, (05): 23-27.

DOI：10.14081/j.cnki.hgdxb.2016.05.004

• 对偶图
• 完备图
• 结合矩阵
• 置换群
• 换位
• 四色定理 dual graph
• complete graph
• adjacency matrix
• permutation group
• commutation
• Four Color Theorem

首先叙述了三角形平面图的顶点、边和面的关系.因为不会存在顶点数大于4的完备图的子图,所以如分成一个个由2个相邻三角形面构成的子图,对比2个三角形面而言,其公共边是唯一的.其次引入其对偶图的边与顶点的关系,并应用了置换群的概念,对顶点做换位运算,可以导出对顶点所连接的3条边可以分别属于3个不相交的集合.因此对偶于原三角形平面图的每个三角形面的3条边,也分别属于3个不相交的边的集合.最后可以得出这样的结论,只用4种颜色来对三角形平面图的顶点正确着色的充要条件是:三角形平面图中,不存在4个顶点以上的完备图的子图.

• 单位
  河北工业大学