Ejercicio · ZW-GRAFO-BIPARTITO-003 · ★☆☆ Básico
¿Cuál es el máximo número de aristas de un grafo bipartito con 6 vértices?
Elige una opción.
Ver respuesta
- A. 9
Explicación
Con partes de tamaños \(a\) y \(6-a\) caben \(a(6-a)\) aristas, máximo en \(a=3\): \(3\cdot3=9\). Las 15 aristas de \(K_6\) incluirían triángulos.
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-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-006 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…
- 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…