Graf bipartit

Exemplu de graf bipartit fără cicluri

Graf bipartit complet^⁠(d) cu m = 5 și n = 3

În domeniul matematic al teoriei grafurilor, un graf bipartit (sau bigraf) este un graf ale cărui noduri pot fi împărțite în două mulțimi disjuncte $U$ și $V$ (adică $U$ și $V$ sunt fiecare mulțimi de noduri independente^⁠(d)), astfel încât fiecare muchie conectează un nod din $U$ cu unul din $V$. Mulțimile de noduri $U$ și $V$ sunt de obicei numite părțile grafului. Echivalent, un graf bipartit este un graf care nu conține niciun ciclu de lungime impară.

Cele două mulțimi $U$ și $V$ pot fi gândite ca o colorare a grafului cu două culori: dacă se colorează toate nodurile din $U$ cu albastru, și toate nodurile din $V$ cu verde, fiecare muchie are extremitățile de culori diferite, după cum este necesar în problema colorării grafului. O astfel de colorare este imposibilă în cazul unui graf nebipartit, cum ar fi un triunghi^⁠(d): după ce un nod este colorat albastru și altul verde, cel de-al treilea vârf al triunghiului este conectat la noduri de ambele culori, împiedicând atribuirea oricărei culori.

Deseori se scrie $G=(U,V,E)$ pentru a desemna un graf bipartit a cărui partiție are părțile $U$ și $V$, iar $E$ este mulțimea muchiilor din graf. Dacă un graf bipartit nu este conex^⁠(d), acesta poate avea mai mult de o bipartiție; în acest caz, notația ${\displaystyle }$ precizează o anume bipartiție care poate fi de importanță într-o aplicație. Dacă ${\displaystyle }$, adică dacă cele două subgrupuri sunt de cardinalități^⁠(d) egale, atunci ${\displaystyle }$ se numește graf bipartit echilibrat. Dacă toate nodurile de pe aceeași parte a bipartiției au același grad, atunci $G$ este numit graf biregulat^⁠(d).

Exemple

La modelarea relațiilor dintre două clase diferite de obiecte, grafurile bipartite apar de foarte multe ori în mod natural. De exemplu, un graf al fotbaliștilor și cluburilor, cu o margine între un jucător și un club dacă jucătorul a jucat la respectivul club este un exemplu natural de rețea de afiliere, un tip de graf bipartit utilizat în analiza rețelelor sociale^⁠(d).

Un alt exemplu unde grafurile bipartite apar în mod natural este problema optimizării căilor ferate (NP-completă), în care intrarea este un orar al trenurilor și stațiilor, iar scopul este să se găsească o mulțime de stații de tren cât mai mică cu putință, astfel încât fiecare tren să viziteze cel puțin una dintre stațiile alese. Această problemă poate fi modelată ca o problemă a mulțimii dominante^⁠(d) într-un graf bipartit, care are un nod pentru fiecare tren și fiecare stație și o muchie pentru fiecare pereche stație-tren ce semnifică oprirea trenului în stație.

Un al treilea exemplu este din domeniul academic al numismaticii. Monedele antice sunt realizate cu ajutorul a două impresii pozitive de design (avers și revers). Graficele produse de numismați pentru a reprezenta producția de monede sunt grafuri bipartite.

Exemple mai abstracte sunt:

• Orice arbore este bipartit.
• Grafurile ciclu^⁠(d) cu un număr par de noduri sunt bipartite.
• Fiecare graf planar ale cărui fețe au toate lungime pară este bipartit. Cazuri speciale sunt grafurile grilă^⁠(d) și grafurile pătrate^⁠(d), în care fiecare interior este format din 4 muchii și fiecare nod interior are patru sau mai mulți vecini.
• Graful bipartit complet^⁠(d) cu m și n noduri, notate cu K_n,m este graful bipartit G = (U, V, E), unde U și V sunt mulțimi disjuncte de dimensiuni m și n, respectiv, și E conectează fiecare nod din U cu toate nodurile din V. Rezultă că K_m,n are mn muchii. O noțiune strâns legată de grafurile bipartite complete sunt grafurile coroană^⁠(d), formate din grafuri bipartite complete prin eliminarea muchiilor unui cuplaj perfect^⁠(d).
• Grafurile hipercub, cuburile parțiale, și grafurile mediane sunt bipartite. În aceste grafuri, nodurile pot fi etichetate prin bitvectori, în așa fel încât două noduri sunt adiacente dacă și numai dacă respectivii bitvectori diferă într-o singură poziție. O bipartiție poate fi formată prin separarea de noduri ale căror bitvectori au un număr par de 1-uri de la nodurile cu un număr impar de 1-uri. Arborii și grafurile pătrat formează exemple de grafuri mediane, și fiecare graf median este un cub parțial.

Proprietăți

Caracterizarea

Grafurile bipartite pot fi caracterizate în mai multe moduri diferite:

• Un graf este bipartit dacă și numai dacă nu conține un ciclu impar^⁠(d).
• Un graf este bipartit dacă și numai dacă este 2-colorabil, (adică numărul său cromatic este mai mic sau egal cu 2).
• Spectrul^⁠(d) unui graf este simetric dacă și numai dacă este un graf bipartit.

Teorema lui König și grafurile perfecte

În grafurile bipartite, dimensiunea acoperirii minime cu noduri^⁠(d) este egală cu dimensiunea cuplajului maxim^⁠(d); aceasta este teorema lui König^⁠(d). O formă alternativă și echivalentă a acestei teoreme este că dimensiunea mulțimii independente maxime^⁠(d) plus dimensiunea cuplajului maxim este egală cu numărul de noduri. În orice graf fără noduri izolate dimensiunea acoperirii minime cu muchii^⁠(d) plus dimensiunea cuplajului maxim este egală cu numărul de noduri. Din combinarea aceastei egalități cu teorema lui König rezultă că, în grafurile bipartite, dimensiunea acoperirii minime cu muchii este egală cu dimensiunea mulțimii independente maxime, iar dimensiunea acoperirii minime cu muchii plus dimensiunea acoperirii minime cu noduri este egală cu numărul de noduri.

O altă clasă de rezultate asociate implică grafurile perfecte^⁠(d): orice graf bipartit, complementul^⁠(d) oricărui graf bipartit, graful linie^⁠(d) al fiecărui graf bipartit, și un complement al grafului linie al fiecărui graf bipartit, sunt toate perfecte. Perfecțiunea grafurilor bipartite este ușor de observat (numărul lor cromatic este doi și dimensiunea clicii maxime este tot doi) dar perfecțiunea complementelor^⁠(d) grafurilor bipartite este mai puțin banală, și este o altă reformulare a teoremei lui König. Acesta a fost unul dintre rezultatele care au motivat definirea grafurilor perfecte. Perfecțiunea complementelor grafurilor linie ale grafurilor perfecte este încă o altă reformulare a teoremei lui König, și perfecțiunea grafurilor linie  ub sube este o reformulare a unei teoreme mai vechi tot a lui König, conform căreia orice graf bipartit are o colorare de muchii, folosind număr de culori egală cu gradul maxim.

Conform teoremei tari a grafurilor perfecte^⁠(d), grafurile perfecte au o caracterizare de graf interzisă^⁠(d) asemănătoare cu cea a grafurilor bipartite: un graf este bipartit dacă și numai dacă acesta nu are niciun ciclu impar ca subgraf, și un graf este perfect dacă și numai dacă acesta nu are niciu ciclu impar și nici pe complementul^⁠(d) său ca subgraf indus. Grafurile bipartite, grafurile linie ale grafurilor bipartite și complementele lor formează patru din cele cinci clase de bază ale grafurilor perfecte utilizate în demonstrația teoremei tari a grafurilor perfecte.

Gradul

Pentru un nod, numărul de noduri adiacente se numește gradul nodului și se notează cu $\deg(v)$. Formula sumei gradelor pentru un graf bipartit afirmă că

$\sum _{v\in V}\deg(v)=\sum _{u\in U}\deg(u)=|E|\,.$

Șirul gradelor unui graf bipartit este o pereche de liste, fiecare conținând gradele de cele două părți $U$ și $V$. De exemplu, graful bipartit complet K_3,5 are șirul de grade $(5,5,5),(3,3,3,3,3)$. Grafurile bipartite izomorfe au același șir de grade. Cu toate acestea, șirul de grade nu identifică în mod unic un graf bipartit; în unele cazuri, grafuri bipartite neizomorfe pot avea același șir de grade.

Problema realizării bipartite^⁠(d) este problema găsirii unui graf bipartit simplu cu șirul de grade fiind două liste date de numere naturale. (Zerourile terminale pot fi ignorate, deoarece acestea sunt ușor de realizat prin adăugarea unui număr adecvat de noduri izolate la digraf.)

Relația cu hipergrafurile și cu grafurile orientate

Matricea de biadiacență a unui graf bipartit $(U,V,E)$ este o (0,1)-matrice^⁠(d) de dimensiune $|U|\times |V|$ care are un pentru fiecare pereche de vârfuri adiacente și zero pentru nodurile neadiacente. Matricele de biadiacență pot fi folosite pentru a descrie echivalențele între grafurile bipartite, hipergrafuri și grafuri orientate.

Un hipergraf este o structură combinatorică care, ca și un graf neorientat, are noduri și muchii, dar în care muchiile pot fi mulțimi arbitrare de noduri, neavând obligatoriu doar două extremități. Un graf bipartit $(U,V,E)$ poate fi folosit pentru a modela un hipergraf în care $U$ este mulțimea de noduri a hipergrafului, $V$ este mulțimea de hipermuchii, și $E$ conține o muchie de la nod de hipergraf $u$ la o muchie de hipergraf $e$ atunci când $v$ este una din extremitățile lui $e$. Sub această corespondență, matricele de biadiacență ale grafurilor bipartite sunt exact matricele de incidență corespunzătoare hipergrafurilor. Ca un caz special al acestei corespondențe între grafurile bipartite și hipergrafuri, orice multigraf (un graf în care pot exista două sau mai multe muchii între aceleași două noduri) poate fi interpretat ca un hipergraph în care unele hipermuchii au mulțimi egale de extremități, reprezentate printr-un graf bipartit care nu are adiacențe multiple și în care nodurile pe de o parte a bipartiției au toate gradul doi.

O reinterpretare similară a matricelor de adiacență poate fi folosită pentru a arăta o corespondență unu-la-unu între grafurile orientate (pe un anumit număr de noduri etichetate, care permit auto-bucle) și grafurile bipartite echilibrate, cu același număr de noduri pe ambele laturi ale partiției. Pentru că matrice de adiacență a unui graf orientat cu $n$ noduri poate fi orice $(0,1)$-matrice de dimensiune $n\times n$, ceea ce se poate reinterpreta ca matricea de adiacență a unui graf bipartit cu $n$ noduri de fiecare parte a bipartiției. În această construcție, graful bipartit este acoperirea bipartită dublă^⁠(d) a grafului orientat.

Algoritmi

Testarea bipartitudinii

Se poate verifica dacă un graf este bipartit, și calcula fie o doi-colorare (dacă este bipartit) sau un ciclu impar (dacă nu este) în timp liniar, folosind căutarea în adâncime. Ideea principală este de a atribui fiecărui nod o culoare diferită de culoarea părintelui său în arborele de căutare în adâncime, atribuind culorile într-o parcurgere în preordine^⁠(d) a arborelui de căutare în adâncime. Acest lucru va furniza neapărat un arbore de acoperire^⁠(d) în două culori, format fiind din muchiile ce conectează nodurile la părinții lor, dar nu poate colora corespunzător unele din muchiile din afara arborelui. Într-un arbore de căutare în adâncime, una dintre cele două extremități ale fiecărei muchii din afara arborelui este un strămoș al celeilalte extremități, și atunci când căutarea în adâncimea descoperă o muchie de acest tip, ar trebui verificat că aceste două noduri au culori diferite. Dacă nu, atunci drumul în arbore de la strămoș la descendent, împreună cu muchia colorată eronat, formează un ciclu impar, care este returnat de algoritm împreună cu rezultatul că graficul nu este bipartit. Cu toate acestea, dacă algoritmul se termină fără a detecta un ciclu impar de acest tip, atunci fiecare muchie trebuie să fie corect colorată, și algoritmul returnează colorarea împreună cu rezultatul că graful este bipartit.

Alternativ, o procedură similară poate fi folosită cu o căutare în lățime în loc de căutare în adâncime. Din nou, fiecare nod primește culoarea opusă față de părintele său din arborele de parcurgere în lățime. Dacă, atunci când un nod este colorat, există o muchie care îl conectează de un nod anterior colorat cu aceeași culoare, atunci această muchie, împreună cu căile din arborele de parcurgere în lățime ce leagă cele două extremități ale sale de cel mai mic strămoș comun^⁠(d) formează un ciclu impar. Dacă algoritmul se termină fără a găsi un ciclu impar în acest fel, atunci acesta trebuie să fi găsit o colorare corectă, și se poate concluziona cu siguranță că graful este bipartit.

Pentru grafurile intersecție^⁠(d) de $n$ segmente de linie sau alte forme simple în planul euclidian, se poate testa dacă graful este bipartit și returna ori o doi-colorare, ori un ciclu impar în timp $O(n\log n)$, chiar dacă graful în sine poate avea până la $\Omega (n^{2})$ muchii.

Transversală de ciclu impar

Un graf cu o transversală de ciclu impar de dimensiune 2: eliminarea celor două noduri albastre face graful să fie bipartit.

Transversala de ciclu impar este o problemă algoritmică NP-completă care cere ca, dat fiind un graf G = (V,E) și un număr k, să se verifice dacă există o mulțime de k noduri a căror îndepărtare din G ar face ca graful rezultat să fie bipartit. Problema este tractabilă în parametru fix^⁠(d), în sensul că nu există un algoritm al cărui timp de funcționare să poată fi delimitat printr-o funcție polinomială de dimensiunea grafului înmulțită cu o funcție mai mare de k. Mai precis, timpul pentru acest algoritm este O(3^k mn), deși în lucrare acesta nu este menționat. Rezultatul lui Reed et al. a fost obținut folosind o metodă complet nouă, care mai târziu a fost numită compresie iterativă și s-a dovedit a fi un instrument algoritmic extrem de util, mai ales în domeniul tractabilitații în parametru fix. Acest instrument este considerat acum unul dintre instrumentele fundamentale de algoritmică parametrizată.

Denumirea de transversală de ciclu impar vine de la faptul că un graf este bipartit dacă și numai dacă acesta nu are cicluri impare. Prin urmare, pentru a șterge noduri dintr-un graf, în scopul de a obține un graf bipartit, este nevoie să se „lovească toate ciclurile impare”, sau să se găsească o așa-numită mulțime transversală de ciclu impar. În figură, se poate observa că toate ciclurile impare din graf conțin nodurile albastre (de jos), prin urmare, eliminarea acestor noduri distruge toate ciclurile impare și lasă graful bipartit.

Problema bipartizării muchiilor problema este problema algoritmică de a șterge cât mai puține muchii posibil pentru a face graful bipartit și este, de asemenea, o problemă importantă în algoritmica modificării grafurilor. Această problemă este, de asemenea, tractabilă în parametru fix^⁠(d), și poate fi rezolvată în timp O(2^k m²), unde k este numărul de muchii de șters și m este numărul de muchii din graful de intrare.

Cuplaje

