Dado un grafo no dirigido GG , G′G′ se crea un gráfico, para cada arista en G se asigna un nodo en G′ si dos aristas en G tienen un nodo común añadimos una arista entre sus nodos en G′ .
Necesito determinar si G tiene un ciclo de Euler significa que G′ también tendrá uno, y viceversa si G′ tiene un ciclo de Euler significa que G ¿debe tener uno?
Intenté resolver el problema mediante ensayo y error, pero eso no me llevó muy lejos.
Si tiene alguna idea, por favor compártala.
El gráfico completo en cuatro puntos no tiene ningún ciclo de Euler (porque todos sus vértices tienen grado impar), pero en su gráfico de líneas (el G′ que definiste) cada nodo tiene grado cuatro, por lo que hay un ciclo de Euler.
Por otro lado, la implicación inversa es correcta. Si cada vértice de G tiene grado par, entonces también lo tienen todos los vértices de G′ . Más detalladamente, el vértice de G′ correspondiente a una arista {u,v} de G tiene grado (en G′ ) igual a la suma de los grados (en G ) de u y v menos 2 .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
