Grafic bipartit

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 4 octombrie 2020; verificările necesită 12 modificări .

Un graf bipartit sau bigraf în teoria grafurilor este un graf al cărui set de vârfuri poate fi împărțit în două părți, astfel încât fiecare margine a graficului să conecteze un vârf dintr-o parte cu un vârf al celeilalte părți, adică există fără muchii între vârfurile acelorași părți ale graficului.

Definiție

Un graf nedirecționat se numește bipartit dacă mulțimea vârfurilor sale poate fi împărțită în două părți astfel încât: $G=(W,E)$ $U\cup V=W$

niciun vârf în nu este conectat la vârfuri în $U$ $U$
niciun vârf în nu este conectat la vârfuri în $V$ $V$

În acest caz, subseturile de vârfuri și sunt numite părți ale unui graf bipartit . $U$ $V$ $G$

Definiții înrudite

Un graf bipartit se numește graf bipartit complet (acest concept este diferit de un graf complet ; adică unul în care fiecare pereche de vârfuri este conectată printr-o muchie) dacă există o muchie pentru fiecare pereche de vârfuri . Pentru $u\în U,v\în V$ $(u,v)\în E$

|U|=i,|V|=j

un astfel de grafic este notat cu simbolul . $K_{{i,j}}$

Exemple

Graficele bipartite apar în mod natural la modelarea relațiilor dintre două clase diferite de obiecte. De exemplu, graficul jucătorilor de fotbal și al cluburilor: o margine leagă jucătorul corespunzător și clubul dacă jucătorul a jucat în acest club. Mai multe exemple abstracte de grafice bipartite:

Copac .
Un ciclu simplu format dintr-un număr par de vârfuri.
Orice grafic plan a cărui față este mărginită de un număr par de muchii.

Graficele bipartite sunt folosite pentru a descrie codurile LDPC .

Proprietăți

Un grafic este bipartit dacă și numai dacă nu conține un ciclu de lungime impară .
- În special, un grafic bipartit nu poate conține o clică de dimensiune mai mare de 2.
Un grafic este bipartit dacă și numai dacă este 2-cromatic; adică numărul său cromatic este doi.
Graficul este împărțit în perechi de vârfuri multicolore dacă și numai dacă oricare dintre elementele uneia dintre părți sunt conectate cel puțin cu elemente ale celeilalte ( teorema Wedding ). $k$ $k$
Un graf bipartit complet cu mai mult de 2 vârfuri în fiecare parte este neplanar .
Orice grafic bipartit este perfect .

Se verifică bipartit

Pentru a verifica caracterul bipartit al graficului, este suficient să selectați orice vârf din fiecare componentă conectată și să marcați vârfurile rămase în timpul parcurgerii graficului (de exemplu, prin căutare pe lățimea întâi ) alternativ ca par și impar (vezi ilustrația) . Dacă nu există niciun conflict, toate vârfurile pare formează mulțimea , iar toate vârfurile impare formează . $U$ $V$

Aplicații

rețele Petri
Contele Levy
Teoria codificarii
- graficul factorilor
- Contele de Tanner