El gráfico lineal L(G) de un gráfico simple G se define como sigue:
- Hay exactamente un vértice v(e) en L(G) para cada arista e en G.
- Para dos aristas cualesquiera e y e’ en G, L(G) tiene una arista entre v(e) y v(e’), si y sólo si e y e’ son incidentes con el mismo vértice en G.
¿Cuál de las siguientes opciones no es correcta sobre «Gráfico de líneas»?
(A) Un gráfico lineal tiene un punto de articulación si y solo si el gráfico subyacente tiene un puente para el cual ninguno de los extremos tiene grado uno
(B) Para un gráfico G con n vértices y m aristas, el número de vértices del gráfico lineal L (G) es m, y el número de aristas de L(G) es la mitad de la suma de los cuadrados de los grados de los vértices en G, m.
(C) Si un gráfico G tiene un ciclo de Euler, es decir, si G es conexo y tiene un número par de aristas en cada vértice, entonces el gráfico lineal de G es hamiltoniano.
(D) Ninguna de estas
Respuesta: (B)
Explicación:Para un gráfico G con n vértices y m aristas, el número de vértices del gráfico lineal L(G) es m, y el número de aristas de L(G) es la mitad de la suma de los cuadrados de los grados de los vértices en G, menos m.
La opción (B) es falsa.
Ver propiedades del gráfico de líneas .
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA