Teoría de Grafos

¿Cuál es la definición de un conjunto independiente en un grafo?

• Un conjunto independiente en un grafo es un conjunto de vértices que no tienen aristas conectándolos entre sí.

• Un conjunto independiente en un grafo es un grupo de vértices conectados por múltiples aristas.

• Un conjunto independiente en un grafo es un conjunto de vértices que tienen todos aristas conectándolos entre si.

• Un conjunto independiente en un grafo es un conjunto de vértices tal que existe un camino entre todo par de vértices.

¿Cuáles son las propiedades de dos grafos isomorfos?

• Mismo número de vértices

• Misma cantidad de caminos de longitud k.

• Mismo número de aristas

• Mismo número de componentes conexas

Explica el concepto de isomorfismo en grafos.

• Dos grafos son isomorfos si tienen diferente cantidad de vértices pero las mismas aristas.

• Un grafo es isomorfo si sus vértices están conectados de forma aleatoria sin seguir un patrón.

• El isomorfismo en grafos se refiere a la simetría de los vértices en lugar de las aristas.

• Dos grafos son isomorfos si existe una biyección entre sus conjuntos de vértices que preserva las aristas entre ellos.

¿Qué es un matching en teoría de grafos?

• Un matching en teoría de grafos es un subconjunto de aristas en un grafo donde ninguna dos aristas comparten un vértice en común.

• Un matching en teoría de grafos es un grafo completo donde todos los vértices están conectados por aristas.

• Un matching en teoría de grafos es un subconjunto de vértices en un grafo que comparten todas sus aristas.

• Un matching en teoría de grafos es un conjunto de vértices que no están conectados por aristas.

¿Qué se entiende por un coloreo válido en grafos?

• Es una asignación de colores a los vértices de un grafo de manera que todos los vértices tengan el mismo color.

• Es una asignación de colores a los vértices de un grafo de manera que todo par de vértices tiene el mismo color.

• Es una asignación de colores a los vértices de un grafo de manera que dos vértices adyacentes no tengan el mismo color.

• Es una asignación de colores a los vértices del grafo tal que todo vértice tiene un color único.

Dado el grafo en la figura.

¿Qué tamaño tiene la clique máxima?

• 2

• 3

• 4

• 5