作业帮 > 综合 > 作业

1.设n阶m条边的平面图是自对偶图,则m=2n-2

来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:综合作业 时间:2024/04/30 08:45:01
1.设n阶m条边的平面图是自对偶图,则m=2n-2
2.举出一个既是极大平面图又是自对偶图的例子.
1.设n阶m条边的平面图是自对偶图,则m=2n-2
证明设平面图G=<V,E,F>,其对偶图为图G*=<V*,E*,F*>,从对偶图的定义可知对偶图G*的结点个数等于图G的面数r,即
∣V*∣=∣F∣
因为图G是自对偶的,故
n=∣V∣=∣V*∣=∣F∣=r
代入Euler公式n-m+r=2得m=2n-2. 
解图是极大平面图当且仅当每个面是3度的,此时m=3n-6,由图是自对偶图m=2n-2,故2n-2=3n-6,n=4,极大平面图又是自对偶图只能是4阶完全图,看图: