Graf bipartit complet

De Viquipèdia
Dreceres ràpides: navegació, cerca

En teoria de grafs un graf bipartit (o bipartit) complet és aquell Graf bipartit en el qual tots els vèrtexs de la partició  V_1 estan connectats a tots els vèrtexs de la partició  V_2 i viceversa.

Definició[modifica | modifica el codi]

Un graf bipartit complet  G: = (V_1 \cup V_2, E) \, és un graf bipartit tal que  \forall v_1 \in V_1, \forall \ v_2 \in V_2 \rightarrow i (v_1, v_2) \in E. \, És a dir, un graf bipartit complet està format per dos conjunts disjunts de vèrtexs i totes les possibles arestes que uneixen aquests vèrtexs.

El graf complet bipartit amb particions de mida  \left|V_1 \right|= m i  \left|V_2 \right|= n, és denotat com  K_{m, n}\, .

Exemples[modifica | modifica el codi]

Vegeu també[modifica | modifica el codi]