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 es correcta sobre «Gráfico lineal»?
Nota: esta pregunta es de selección múltiple (MSQ).
(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: (A) (C)
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 .
Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior
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