Tarjetas de Fundamentos de Matemáticas Discretas
Fundamentos de Matemáticas Discretas: Guía Completa para Estudiantes
Toca para girar · Desliza para navegar
Grafos y árboles
282 tarjetas
Tarjeta 1
Pregunta: ¿Qué es un árbol maximal de un grafo G = (N,S)?
Respuesta: Es un subgrafo de G que es un árbol e incluye todos los nodos de N; conecta todos los nodos con la mínima cantidad de aristas posible.
Tarjeta 2
Pregunta: ¿Qué es un árbol maximal minimal en un grafo rotulado G = (N,S,p) con pesos p:S→R?
Respuesta: Es un árbol maximal cuyas aristas suman el menor peso posible: conecta todos los nodos minimizando el peso total.
Tarjeta 3
Pregunta: Según los teoremas, ¿qué propiedad de caminos tiene un árbol A = (N,S)?
Respuesta: Existe un único sendero entre cualquier par de nodos.
Tarjeta 4
Pregunta: En un árbol A = (N,S), ¿cómo se relacionan el número de nodos |N| y el número de aristas |S|?
Respuesta: Se cumple |N| = |S| + 1.
Tarjeta 5
Pregunta: ¿Qué dice el teorema sobre vértices colgantes si |S| > 0 en un árbol?
Respuesta: Si |S| > 0 entonces el árbol tendrá al menos dos vértices colgantes.
Tarjeta 6
Pregunta: Si |S| > 0 en un árbol A, ¿qué propiedades adicionales se cumplen?
Respuesta: 1) Existe una trayectoria entre cualquier par de nodos. 2) A es conexo, pero si se quita una arista deja de serlo. 3) A no tiene ciclos, pero si se ag
Tarjeta 7
Pregunta: ¿Es un árbol un grafo plano según el contenido?
Respuesta: Sí: el árbol A es un grafo plano.
Tarjeta 8
Pregunta: En un árbol, ¿qué puede decirse sobre cada nodo respecto a colgante o punto de corte?
Respuesta: Cada nodo o es colgante o es un punto de corte.
Tarjeta 9
Pregunta: ¿Cómo se obtiene un árbol maximal minimal de un grafo pesado G según el método descrito?
Respuesta: Quitando las aristas de mayor peso posible mientras se mantiene el grafo conexo, hasta obtener un árbol que conecte todos los nodos con peso mínimo.
Tarjeta 10
Pregunta: Define un árbol con raíz según el material.
Respuesta: Es un grafo dirigido acíclico conexo con un único nodo raíz R desde el cual existe un camino dirigido hacia cualquier otro nodo del árbol.