miniatura|Exemplu de graf bipartit fără cicluri miniatura| 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 și (adică și sunt fiecare ), astfel încât fiecare muchie conectează un nod din cu unul din . Mulțimile de noduri și 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 și pot fi gândite ca o colorare a grafului cu două culori: dacă se colorează toate nodurile din cu albastru, și toate nodurile din 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 : 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 pentru a desemna un graf bipartit a cărui partiție are părțile și , iar este mulțimea muchiilor din graf. Dacă un graf bipartit nu este , acesta poate avea mai mult de o bipartiție;. în acest caz, notația precizează o anume bipartiție care poate fi de importanță într-o aplicație. Dacă , adică dacă cele două subgrupuri sunt de egale, atunci se numește graf bipartit echilibrat., p. 7. Dacă toate nodurile de pe aceeași parte a bipartiției au același grad, atunci este numit .
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 ..
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 î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. 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ă și , în care fiecare interior este format din 4 muchii și fiecare nod interior are patru sau mai mulți vecini.. cu m și n noduri, notate cu Kn,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ă Km,n are mn muchii., p. 11. O noțiune strâns legată de grafurile bipartite complete sunt , formate din grafuri bipartite complete prin eliminarea muchiilor unui .. 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 ., Theorem 2.1.3, p. 8. Un graf este bipartit dacă și numai dacă este 2-colorabil, (adică numărul său cromatic este mai mic sau egal cu 2). unui graf este simetric dacă și numai dacă este un graf bipartit.
Teorema lui König și grafurile perfecte În grafurile bipartite, dimensiunea este egală cu dimensiunea ; aceasta este . O formă alternativă și echivalentă a acestei teoreme este că dimensiunea plus dimensiunea cuplajului maxim este egală cu numărul de noduri. În orice graf fără noduri izolate dimensiunea 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ă : orice graf bipartit, oricărui graf bipartit, 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 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 , grafurile perfecte au o 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 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 . Formula sumei gradelor pentru un graf bipartit afirmă că
Șirul gradelor unui graf bipartit este o pereche de liste, fiecare conținând gradele de cele două părți și . De exemplu, graful bipartit complet K3,5 are șirul de grade . 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.
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 este o de dimensiune care are un pentru fiecare pereche de vârfuri adiacente și zero pentru nodurile neadiacente., p. 17. 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 poate fi folosit pentru a modela un hipergraf în care este mulțimea de noduri a hipergrafului, este mulțimea de hipermuchii, și conține o muchie de la nod de hipergraf la o muchie de hipergraf atunci când este una din extremitățile lui . 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 noduri poate fi orice -matrice de dimensiune , ceea ce se poate reinterpreta ca matricea de adiacență a unui graf bipartit cu noduri de fiecare parte a bipartiției.. În această construcție, graful bipartit este 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 a arborelui de căutare în adâncime. Acest lucru va furniza neapărat un î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 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 de 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 , chiar dacă graful în sine poate avea până la muchii.
Transversală de ciclu impar miniatura|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 , î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(3k mn), deși în lucrare acesta nu este menționat..