n个节点的无向完全图Kn的边数为(n *(n-1)/ 2),并且欧拉图的充要条件是(至多两个奇数度为5的节点)。
顶点为n,每个点可以连接到其他n-1个点,总计n *(n-1),但是每条线计算两次(例如,从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)}