Red de conocimiento informático - Material del sitio web - ¿En qué condiciones el grafo completo no dirigido kn es un diagrama de Euler?

¿En qué condiciones el grafo completo no dirigido kn es un diagrama de Euler?

El número de aristas del grafo completo no dirigido Kn con n nodos es (n * (n-1)/2), y las condiciones necesarias y suficientes del diagrama de Euler son (como máximo dos grados impares). 5 nodos).

Los vértices son n, cada punto se puede conectar a otros n-1 puntos, totalizando n*(n-1), pero cada línea se calcula dos veces (por ejemplo, de A a B frente a B igual ) a A), luego divida por 2, que es n*(n-1)/2.

Los circuitos eulerianos requieren que todos los vértices tengan grados pares, es decir, que haya entradas y salidas. Las trayectorias de Euler no son ciclos y los puntos inicial y final pueden no ser consistentes, por lo que para el punto inicial, el grado de salida es 1 mayor que el grado de entrada, y lo contrario es cierto para el punto final. En cuanto a otros vértices, todos los vértices son nodos intermedios y deben tener entradas y salidas. Un gráfico no dirigido es de grado par y el grado de entrada de un gráfico dirigido es igual a su grado de salida.

Información ampliada:

1. Representación de aristas no dirigidas

Las aristas en un gráfico no dirigido son pares de vértices desordenados, y los pares desordenados generalmente se expresan entre paréntesis. expresar.

[Ejemplo] Los pares desordenados (vi, vj) y (vj, vi) representan la misma arista.

2. Representación de grafos no dirigidos

[Ejemplo] G2 en (b) y G3 en (c) son grafos no dirigidos, y sus conjuntos de vértices y conjuntos de aristas son:

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

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