b'\n_START_ARTICLE_\nGraf bipartit\n_START_PARAGRAPH_\n\xc3\x8en domeniul\xc2\xa0matematic\xc2\xa0al\xc2\xa0teoriei grafurilor, un graf bipartit (sau bigraf) este un graf ale c\xc4\x83rui noduri pot fi \xc3\xaemp\xc4\x83r\xc8\x9bite \xc3\xaen dou\xc4\x83 mul\xc8\x9bimi disjuncte  \xc8\x99i  (adic\xc4\x83\xc2\xa0 \xc8\x99i  sunt fiecare\xc2\xa0mul\xc8\x9bimi independente), astfel \xc3\xaenc\xc3\xa2t fiecare muchie\xc2\xa0conecteaz\xc4\x83 un nod din \xc2\xa0cu unul din . Mul\xc8\x9bimile de noduri\xc2\xa0 \xc8\x99i  sunt de obicei numite p\xc4\x83r\xc8\x9bile\xc2\xa0grafului. Echivalent, un graf bipartit este un graf care nu con\xc8\x9bine niciun ciclu\xc2\xa0de lungime impar\xc4\x83._NEWLINE_Cele dou\xc4\x83 mul\xc8\x9bimi\xc2\xa0 \xc8\x99i  pot fi g\xc3\xa2ndite ca o colorare a grafului cu dou\xc4\x83 culori: dac\xc4\x83 se coloreaz\xc4\x83 toate nodurile din \xc2\xa0cu albastru, \xc8\x99i toate nodurile din \xc2\xa0cu verde, fiecare muchie are extremit\xc4\x83\xc8\x9bile de culori diferite, dup\xc4\x83 cum este necesar \xc3\xaen problema color\xc4\x83rii grafului. O astfel de colorare este imposibil\xc4\x83 \xc3\xaen cazul unui graf nebipartit, cum ar fi un triunghi: dup\xc4\x83 ce un nod este colorat albastru \xc8\x99i altul verde, cel de-al treilea v\xc3\xa2rf al triunghiului este conectat la noduri de ambele culori, \xc3\xaempiedic\xc3\xa2nd asignarea oric\xc4\x83rei culori._NEWLINE_Deseori se scrie  pentru a desemna un graf bipartit a c\xc4\x83rui parti\xc8\x9bie are p\xc4\x83r\xc8\x9bile\xc2\xa0 \xc8\x99i , iar\xc2\xa0 este mul\xc8\x9bimea muchiilor din graf. Dac\xc4\x83 un graf bipartit nu este conex, acesta poate avea mai mult de o biparti\xc8\x9bie; \xc3\xaen acest caz, nota\xc8\x9bia\xc2\xa0\xc2\xa0precizeaz\xc4\x83 o anume biparti\xc8\x9bie care poate fi de importan\xc8\x9b\xc4\x83 \xc3\xaentr-o aplica\xc8\x9bie. Dac\xc4\x83 , adic\xc4\x83 dac\xc4\x83 cele dou\xc4\x83 subgrupuri sunt de\xc2\xa0cardinalit\xc4\x83\xc8\x9bi\xc2\xa0egale, atunci\xc2\xa0 se nume\xc8\x99te graf bipartit\xc2\xa0echilibrat. Dac\xc4\x83 toate nodurile de pe aceea\xc8\x99i parte a biparti\xc8\x9biei au acela\xc8\x99i grad, atunci  este numit graf biregulat.\n_START_SECTION_\nTeorema lui K\xc3\xb6nig \xc8\x99i grafurile perfecte\n_START_PARAGRAPH_\n\xc3\x8en grafurile bipartite, dimensiunea acoperirii minime cu noduri\xc2\xa0este egal\xc4\x83 cu dimensiunea cuplajului maxim; aceasta este teorema lui K\xc3\xb6nig. O form\xc4\x83 alternativ\xc4\x83 \xc8\x99i echivalent\xc4\x83 a acestei teoreme este c\xc4\x83 dimensiunea mul\xc8\x9bimii independente maxime\xc2\xa0plus dimensiunea cuplajului maxim este egal\xc4\x83 cu num\xc4\x83rul de noduri. \xc3\x8en orice graf f\xc4\x83r\xc4\x83\xc2\xa0noduri izolate dimensiunea acoperirii minime cu muchii\xc2\xa0plus dimensiunea cuplajului maxim este egal\xc4\x83 cu num\xc4\x83rul de noduri.\xc2\xa0Din combinarea\xc2\xa0aceastei egalit\xc4\x83\xc8\x9bi cu teorema lui K\xc3\xb6nig rezult\xc4\x83 c\xc4\x83, \xc3\xaen grafurile bipartite, dimensiunea acoperirii minime cu muchii este egal\xc4\x83 cu dimensiunea mul\xc8\x9bimii independente maxime, iar dimensiunea acoperirii minime cu muchii plus dimensiunea acoperirii minime cu noduri este egal\xc4\x83 cu num\xc4\x83rul de noduri._NEWLINE_O alt\xc4\x83 clas\xc4\x83 de rezultate asociate implic\xc4\x83\xc2\xa0grafurile perfecte: orice graf bipartit,\xc2\xa0complementul\xc2\xa0oric\xc4\x83rui graf bipartit, graful linie\xc2\xa0al fiec\xc4\x83rui graf bipartit, \xc8\x99i un complement al grafului linie al fiec\xc4\x83rui graf bipartit, sunt toate perfecte. Perfec\xc8\x9biunea grafurilor bipartite este u\xc8\x99or de observat (num\xc4\x83rul lor cromatic\xc2\xa0este doi \xc8\x99i dimensiunea\xc2\xa0clicii maxime\xc2\xa0este tot doi) dar perfec\xc8\x9biunea complementelor\xc2\xa0grafurilor bipartite este mai pu\xc8\x9bin banal\xc4\x83, \xc8\x99i este o alt\xc4\x83 reformulare a teoremei lui K\xc3\xb6nig. Acesta a fost unul dintre rezultatele care au motivat definirea grafurilor perfecte. Perfec\xc8\x9biunea complementelor grafurilor linie ale grafurilor perfecte este \xc3\xaenc\xc4\x83 o alt\xc4\x83 reformulare a teoremei lui K\xc3\xb6nig, \xc8\x99i perfec\xc8\x9biunea grafurilor linie \xc2\xa0ub sube este o reformulare a unei teoreme mai vechi tot a lui K\xc3\xb6nig, conform c\xc4\x83reia orice graf bipartit are o colorare de muchii, folosind num\xc4\x83r de culori egal\xc4\x83 cu gradul maxim._NEWLINE_Conform\xc2\xa0teoremei tari a grafurilor perfecte, grafurile perfecte au o\xc2\xa0caracterizare de graf interzis\xc4\x83\xc2\xa0asem\xc4\x83n\xc4\x83toare cu cea a grafurilor bipartite: un graf este bipartit dac\xc4\x83 \xc8\x99i numai dac\xc4\x83 acesta nu are niciun ciclu impar ca subgraf, \xc8\x99i un graf este perfect dac\xc4\x83 \xc8\x99i numai dac\xc4\x83 acesta nu are niciu ciclu impar \xc8\x99i nici pe\xc2\xa0complementul\xc2\xa0s\xc4\x83u\xc2\xa0ca\xc2\xa0subgraf indus. Grafurile bipartite, grafurile linie ale grafurilor bipartite \xc8\x99i complementele lor formeaz\xc4\x83 patru din cele cinci clase de baz\xc4\x83 ale grafurilor perfecte utilizate \xc3\xaen demonstra\xc8\x9bia teoremei tari a grafurilor perfecte.\n_START_SECTION_\nRela\xc8\x9bia cu hipergrafurile \xc8\x99i cu grafurile orientate\n_START_PARAGRAPH_\nMatricea de biadiacen\xc8\x9b\xc4\x83\xc2\xa0a unui graf bipartit  este o (0,1)-matrice de dimensiune  care are un pentru fiecare pereche de v\xc3\xa2rfuri adiacente \xc8\x99i zero pentru nodurile neadiacente.\xc2\xa0Matricele de biadiacen\xc8\x9b\xc4\x83\xc2\xa0pot fi folosite pentru a descrie echivalen\xc8\x9bele \xc3\xaentre grafurile bipartite, hipergrafuri \xc8\x99i grafuri orientate._NEWLINE_Un hipergraf\xc2\xa0este o structur\xc4\x83 combinatoric\xc4\x83 care, ca \xc8\x99i un graf neorientat, are noduri \xc8\x99i muchii, dar \xc3\xaen care muchiile pot fi mul\xc8\x9bimi arbitrare de noduri, neav\xc3\xa2nd obligatoriu doar dou\xc4\x83 extremit\xc4\x83\xc8\x9bi. Un graf bipartit  poate fi folosit pentru a modela un hipergraf \xc3\xaen care  este mul\xc8\x9bimea de noduri a hipergrafului,  este mul\xc8\x9bimea de hipermuchii, \xc8\x99i  con\xc8\x9bine o muchie de la nod de hipergraf\xc2\xa0 la o muchie de hipergraf\xc2\xa0\xc2\xa0atunci c\xc3\xa2nd  este una din extremit\xc4\x83\xc8\x9bile lui\xc2\xa0. Sub aceast\xc4\x83 coresponden\xc8\x9b\xc4\x83, matricele de biadiacen\xc8\x9b\xc4\x83 ale grafurilor bipartite sunt exact matricele de inciden\xc8\x9b\xc4\x83 corespunz\xc4\x83toare hipergrafurilor. Ca un caz special al acestei coresponden\xc8\x9be \xc3\xaentre grafurile bipartite \xc8\x99i hipergrafuri, orice multigraf\xc2\xa0(un grafic \xc3\xaen care pot exista dou\xc4\x83 sau mai multe muchii \xc3\xaentre acelea\xc8\x99i dou\xc4\x83 noduri) poate fi interpretat ca un hypergraph \xc3\xaen care unele hipermuchii au mul\xc8\x9bimi egale de extremit\xc4\x83\xc8\x9bi, reprezentate printr-un graf bipartit care nu are adiacen\xc8\x9be multiple \xc8\x99i \xc3\xaen care nodurile pe de o parte a biparti\xc8\x9biei au toate\xc2\xa0gradul doi._NEWLINE_Un reinterpretare similar\xc4\x83 a matricelor de adiacen\xc8\x9b\xc4\x83 poate fi folosit\xc4\x83 pentru a ar\xc4\x83ta o coresponden\xc8\x9b\xc4\x83 unu-la-unu \xc3\xaentre\xc2\xa0grafurile orientate (pe un anumit num\xc4\x83r de noduri etichetate, care permit auto-bucle) \xc8\x99i grafurile bipartite echilibrate, cu acela\xc8\x99i num\xc4\x83r de noduri pe ambele laturi ale parti\xc8\x9biei. Pentru c\xc4\x83 matrice de adiacen\xc8\x9b\xc4\x83 a unui graf orientat cu  noduri poate fi orice -matrice de dimensiune , ceea ce se poate reinterpreta ca matricea de adiacen\xc8\x9b\xc4\x83 a unui graf bipartit cu  noduri de fiecare parte a biparti\xc8\x9biei. \xc3\x8en aceast\xc4\x83 construc\xc8\x9bie, graful bipartit este acoperirea bipartit\xc4\x83 dubl\xc4\x83\xc2\xa0a grafului orientat.\n_START_SECTION_\nTestarea bipartitudinii\n_START_PARAGRAPH_\nSe poate verifica dac\xc4\x83 un graf este bipartit, \xc8\x99i calcula fie o doi-colorare (dac\xc4\x83 este bipartit) sau un ciclu impar (dac\xc4\x83 nu este) \xc3\xaen timp liniar, folosind c\xc4\x83utarea \xc3\xaen ad\xc3\xa2ncime. Ideea principal\xc4\x83 este de a atribui fiec\xc4\x83rui nod o culoare diferit\xc4\x83 de culoarea p\xc4\x83rintelui s\xc4\x83u \xc3\xaen arborele de c\xc4\x83utare \xc3\xaen ad\xc3\xa2ncime, atribuind culorile \xc3\xaentr-o\xc2\xa0parcurgere \xc3\xaen preordine\xc2\xa0a arborelui de c\xc4\x83utare \xc3\xaen ad\xc3\xa2ncime. Acest lucru va furniza neap\xc4\x83rat un arbore de acoperire\xc2\xa0\xc3\xaen dou\xc4\x83 culori,\xc2\xa0format fiind din muchiile ce conecteaz\xc4\x83 nodurile la p\xc4\x83rin\xc8\x9bii lor, dar nu poate colora corespunz\xc4\x83tor unele din muchiile din afara arborelui. \xc3\x8entr-un arbore de c\xc4\x83utare \xc3\xaen ad\xc3\xa2ncime, una dintre cele dou\xc4\x83 extremit\xc4\x83\xc8\x9bi ale fiec\xc4\x83rei muchii din afara arborelui este un str\xc4\x83mo\xc8\x99 al celeilalte extremit\xc4\x83\xc8\x9bi, \xc8\x99i atunci c\xc3\xa2nd c\xc4\x83utarea \xc3\xaen ad\xc3\xa2ncimea descoper\xc4\x83 o muchie de acest tip, ar trebui verificat c\xc4\x83 aceste dou\xc4\x83 noduri au culori diferite. Dac\xc4\x83 nu, atunci drumul \xc3\xaen arbore de la str\xc4\x83mo\xc8\x99 la descendent, \xc3\xaempreun\xc4\x83 cu muchia colorat\xc4\x83 eronat, formeaz\xc4\x83 un ciclu impar, care este returnat de algoritm \xc3\xaempreun\xc4\x83 cu rezultatul c\xc4\x83 graficul nu este bipartit. Cu toate acestea, dac\xc4\x83 algoritmul se termin\xc4\x83 f\xc4\x83r\xc4\x83 a detecta un ciclu impar de acest tip, atunci fiecare muchie trebuie s\xc4\x83 fie corect colorat\xc4\x83, \xc8\x99i algoritmul returneaz\xc4\x83 colorarea \xc3\xaempreun\xc4\x83 cu rezultatul c\xc4\x83 graful este bipartit._NEWLINE_Alternativ, o procedur\xc4\x83 similar\xc4\x83 poate fi folosit\xc4\x83 cu o\xc2\xa0c\xc4\x83utare \xc3\xaen l\xc4\x83\xc8\x9bime\xc2\xa0\xc3\xaen loc de c\xc4\x83utare \xc3\xaen ad\xc3\xa2ncime. Din nou, fiecare nod prime\xc8\x99te culoarea opus\xc4\x83 fa\xc8\x9b\xc4\x83 de p\xc4\x83rintele s\xc4\x83u din arborele de parcurgere \xc3\xaen l\xc4\x83\xc8\x9bime. Dac\xc4\x83, atunci c\xc3\xa2nd un nod este colorat, exist\xc4\x83 o muchie care \xc3\xael conecteaz\xc4\x83 de un nod anterior colorat cu aceea\xc8\x99i culoare, atunci aceast\xc4\x83 muchie, \xc3\xaempreun\xc4\x83 cu c\xc4\x83ile din arborele de parcurgere \xc3\xaen l\xc4\x83\xc8\x9bime ce leag\xc4\x83 cele dou\xc4\x83 extremit\xc4\x83\xc8\x9bi ale sale de cel mai mic str\xc4\x83mo\xc8\x99 comun formeaz\xc4\x83 un ciclu impar. Dac\xc4\x83 algoritmul se termin\xc4\x83 f\xc4\x83r\xc4\x83 a g\xc4\x83si un ciclu impar \xc3\xaen acest fel, atunci acesta trebuie s\xc4\x83 fi g\xc4\x83sit o colorare corect\xc4\x83, \xc8\x99i se poate concluziona cu siguran\xc8\x9b\xc4\x83 c\xc4\x83 graful este bipartit._NEWLINE_Pentru grafurile intersec\xc8\x9bie\xc2\xa0de  segmente de linie sau alte forme simple \xc3\xaen planul euclidian, se poate testa dac\xc4\x83 graful este bipartit \xc8\x99i returna ori o doi-colorare, ori un ciclu impar \xc3\xaen timp , chiar dac\xc4\x83 graful \xc3\xaen sine poate avea p\xc3\xa2n\xc4\x83 la\xc2\xa0 muchii.\n_START_SECTION_\nTransversal\xc4\x83 de ciclu impar\n_START_PARAGRAPH_\nTransversala de ciclu impar\xc2\xa0este o problem\xc4\x83 algoritmic\xc4\x83\xc2\xa0NP-complet\xc4\x83\xc2\xa0care cere ca, dat fiind un graf G = (V,E) \xc8\x99i un num\xc4\x83r k, s\xc4\x83 se verifice dac\xc4\x83 exist\xc4\x83 o mul\xc8\x9bime de k noduri a c\xc4\x83ror \xc3\xaendep\xc4\x83rtare din\xc2\xa0G ar face ca graful rezultat s\xc4\x83 fie bipartit.\xc2\xa0Problema este tractabil\xc4\x83 \xc3\xaen parametru fix, \xc3\xaen sensul c\xc4\x83 nu exist\xc4\x83 un algoritm al c\xc4\x83rui timp de func\xc8\x9bionare s\xc4\x83 poat\xc4\x83 fi delimitat printr-o func\xc8\x9bie polinomial\xc4\x83 de dimensiunea grafului \xc3\xaenmul\xc8\x9bit\xc4\x83 cu o func\xc8\x9bie mai mare de k. Mai precis, timpul pentru acest algoritm este O(3\xe1\xb5\x8f mn), de\xc8\x99i \xc3\xaen lucrare acesta nu este men\xc8\x9bionat. Rezultatul lui Reed et al. a fost ob\xc8\x9binut folosind o metod\xc4\x83 complet nou\xc4\x83, care mai t\xc3\xa2rziu a fost numit\xc4\x83\xc2\xa0compresie iterativ\xc4\x83\xc2\xa0\xc8\x99i s-a dovedit a fi un instrument algoritmic extrem de util, mai ales \xc3\xaen domeniul tractabilita\xc8\x9bii \xc3\xaen parametru fix. Acest instrument este considerat acum unul dintre instrumentele fundamentale de algoritmic\xc4\x83 parametrizat\xc4\x83._NEWLINE_Denumirea de\xc2\xa0transversal\xc4\x83 de ciclu impar\xc2\xa0vine de la faptul c\xc4\x83 un graf este bipartit dac\xc4\x83 \xc8\x99i numai dac\xc4\x83 acesta nu are\xc2\xa0cicluri\xc2\xa0impare. Prin urmare, pentru a \xc8\x99terge noduri dintr-un graf, \xc3\xaen scopul de a ob\xc8\x9bine un graf bipartit, este nevoie s\xc4\x83 se \xe2\x80\x9eloveasc\xc4\x83 toate ciclurile impare\xe2\x80\x9d, sau s\xc4\x83 se g\xc4\x83seasc\xc4\x83 o a\xc8\x99a-numit\xc4\x83 mul\xc8\x9bime\xc2\xa0transversal\xc4\x83\xc2\xa0de ciclu impar. \xc3\x8en figur\xc4\x83, se poate observa c\xc4\x83 toate ciclurile impare din graf con\xc8\x9bin nodurile albastre (de jos), prin urmare, eliminarea acestor noduri distruge toate ciclurile impare \xc8\x99i las\xc4\x83 graful bipartit._NEWLINE_Problema\xc2\xa0bipartiz\xc4\x83rii muchiilor\xc2\xa0problema este problema algoritmic\xc4\x83\xc2\xa0de a \xc8\x99terge c\xc3\xa2t mai pu\xc8\x9bine muchii posibil pentru a face graful bipartit \xc8\x99i este, de asemenea, o problem\xc4\x83 important\xc4\x83 \xc3\xaen algoritmica modific\xc4\x83rii grafurilor. Aceast\xc4\x83 problem\xc4\x83 este, de asemenea, tractabil\xc4\x83 \xc3\xaen parametru fix, \xc8\x99i poate fi rezolvat\xc4\x83 \xc3\xaen timp O(2\xe1\xb5\x8f m\xc2\xb2),\xc2\xa0unde k este num\xc4\x83rul de muchii de \xc8\x99ters \xc8\x99i m este num\xc4\x83rul de muchii din graful de intrare.\n_START_SECTION_\nCuplaje\n_START_PARAGRAPH_\nUn\xc2\xa0cuplaj\xc2\xa0\xc3\xaentr-un graf este o submul\xc8\x9bime a muchiilor sale cu proprietatea c\xc4\x83 nu exist\xc4\x83 dou\xc4\x83 care s\xc4\x83 aib\xc4\x83 o extremitate comun\xc4\x83. Se cunosc algoritmi\xc2\xa0\xc3\xaen timp polinomial\xc2\xa0pentru multe\xc2\xa0probleme de cuplaje, inclusiv cuplajul maxim\xc2\xa0(g\xc4\x83sirea unui cuplaj care utilizeaz\xc4\x83 c\xc3\xa2t mai multe muchii posibil), cuplajul de pondere maxim\xc4\x83, \xc8\x99i c\xc4\x83snicia stabil\xc4\x83. \xc3\x8en multe cazuri, problemele de potrivire sunt mai simplu de rezolvat pe grafurile bipartite dec\xc3\xa2t pe cele nebipartite, \xc8\x99i mul\xc8\x9bi algoritmi de cuplaj, cum ar fi algoritmul Hopcroft\xe2\x80\x93Karp\xc2\xa0pentru cardinalitatea maxim\xc4\x83 a cuplajelor func\xc8\x9bioneaz\xc4\x83 corect numai pe intr\xc4\x83ri bipartite._NEWLINE_Ca exemplu simplu, s\xc4\x83 presupunem c\xc4\x83 o mul\xc8\x9bime\xc2\xa0 de oameni sunt \xc3\xaen c\xc4\x83utarea de locuri de munc\xc4\x83 dintr-o mul\xc8\x9bime de  locuri de munc\xc4\x83, dar nu toate persoanele se potrivesc pentru toate locurile de munc\xc4\x83. Aceast\xc4\x83 situa\xc8\x9bie poate fi modelat\xc4\x83 ca un graf bipartit  unde o muchie conecteaz\xc4\x83 fiecare solicitant de loc de munc\xc4\x83 cu fiecare loc de munc\xc4\x83 adecvat. Un\xc2\xa0cuplaj perfect\xc2\xa0descrie un mod de a satisface simultan\xc2\xa0toate solicit\xc4\x83rile de locuri de munc\xc4\x83 \xc8\x99i de a ocupa toate locurile de munc\xc4\x83; teorema c\xc4\x83s\xc4\x83toriilor a lui Hall\xc2\xa0ofer\xc4\x83 o caracterizare a grafurilor bipartite care permit cuplaje perfecte. National Resident Matching Program\xc2\xa0aplic\xc4\x83 metodele de cuplaje pe grafuri pentru a rezolva aceast\xc4\x83 problem\xc4\x83 \xc3\xaentre studen\xc8\x9bii americani la medicin\xc4\x83\xc2\xa0\xc8\x99i posturile de medic rezident \xc3\xaen spitale._NEWLINE_Descompunerea Dulmage\xe2\x80\x93Mendelsohn\xc2\xa0este o descompunere structural\xc4\x83 a grafurilor bipartite, care este util\xc4\x83 \xc3\xaen g\xc4\x83sirea de cuplaje maxime.\n_START_SECTION_\nAlte aplica\xc8\x9bii\n_START_PARAGRAPH_\nGrafurile bipartite sunt utilizate pe scar\xc4\x83 larg\xc4\x83 \xc3\xaen teoria modern\xc4\x83 a codurilor, mai ales pentru a decoda cuvinte de cod primite de pe canal. Grafurile de factorizare\xc2\xa0\xc8\x99i grafurile Tanner\xc2\xa0sunt exemple \xc3\xaen acest sens. Un graf Tanner este un graf bipartit \xc3\xaen care nodurile de o parte a parti\xc8\x9biei reprezint\xc4\x83 cifre dintr-un cuv\xc3\xa2nt de cod, \xc8\x99i nodurile pe de alt\xc4\x83 parte reprezint\xc4\x83 combina\xc8\x9bii de cifre, care sunt de a\xc8\x99teptat s\xc4\x83 aib\xc4\x83 suma zero \xc3\xaentr-un cuv\xc3\xa2nt de cod f\xc4\x83r\xc4\x83 erori. Un graf de factorizare este str\xc3\xa2ns legat\xc2\xa0re\xc8\x9beaua de credin\xc8\x9be\xc2\xa0folosit\xc4\x83 pentru decodarea probabilistic\xc4\x83\xc2\xa0Low-density parity-check code \xc8\x99i codurile turbo._NEWLINE_\xc3\x8en informatic\xc4\x83, o re\xc8\x9bea Petri este un instrument de modelare matematic\xc4\x83 utilizat \xc3\xaen analize \xc8\x99i simul\xc4\x83ri ale sistemelor concurente. Un sistem este modelat ca un graf bipartit cu dou\xc4\x83 mul\xc8\x9bimi de noduri: o mul\xc8\x9bime de \xe2\x80\x9elocuri\xe2\x80\x9d care con\xc8\x9bin resurse, \xc8\x99i o mul\xc8\x9bime de \xe2\x80\x9etranzi\xc8\x9bii\xe2\x80\x9d care genereaz\xc4\x83, transfer\xc4\x83 \xc8\x99i/sau consum\xc4\x83 resurse. Exist\xc4\x83 constr\xc3\xa2ngeri suplimentare pe nodurile \xc8\x99i muchiile care constr\xc3\xa2ng comportamentul sistemului. Re\xc8\x9bele Petri utilizeaz\xc4\x83 propriet\xc4\x83\xc8\x9bile grafurilor orientate bipartite \xc8\x99i alte propriet\xc4\x83\xc8\x9bi pentru a permite demonstra\xc8\x9bii matematice ale comportamentului sistemelor \xc3\xaen timp ce permite \xc8\x99i implementarea de simul\xc4\x83ri ale sistemelor._NEWLINE_\xc3\x8en geometria proiectiv\xc4\x83, grafurile Levi\xc2\xa0sunt o form\xc4\x83 de grafuri bipartite folosite pentru a modela inciden\xc8\x9bele \xc3\xaentre puncte \xc8\x99i linii \xc3\xaentr-o configura\xc8\x9bie. Corespunz\xc4\x83toare propriet\xc4\x83\xc8\x9bilor geomerice ale punctelor \xc8\x99i ale liniilor, acelea ca fiecare dou\xc4\x83 linii s\xc4\x83 se \xc3\xaent\xc3\xa2lneasc\xc4\x83 \xc3\xaen cel mult un punct \xc8\x99i ca orice dou\xc4\x83 puncte s\xc4\x83 fie conectate cu o singur\xc4\x83 linie, grafurile Levi obligatoriu nu con\xc8\x9bin cicluri de lungime patru, deci\xc2\xa0calibrul\xc2\xa0lor trebuie s\xc4\x83 fie cel pu\xc8\x9bin \xc8\x99ase.'