Vizualizare sursă pentru „Graf bipartit”

[[Fișier:Simple-bipartite-graph.svg|miniatura|Exemplu de graf bipartit fără cicluri]]
[[Fișier:Biclique_K_3_5.svg|miniatura|{{Ill-wd|Q913598|3=Graf bipartit complet}} cu m = 5 și n = 3]]
În domeniul [[Matematică|matematic]] al [[Teoria grafurilor|teoriei grafurilor]], un '''graf bipartit''' (sau '''bigraf''') este un [[graf]] ale cărui [[Nod (teoria grafurilor)|noduri]] pot fi împărțite în două [[mulțimi disjuncte]] <math>U</math> și <math>V</math> (adică <math>U</math> și <math>V</math> sunt fiecare {{Ill-wd|Q1060343|3=mulțimi de noduri independente}}), astfel încât fiecare [[Glosar de teoria grafurilor|muchie]] conectează un nod din <math>U</math> cu unul din <math>V</math>. Mulțimile de noduri <math>U</math> și <math>V</math> sunt de obicei numite ''părțile'' grafului. Echivalent, un graf bipartit este un graf care nu conține niciun [[Ciclu (teoria grafurilor)|ciclu]] de lungime impară.<ref name="diestel2005graph">{{cite book|last=Diestel|first=Reinard|title=Graph Theory, Grad. Texts in Math|year=2005|publisher=Springer|isbn=978-3-642-14278-9|url=http://diestel-graph-theory.com/}}</ref><ref>{{citation|last1=Asratian|first1=Armen S.|last2=Denley|first2=Tristan M. J.|last3=Häggkvist|first3=Roland|isbn=9780521593458|publisher=Cambridge University Press|series=Cambridge Tracts in Mathematics|title=Bipartite Graphs and their Applications|volume=131|year=1998}}.</ref>

Cele două mulțimi <math>U</math> și <math>V</math> pot fi gândite ca o colorare a grafului cu două culori: dacă se colorează toate nodurile din <math>U</math> cu albastru, și toate nodurile din <math>V</math> cu verde, fiecare muchie are extremitățile de culori diferite, după cum este necesar în problema colorării grafului.<ref name="s12">{{citation|last=Scheinerman|first=Edward R.|authorlink=Ed Scheinerman|edition=3rd|isbn=9780840049421|page=363|publisher=Cengage Learning|title=Mathematics: A Discrete Introduction|url=https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363|year=2012}}</ref> O astfel de colorare este imposibilă în cazul unui graf nebipartit, cum ar fi un {{Ill-wd|Q5519016|3=triunghi}}: 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 <math>G=(U,V,E)</math> pentru a desemna un graf bipartit a cărui partiție are părțile <math>U</math> și <math>V</math>, iar <math>E</math> este mulțimea muchiilor din graf. Dacă un graf bipartit nu este {{Ill-wd|Q230655|3=conex}}, acesta poate avea mai mult de o bipartiție;<ref>{{citation|last1=Chartrand|first1=Gary|last2=Zhang|first2=Ping|isbn=9781584888000|page=223|publisher=CRC Press|series=Discrete Mathematics And Its Applications|title=Chromatic Graph Theory|url=https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223|volume=53|year=2008}}.</ref> în acest caz, notația <math /> precizează o anume bipartiție care poate fi de importanță într-o aplicație. Dacă <math />, adică dacă cele două subgrupuri sunt de {{Ill-wd|Q4049983|3=cardinalități}} egale, atunci <math /> se numește graf bipartit ''echilibrat''.<ref name="adh98-7">{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 7.</ref> Dacă toate nodurile de pe aceeași parte a bipartiției au același [[Grad (teoria grafurilor)|grad]], atunci <math>G</math> este numit {{Ill-wd|Q1153612|3=graf biregulat}}.

== 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 {{Ill-wd|Q1140126|3=analiza rețelelor sociale}}.<ref>{{citation|last1=Wasserman|first1=Stanley|author-link1=Stanley Wasserman|last2=Faust|first2=Katherine|isbn=9780521387071|pages=299–302|publisher=Cambridge University Press|series=Structural Analysis in the Social Sciences|title=Social Network Analysis: Methods and Applications|url=https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA299|volume=8|year=1994}}.</ref>

Un alt exemplu unde grafurile bipartite apar în mod natural este problema optimizării căilor ferate ([[NP-completitudine|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 {{Ill-wd|Q2915204|3=mulțimii dominante}} î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.<ref name="niedermeier2006invitiation">{{cite book|last=Niedermeier|first=Rolf|title=Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications)|year=2006|publisher=Oxford|isbn=978-0-19-856607-6|pages=20–21}}</ref>

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. <ref name="bracey2012">{{cite article|last=Bracey|first=Robert|title=On the Graphical Interpreation of Herod's Coinage in Judaea and Rome in Coins|year=2012|url=https://www.academia.edu/2078897/On_the_Graphical_Interpretation_of_Herods_Coinage|pages=65–84}}</ref>

Exemple mai abstracte sunt:
* Orice [[Arbore (teoria grafurilor)|arbore]] este bipartit.
* {{Ill-wd|Q622506|3=Grafurile ciclu}} cu un număr par de noduri sunt bipartite.
* Fiecare [[graf planar]] ale cărui [[Glosar de teoria grafurilor|fețe]] au toate lungime pară este bipartit.<ref>{{citation|first=Alexander|last=Soifer|authorlink=Alexander Soifer|year=2008|title=The Mathematical Coloring Book|publisher=[[Springer-Verlag]]|isbn=978-0-387-74640-1|pages=136–137}}. </ref> Cazuri speciale sunt {{Ill-wd|Q6497118|3=grafurile grilă}} și {{Ill-wd|Q7582090|3=grafurile pătrate}}, în care fiecare interior este format din 4 muchii și fiecare nod interior are patru sau mai mulți vecini.<ref>{{citation|title=Combinatorics and geometry of finite and infinite squaregraphs|first1=H.-J.|last1=Bandelt|first2=V.|last2=Chepoi|first3=D.|last3=Eppstein|author3-link=David Eppstein|arxiv=0905.4537|journal={{Ill-wd|Q7390256}}|volume=24|issue=4|pages=1399–1440|year=2010|doi=10.1137/090760301}}.</ref>
* {{Ill-wd|Q913598|3=Graful bipartit complet}} cu ''m'' și ''n'' noduri, notate cu ''K<sub>n,m</sub>'' 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<sub>m,n</sub>'' are ''mn'' muchii.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 11.</ref> O noțiune strâns legată de grafurile bipartite complete sunt {{Ill-wd|Q3115466|3=grafurile coroană}}, formate din grafuri bipartite complete prin eliminarea muchiilor unui {{Ill-wd|Q1065144|3=cuplaj perfect}}.<ref>{{citation|last1=Archdeacon|first1=D.|last2=Debowsky|first2=M.|last3=Dinitz|first3=J.|last4=Gavlas|first4=H.|doi=10.1016/j.disc.2003.11.021|issue=1–3|journal={{Ill-wd|Q5282038|3=Discrete Mathematics}}|pages=37–43|title=Cycle systems in the complete bipartite graph minus a one-factor|volume=284|year=2004}}.</ref>
* 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.<ref>{{citation|first=Sergei|last=Ovchinnikov|title=Graphs and Cubes|series=Universitext|publisher=Springer|year=2011}}. </ref>

== Proprietăți ==

=== Caracterizarea ===
Grafurile bipartite pot fi caracterizate în mai multe moduri diferite:
* Un graf este bipartit [[Dacă și numai dacă|dacă și numai dacă]] nu conține un {{Ill-wd|Q622506|3=ciclu impar}}.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, Theorem 2.1.3, p. 8. </ref>
* Un graf este bipartit dacă și numai dacă este 2-colorabil, (adică [[Colorarea grafurilor|numărul său cromatic]] este mai mic sau egal cu 2).
* {{Ill-wd|Q3180727|3=Spectrul}} unui graf este simetric dacă și numai dacă este un graf bipartit.<ref>{{citation|last=Biggs|first=Norman|edition=2nd|isbn=9780521458979|page=53|publisher=Cambridge University Press|series=Cambridge Mathematical Library|title=Algebraic Graph Theory|url=https://books.google.com/books?id=6TasRmIFOxQC&pg=PA53|year=1994}}</ref>

=== Teorema lui König și grafurile perfecte ===
În grafurile bipartite, dimensiunea {{Ill-wd|Q924362|3=acoperirii minime cu noduri}} este egală cu dimensiunea {{Ill-wd|Q1065144|3=cuplajului maxim}}; aceasta este {{Ill-wd|Q897769|3=teorema lui König}}.<ref>{{cite journal|author=Kőnig, Dénes|authorlink=Dénes Kőnig|title=Gráfok és mátrixok|journal=Matematikai és Fizikai Lapok|volume=38|year=1931|pages=116–119}}</ref><ref>{{citation|last1=Gross|first1=Jonathan L.|last2=Yellen|first2=Jay|edition=2nd|isbn=9781584885054|page=568|publisher=CRC Press|series=Discrete Mathematics And Its Applications|title=Graph Theory and Its Applications|url=https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568|year=2005}}</ref> O formă alternativă și echivalentă a acestei teoreme este că dimensiunea {{Ill-wd|Q1060343|3=mulțimii independente maxime}} plus dimensiunea cuplajului maxim este egală cu numărul de noduri.
În orice graf fără [[Nod (teoria grafurilor)|noduri izolate]] dimensiunea {{Ill-wd|Q594001|3=acoperirii minime cu muchii}} plus dimensiunea cuplajului maxim este egală cu numărul de noduri.<ref>{{citation|last1=Chartrand|first1=Gary|last2=Zhang|first2=Ping|isbn=9780486483689|pages=189–190|publisher=Courier Dover Publications|title=A First Course in Graph Theory|url=https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189|year=2012}}.</ref> 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ă {{Ill-wd|Q1187620|3=grafurile perfecte}}: orice graf bipartit, {{Ill-wd|Q902252|3=complementul}} oricărui graf bipartit, {{Ill-wd|Q1378376|3=graful linie}} 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 ([[Colorarea grafurilor|numărul lor cromatic]] este doi și dimensiunea [[Clică|clicii maxime]] este tot doi) dar perfecțiunea {{Ill-wd|Q902252|3=complementelor}} 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.<ref>{{citation|title=Modern Graph Theory|volume=184|series=[[Graduate Texts in Mathematics]]|author={{Ill-wd|Q834127}}|publisher=Springer|year=1998|isbn=9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165}}.</ref> 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 {{Ill-wd|Q17156804|3=teoremei tari a grafurilor perfecte}}, grafurile perfecte au o {{Ill-wd|Q5467387|3=caracterizare de graf  interzisă}} 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 {{Ill-wd|Q902252|3=complementul}} 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.<ref>{{citation|last1=Chudnovsky|first1=Maria|author1-link=Maria Chudnovsky|last2=Robertson|first2=Neil|author2-link=Neil Robertson (mathematician)|last3=Seymour|first3=Paul|author3-link=Paul Seymour (mathematician)|last4=Thomas|first4=Robin|author4-link=Robin Thomas (mathematician)|doi=10.4007/annals.2006.164.51|issue=1|journal={{Ill-wd|Q564426}}|pages=51–229|title=The strong perfect graph theorem|url=http://annals.princeton.edu/annals/2006/164-1/p02.xhtml|volume=164|year=2006|citeseerx=10.1.1.111.7265}}.</ref>

=== Gradul ===
Pentru un nod, numărul de noduri adiacente se numește [[Grad (teoria grafurilor)|gradul]] nodului și se notează cu <math>\deg(v)</math>.
''Formula sumei gradelor'' pentru un graf bipartit afirmă că
: <math>\sum_{v \in V} \deg(v) = \sum_{u \in U} \deg(u) = |E|\, .</math>
Șirul gradelor unui graf bipartit este o pereche de liste, fiecare conținând gradele de cele două părți <math>U</math> și <math>V</math>. De exemplu, graful bipartit complet ''K''<sub>3,5</sub> are șirul de grade <math>(5,5,5),(3,3,3,3,3)</math>. 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.

{{Ill-wd|Q18206555|3=Problema realizării bipartite}} 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 ===
[[Matrice de adiacență|Matricea de biadiacență]] a unui graf bipartit <math>(U,V,E)</math> este o {{Ill-wd|Q1994977|3=(0,1)-matrice}} de dimensiune <math>|U|\times|V|</math> care are un pentru fiecare pereche de vârfuri adiacente și zero pentru nodurile neadiacente.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 17.</ref> 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 <math>(U,V,E)</math> poate fi folosit pentru a modela un hipergraf în care <math>U</math> este mulțimea de noduri a hipergrafului, <math>V</math> este mulțimea de hipermuchii, și <math>E</math> conține o muchie de la nod de hipergraf <math>u</math> la o muchie de hipergraf <math>e</math> atunci când <math>v</math> este una din extremitățile lui <math>e</math>. 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 [[Grad (teoria grafurilor)|gradul]] doi.<ref>{{SpringerEOM|title=Hypergraph|author=A. A. Sapozhenko}}</ref>

O reinterpretare similară a matricelor de adiacență poate fi folosită pentru a arăta o corespondență unu-la-unu între [[Graf orientat|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 <math>n</math> noduri poate fi orice <math>(0,1)</math>-matrice de dimensiune <math>n\times n</math>, ceea ce se poate reinterpreta ca matricea de adiacență a unui graf bipartit cu <math>n</math> noduri de fiecare parte a bipartiției.<ref>{{citation|last1=Brualdi|first1=Richard A.|last2=Harary|first2=Frank|author2-link=Frank Harary|last3=Miller|first3=Zevi|doi=10.1002/jgt.3190040107|mr=558453|issue=1|journal=Journal of Graph Theory|pages=51–73|title=Bigraphs versus digraphs via matrices|volume=4|year=1980}}. </ref> În această construcție, graful bipartit este {{Ill-wd|Q4915409|3=acoperirea bipartită dublă}} 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 [[Complexitate în timp|timp liniar]], folosind [[Căutare în adâncime|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 {{Ill-wd|Q1210082|3=parcurgere în preordine}} a arborelui de căutare în adâncime. Acest lucru va furniza neapărat un {{Ill-wd|Q831672|3=arbore de acoperire}} î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.<ref>{{Citation|title=Algorithms in Java, Part 5: Graph Algorithms|year=2004|last=Sedgewick|first=Robert|author-link=Robert Sedgewick (computer scientist)|pages=109–111|edition=3rd|publisher=Addison Wesley}}</ref>

Alternativ, o procedură similară poate fi folosită cu o [[Căutare în lățime|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 {{Ill-wd|Q4312352|3=cel mai mic strămoș comun}} 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.<ref>{{Citation|title=Algorithm Design|year=2006|last1=Kleinberg|last2=Tardos|first1=Jon|first2=Éva|author1-link=Jon Kleinberg|author2-link=Éva Tardos|pages=94–97|publisher=Addison Wesley}}.</ref>

Pentru {{Ill-wd|Q3498041|3=grafurile intersecție}} de <math>n</math> [[Segment (geometrie)|segmente de linie]] sau alte forme simple în [[2D|planul euclidian]], se poate testa dacă graful este bipartit și returna ori o doi-colorare, ori un ciclu impar în timp <math>O(n\log n)</math>, chiar dacă graful în sine poate avea până la <math>\Omega(n^2)</math> muchii.<ref>{{Citation|title=Testing bipartiteness of geometric intersection graphs|year=2009|last=Eppstein|first=David|author-link=David Eppstein|journal=ACM Transactions on Algorithms|volume=5|issue=2|page=Art. 15|doi=10.1145/1497290.1497291|DOI=10.1145/1497290.1497291}}</ref>

=== Transversală de ciclu impar ===
[[Fișier:Odd_Cycle_Transversal_of_size_2.png|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-completitudine|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&nbsp;''G'' ar face ca graful rezultat să fie bipartit.<ref name="yannakakis1978node">{{Citation|title={{Ill-wd|Q7661893|3=Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78)}}|year=1978|last=Yannakakis|first=Mihalis|author-link=Mihalis Yannakakis|pages=253–264|contribution=Node-and edge-deletion NP-complete problems|doi=10.1145/800133.804355|DOI=10.1145/800133.804355}}</ref> Problema este {{Ill-wd|Q1570441|3=tractabilă în parametru fix}}, î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''.<ref name="reed2004finding">{{Citation|title=Finding odd cycle transversals|year=2004|last1=Reed|last2=Smith|last3=Vetta|first1=Bruce|first2=Kaleigh|first3=Adrian|author1-link=Bruce Reed (mathematician)|journal=Operations Research Letters|volume=32|issue=4|pages=299–301|doi=10.1016/j.orl.2003.10.009|DOI=10.1016/j.orl.2003.10.009}}.</ref> Mai precis, timpul pentru acest algoritm este ''O''(3<sup>''k''</sup> ''mn''), deși în lucrare acesta nu este menționat.<ref name="huffner2005algorithm">{{Citation|title=Algorithm engineering for optimal graph bipartization|year=2005|last1=Hüffner|first1=Falk|journal=Experimental and Efficient Algorithms|pages=240–252|doi=10.1007/11427186_22|DOI=10.1007/11427186_22}}.</ref>
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 [[Ciclu (teoria grafurilor)|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, {{Ill-wd|Q1570441|3=tractabilă în parametru fix}}, și poate fi rezolvată în timp ''O''(2<sup>''k''</sup> ''m''<sup>2</sup>),<ref name="guo2006compression">{{Citation|title=Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization|year=2006|last1=Guo|last2=Gramm|last3=Hüffner|last4=Niedermeier|last5=Wernicke|first1=Jiong|first2=Jens|first3=Falk|first4=Rolf|first5=Sebastian|journal=JCSS|pages=1386–1396|doi=10.1016/j.jcss.2006.02.001|DOI=10.1016/j.jcss.2006.02.001}}</ref> unde ''k'' este numărul de muchii de șters și ''m'' este numărul de muchii din graful de intrare.

=== Cuplaje ===
Un {{Ill-wd|Q1065144|3=cuplaj}} î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 [[Complexitate în timp|în timp polinomial]] pentru multe probleme de cuplaje, inclusiv {{Ill-wd|Q1065144|3=cuplajul maxim}} (găsirea unui cuplaj care utilizează cât mai multe muchii posibil), {{Ill-wd|Q1065144|3=cuplajul de pondere maximă}}, și {{Ill-wd|Q620702|3=căsnicia stabilă}}.<ref>{{Citation|title=Network Flows: Theory, Algorithms, and Applications|year=1993|last1=Ahuja|last2=Magnanti|last3=Orlin|first1=Ravindra K.|first2=Thomas L.|first3=James B.|pages=461–509|contribution=12. Assignments and Matchings|publisher=Prentice Hall}}</ref> În multe cazuri, problemele de potrivire sunt mai simplu de rezolvat pe grafurile bipartite decât pe cele nebipartite,<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."</ref> și mulți algoritmi de cuplaj, cum ar fi {{Ill-wd|Q1516988|3=algoritmul Hopcroft–Karp}} pentru cardinalitatea maximă a cuplajelor<ref>{{Citation|title=An ''n''<sup>5/2</sup> algorithm for maximum matchings in bipartite graphs|year=1973|last1=Hopcroft|last2=Karp|first1=John E.|first2=Richard M.|author1-link=John Hopcroft|author2-link=Richard Karp|journal=SIAM Journal on Computing|volume=2|issue=4|pages=225–231|doi=10.1137/0202019|DOI=10.1137/0202019}}.</ref> funcționează corect numai pe intrări bipartite.

Ca exemplu simplu, să presupunem că o mulțime <math>P</math> de oameni sunt în căutarea de locuri de muncă dintr-o mulțime de <math>J</math> locuri de muncă, dar nu toate persoanele se potrivesc pentru toate locurile de muncă. Această situație poate fi modelată ca un graf bipartit <math>(P,J,E)</math> unde o muchie conectează fiecare solicitant de loc de muncă cu fiecare loc de muncă adecvat.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.</ref> Un {{Ill-wd|Q1065144|3=cuplaj perfect}} 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|teorema căsătoriilor a lui Hall]] oferă o caracterizare a grafurilor bipartite care permit cuplaje perfecte. {{Ill-wd|Q6978073}} aplică metodele de cuplaje pe grafuri pentru a rezolva această problemă între {{Ill-wd|Q6806523|3=studenții americani la medicină}} și [[Rezidență (medicină)|posturile de medic rezident în spitale]].<ref>{{Citation|title=Are Medical Students Meeting Their (Best Possible) Match?|last=Robinson|first=Sara|date=April 2003|url=http://www.siam.org/pdf/news/305.pdf|journal=SIAM News|issue=3|page=36|access-date=2017-06-19|archive-date=2016-11-18|archive-url=https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf|dead-url=yes}}</ref>

Descompunerea Dulmage–Mendelsohn este o descompunere structurală a grafurilor bipartite, care este utilă în găsirea de cuplaje maxime.<ref>{{harvtxt|Dulmage|Mendelsohn|1958}}.</ref>

== Alte aplicații ==
Grafurile bipartite sunt utilizate pe scară largă în {{Ill-wd|Q602136|3=teoria modernă a codurilor}}, mai ales pentru a decoda {{Ill-wd|Q863873|3=cuvinte de cod}} primite de pe canal. {{Ill-wd|Q5428725|3=Grafurile de factorizare}} și {{Ill-wd|Q7683664|3=grafurile Tanner}} 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.<ref>{{Citation|title=Error Correction Coding: Mathematical Methods and Algorithms|year=2005|last=Moon|first=Todd K.|url=https://books.google.com/books?id=adxb8CRx5vQC&pg=PA638|page=638|publisher=John Wiley & Sons|isbn=9780471648000|ISBN=9780471648000}}.</ref> Un graf de factorizare este strâns legat [[Rețea bayesiană|rețeaua de credințe]] folosită pentru decodarea probabilistică {{Ill-wd|Q187444}} și {{Ill-wd|Q2164281|3=codurile turbo}}.<ref>{{harvtxt|Moon|2005}}, p. 686.</ref>

Î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.<ref>{{Citation|title=Introduction to Discrete Event Systems|year=2007|last1=Cassandras|last2=Lafortune|first1=Christos G.|first2=Stephane|url=https://books.google.com/books?id=AxguNHDtO7MC&pg=PA224|page=224|edition=2nd|publisher=Springer|isbn=9780387333328|ISBN=9780387333328}}</ref>

În [[Geometrie proiectivă|geometria proiectivă]], {{Ill-wd|Q6535569|3=grafurile Levi}} sunt o formă de grafuri bipartite folosite pentru a modela incidențele între puncte și linii într-o {{Ill-wd|Q1866689|3=configurație}}. 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 {{Ill-wd|Q959831|3=calibrul}} lor trebuie să fie cel puțin șase.<ref>{{Citation|title=Configurations of Points and Lines|year=2009|last=Grünbaum|first=Branko|author-link=Branko Grünbaum|url=https://books.google.com/books?id=mRw571GNa5UC&pg=PA28|series=[[Graduate Studies in Mathematics]]|volume=103|page=28|publisher=[[American Mathematical Society]]|isbn=9780821843086|ISBN=9780821843086}}.</ref>

== Bibliografie ==
<references />

== Legături externe ==
* {{en icon}} {{springer|title=Graph, bipartite|id=p/g044880}}
* {{en icon}} [http://www.graphclasses.org/ Information System on Graph Classes and their Inclusions]: [http://www.graphclasses.org/classes/gc_69.html bipartite graph]
* {{en icon}} {{mathworld | title = Bipartite Graph | urlname = BipartiteGraph}}

{{Portal|Matematică}}
{{Clase de grafuri}}

[[Categorie:Grafuri|Bipartit]]
[[Categorie:Paritate]]