Ejercicio · ZW-GRAFO-BIPARTITO-006 · ★★☆ Intermedio
Al ciclo \(C_6\), con vértices \(1,\dots,6\) y aristas \(\{i,i+1\}\) y \(\{6,1\}\), se le agrega una arista. ¿Cuál hace que deje de ser bipartito?
Elige una opción.
Ver respuesta
- D. \(\{1,3\}\)
Explicación
Con \(A=\{1,3,5\}\) y \(B=\{2,4,6\}\), las aristas \(\{1,4\}\), \(\{2,5\}\) y \(\{3,6\}\) unen partes distintas. En cambio \(\{1,3\}\) cierra el triángulo \(1,2,3\).
Repasa el concepto: Grafo bipartito
Un grafo bipartito es un grafo \(G=(V,E)\) cuyos vértices se reparten en dos conjuntos disjuntos \(A\) y \(B\) de modo que cada arista \(e\in E\) une un vértice de \(A\) con uno de \(B\).
\[V=A\cup B,\quad A\cap B=\varnothing,\quad |e\cap A|=1\ \text{ para toda } e\in E\]
Más ejercicios de grafo bipartito
- ZW-GRAFO-BIPARTITO-001 ¿Cuál de los siguientes grafos es bipartito?
- ZW-GRAFO-BIPARTITO-002 ¿Cuántas aristas tiene el grafo bipartito completo K_2,5, donde cada vértice de una parte se une co…
- ZW-GRAFO-BIPARTITO-003 ¿Cuál es el máximo número de aristas de un grafo bipartito con 6 vértices?
- ZW-GRAFO-BIPARTITO-004 ¿Cuál de estas condiciones garantiza que un grafo NO es bipartito?
- ZW-GRAFO-BIPARTITO-005 Un grafo tiene vértices 1,dots,6 y aristas \1,4\,\1,5\,\2,4\,\2,6\,\3,5\,\3,6\. ¿Cuál es una partic…
- ZW-GRAFO-BIPARTITO-007 En un grafo bipartito, los 4 vértices de la parte A tienen grado 3 y los 6 vértices de B tienen tod…
- ZW-GRAFO-BIPARTITO-008 Un grafo bipartito conexo tiene partes de 3 y 5 vértices. ¿Cuál es el mínimo número de aristas que…
- ZW-GRAFO-BIPARTITO-009 Un grafo con 7 vértices tiene tres componentes conexas: dos aristas aisladas y un camino de 3 vérti…