== include(page="template/taskheader" task_id="gbc") ==

Fie {$G = (V, E)$} un graf neorientat cu $V$ multimea varfurilor, iar $E$ multimea muchiilor. Definim un subgraf bipartit complet bun al lui $G$ un graf {$G' = (V', E')$} cu proprietatile urmatoare:

Fie {$G = (V, E)$} un graf neorientat cu $V$ multimea varfurilor, iar $E$ multimea muchiilor. Vrem sa alegem doua multimi{$A,B ⊆ V$} astfel incat

* {$V' = A U B$}
* {$V' ⊆ V$}
* {$E' = { (i,j) | i ∈ A, j ∈ B }$} ( toate muchiile cu un capat in A si celalalt capat in B )
* {$E' ⊆ E$}

* {$|A| = n$}
* {$|B| = m$}

* {$A ⋂ B = Φ$} ({$A$} si $B$ sunt disjuncte)
* {$∀ i ∈ A, j ∈ B$}, muchia {$(i j) ∈ E$} (exista muchie intre orice nod al lui $A$ si orice nod al lui {$B$})

h2. Cerinta