Question

如何证明小于30条边的平面简单图有一个结点的度数小于等于4

Answer 1

根据题意设无向图中顶点个数为 N，则边数最大为 N*(N-1)/2

假设所有结点的度数都大于4，则总度数>4N

边数=总度数/2 > 2N

N*(N-1)/2 > 2N

N>5

边数> 6*(6-1) =30条

与题目所给矛盾

所以小于30条边的平面简单图有一个结点的度数小于等于4

扩展资料：

在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点。

在C语言中，链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据；二为下一个结点的地址，即指针域和数据域。

数据结构中的每一个数据结点对应于一个储存单元，这种储存单元称为储存结点，也可简称结点。

Answer 2

设无向图中顶点个数为 N,则边数最大为 N*(N-1)/2
假设所有结点的度数都大于4,则总度数>4N
边数=总度数/2 > 2N
N*(N-1)/2 > 2N
N>5
边数> 6*(6-1) =30条
与题目所给矛盾,所以小于30条边的平面简单图有一个结点的度数小于等于4

Answer 3

下面那几个都是copy作业帮的么？连平面简单图条件都不用的

Answer 4

其中Euler公式请参考：百度百科 - 欧拉公式（拓扑学）