← Volver a los ejercicios

Puntos de articulación y puentes

Las dos definiciones se comprueban igual: se quita la pieza, se cuentan los componentes y se compara con los que había. Aquí cada vértice y cada arista traen un botón que la quita del dibujo y vuelve a colorear lo que queda, para que la respuesta se vea antes de escribirla.

1. El grafo

Grafo:

¿Cuántos puntos de articulación tiene?

2. Marque las piezas que sostienen la conexión

Entrada: un grafo no dirigido conexo.  Salida: los vértices cuya remoción aumenta el número de componentes, y las aristas cuya remoción hace lo mismo.

Puntos de articulación

Puentes

3. Cómo se relacionan los dos conceptos

Mire el primer grafo y decida cuál de estas afirmaciones se sostiene.

4. Para llevarse

Sin solución aquí. En el primer grafo, agregue una sola arista que deje el grafo sin ningún puente y diga cuáles puntos de articulación sobreviven. Después conteste, con el árbol del tercer grafo a la vista: en un árbol de n vértices, ¿cuántos puentes hay y cuáles vértices son puntos de articulación?