¿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)}