Un cuplaj^⁠(d) într-un graf este o submulțime a muchiilor sale cu proprietatea că nu există două care să aibă o extremitate comună. Se cunosc algoritmi în timp polinomial pentru multe probleme de cuplaje, inclusiv cuplajul maxim^⁠(d) (găsirea unui cuplaj care utilizează cât mai multe muchii posibil), cuplajul de pondere maximă^⁠(d), și căsnicia stabilă^⁠(d). În multe cazuri, problemele de potrivire sunt mai simplu de rezolvat pe grafurile bipartite decât pe cele nebipartite, și mulți algoritmi de cuplaj, cum ar fi algoritmul Hopcroft–Karp^⁠(d) pentru cardinalitatea maximă a cuplajelor funcționează corect numai pe intrări bipartite.

Ca exemplu simplu, să presupunem că o mulțime $P$ de oameni sunt în căutarea de locuri de muncă dintr-o mulțime de $J$ locuri de muncă, dar nu toate persoanele se potrivesc pentru toate locurile de muncă. Această situație poate fi modelată ca un graf bipartit $(P,J,E)$ unde o muchie conectează fiecare solicitant de loc de muncă cu fiecare loc de muncă adecvat. Un cuplaj perfect^⁠(d) descrie un mod de a satisface simultan toate solicitările de locuri de muncă și de a ocupa toate locurile de muncă; teorema căsătoriilor a lui Hall oferă o caracterizare a grafurilor bipartite care permit cuplaje perfecte. National Resident Matching Program^⁠(d) aplică metodele de cuplaje pe grafuri pentru a rezolva această problemă între studenții americani la medicină^⁠(d) și posturile de medic rezident în spitale.

Descompunerea Dulmage–Mendelsohn este o descompunere structurală a grafurilor bipartite, care este utilă în găsirea de cuplaje maxime.

Alte aplicații

Grafurile bipartite sunt utilizate pe scară largă în teoria modernă a codurilor^⁠(d), mai ales pentru a decoda cuvinte de cod^⁠(d) primite de pe canal. Grafurile de factorizare^⁠(d) și grafurile Tanner^⁠(d) sunt exemple în acest sens. Un graf Tanner este un graf bipartit în care nodurile de o parte a partiției reprezintă cifre dintr-un cuvânt de cod, și nodurile pe de altă parte reprezintă combinații de cifre, care sunt de așteptat să aibă suma zero într-un cuvânt de cod fără erori. Un graf de factorizare este strâns legat rețeaua de credințe folosită pentru decodarea probabilistică low-density parity-check code^⁠(d) și codurile turbo^⁠(d).

În informatică, o rețea Petri este un instrument de modelare matematică utilizat în analize și simulări ale sistemelor concurente. Un sistem este modelat ca un graf bipartit cu două mulțimi de noduri: o mulțime de „locuri” care conțin resurse, și o mulțime de „tranziții” care generează, transferă și/sau consumă resurse. Există constrângeri suplimentare pe nodurile și muchiile care constrâng comportamentul sistemului. Rețele Petri utilizează proprietățile grafurilor orientate bipartite și alte proprietăți pentru a permite demonstrații matematice ale comportamentului sistemelor în timp ce permite și implementarea de simulări ale sistemelor.

În geometria proiectivă, grafurile Levi^⁠(d) sunt o formă de grafuri bipartite folosite pentru a modela incidențele între puncte și linii într-o configurație^⁠(d). Corespunzătoare proprietăților geomerice ale punctelor și ale liniilor, acelea ca fiecare două linii să se întâlnească în cel mult un punct și ca orice două puncte să fie conectate cu o singură linie, grafurile Levi obligatoriu nu conțin cicluri de lungime patru, deci calibrul^⁠(d) lor trebuie să fie cel puțin șase.

Legături externe

• en Hazewinkel, Michiel, ed. (2001), „Graph, bipartite”, Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104 
• en Information System on Graph Classes and their Inclusions: bipartite graph
• en Eric W. Weisstein, Bipartite Graph la MathWorld.