n个结点的无向完全图Kn的边数为（） ，欧拉图的充要条件是（）

Question

如题所述

Answer 1

n个结点的无向完全图Kn的边数为（n*(n-1)/2） ，欧拉图的充要条件是（最多两个奇数度的节点）。

顶点为n，每个点可与其它n-1个点相连，共有n*(n-1)，但是每条线均被计算了2次(比如从A到B和从B连到A是一样的)，再除以2，即n*(n-1)/2。

欧拉回路要求所有顶点都是偶数的度，也就是有进就有出。欧拉路径，不是回路，起点终点可以不重合，所以对于起点来说，出度比入度大1，而终点反之。至于其他的顶点，全部是中间节点，有入必有出。无向图为偶数度，有向图入度等于出度。

扩展资料

（1）无向边的表示

无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

【例】无序对(vi，vj)和(vj，vi)表示同一条边。

（2）无向图的表示

【例】下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为：

V(G2)={v1，v2，v3，v4}

E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}

V(G3)={v1，v2，v3，v4，v5，v6，v7}

E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}

参考资料：百度百科 - 无向完全图

Answer 2

每个节点有边去另外n-1个节点。所以n节点无向完全图共有边n*(n-1)/2条。欧拉图冲要条件，最多两个奇数度的节点。追问

充要条件能解释一下吗

追答

欧拉回路要求所有顶点都是偶数的度，也就是有进就有出。
欧拉路径，不是回路，起点终点可以不重合，所以对于起点来说，出度比入度大1，而终点反之。至于其他的顶点，全部是中间节点，有入必有出。无向图为偶数度，有向图入度等于出度。

本回答被提问者和网友采纳