Ejercicio · ZW-GRAFO-CONEXO-009 · ★★★ Avanzado
Sea \(G\) un grafo conexo y \(e\) una arista que pertenece a un ciclo de \(G\). Al quitar \(e\), el grafo resultante es:
Elige una opción.
Ver respuesta
- B. Siempre conexo
Explicación
Quien usaba \(e\) en un camino puede rodear por el resto del ciclo, que sigue ahí. Por eso seguirá habiendo camino entre cualquier par de vértices.
Repasa el concepto: Grafo conexo
Un grafo \(G=(V,E)\) es conexo si cualesquiera dos vértices \(u,v\in V\) están unidos por un camino.
\[\forall\,u,v\in V\ \ \exists\ \text{camino de } u \text{ a } v\]
Más ejercicios de grafo conexo
- ZW-GRAFO-CONEXO-001 Un grafo tiene vértices 1,2,3,4 y aristas 12, 23, 34. ¿Es conexo?
- ZW-GRAFO-CONEXO-002 Un grafo con vértices 1,dots,5 tiene aristas 12, 23 y 45. ¿Cuántas componentes conexas tiene?
- ZW-GRAFO-CONEXO-003 Un grafo con vértices 1,dots,6 tiene aristas 12, 34 y 56. ¿Cuántas componentes conexas tiene?
- ZW-GRAFO-CONEXO-004 ¿Cuál es el menor número de aristas que puede tener un grafo conexo con 8 vértices?
- ZW-GRAFO-CONEXO-005 ¿Cuál es el máximo número de aristas que puede tener un grafo con 6 vértices que no sea conexo?
- ZW-GRAFO-CONEXO-006 Un grafo con vértices 1,dots,5 tiene aristas 12, 23, 13 y 45. ¿Cuál de estas aristas, agregada, lo…
- ZW-GRAFO-CONEXO-007 Un grafo con 6 vértices tiene 11 aristas. ¿Qué se puede afirmar?
- ZW-GRAFO-CONEXO-008 En el ciclo 1,2,3,4,5,6,1 (aristas 12,23,34,45,56,61) se quitan las aristas 12 y 45. ¿Cuántas compo…