El siguiente gráfico simple no dirigido se conoce como el gráfico de Peterson
¿Cuál de las siguientes afirmaciones es/son VERDADERAS?
(A)
El número cromático de la gráfica es 3
(B)
El gráfico tiene un camino hamiltoniano.
(C)
El siguiente gráfico es isomorfo al gráfico de Peterson.
(D)
El tamaño del conjunto independiente más grande del gráfico dado es 3. (Un subconjunto de vértices de un gráfico forma un conjunto independiente si no hay dos vértices del subconjunto adyacentes).
Respuesta: (A) (B) (C)
Explicación:
Opción A: Al hablar del gráfico de Petersen 
, para ver que el color cromático del gráfico de Petersen es efectivamente 3. Recuerda que, para algún ciclo de n vértices, 
Claramente, el gráfico de Petersen tiene un ciclo impar, por lo que 
. de aquí en adelante solo se necesita intentar un 3-coloreado.
Opción B: Cierto, porque el gráfico de Petersen tiene un camino hamiltoniano pero no un ciclo hamiltoniano.
Opción C: Cierto, puedes decir que los gráficos dados son isomorfos si tienen:
- Igual número de vértices.
- Igual número de aristas.
- Misma secuencia de grados
- Mismo número de circuito de longitud particular
En la mayoría de los gráficos, basta con comprobar las tres primeras condiciones.
Opción D: Falso: Es 4.
Un conjunto de vértices I se denomina conjunto independiente si no hay dos vértices en el conjunto I que sean adyacentes entre sí o, en otras palabras, el conjunto de vértices no adyacentes se denomina conjunto independiente.
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