Grafic bipartit complet

În teoria graficelor , un grafic bipartit complet este definit ca un grafic bipartit $\,G=\langle (V_{1};V_{2}),E\rangle$ ${\ displaystyle \, G = \ langle (V_ {1}; V_ {2}), E \ rangle}$ ${\ displaystyle \, G = \ langle (V_ {1}; V_ {2}), E \ rangle}$ , cu $V_{1}$ ${\ displaystyle V_ {1}}$ $V_ {1}$ Și $V_{2}$ ${\ displaystyle V_ {2}}$ ${\ displaystyle V_ {2}}$ pentru a indica subseturile nodurilor, astfel încât:

$\forall \;(v_{i},v_{j}):[(v_{i}\in V_{1})\land (v_{j}\in V_{2})]\;\exists \;\{v_{i};v_{j}\}$ ${\ displaystyle \ forall \; (v_ {i}, v_ {j}): [(v_ {i} \ in V_ {1}) \ land (v_ {j} \ in V_ {2})] \; \ există \; \ {v_ {i}; v_ {j} \}}$ ${\ displaystyle \ forall \; (v_ {i}, v_ {j}): [(v_ {i} \ in V_ {1}) \ land (v_ {j} \ in V_ {2})] \; \ există \; \ {v_ {i}; v_ {j} \}}$

Prin urmare, este un grafic bipartit în care există toate arcele care leagă elementele unui set de cele ale celuilalt sau, așa cum se spune în definiție, pentru fiecare pereche de vârfuri din care primul din set $V_{1}$ ${\ displaystyle V_ {1}}$ $V_ {1}$ iar al doilea în ansamblu $V_{2}$ ${\ displaystyle V_ {2}}$ ${\ displaystyle V_ {2}}$ există un arc care începe în primul și se termină în al doilea.

Acest tip de grafic este utilizat în unele algoritmi, în special în soluționarea problemelor de atribuire .

Exemple

Graficele stelelor S ₃ , S ₄ , S ₅ și S ₆ .

Graficul serviciilor K _3.3

Pentru fiecare k , K _{1, k} se numește stea . Toate graficele bipartite complete care sunt copaci sunt stele.
Graficul K _1,3 se numește gheară .
Graficul K _3,3 se numește graficul serviciilor .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe un grafic bipartit complet

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică