Bipartitna dimenzija

U matematičkim oblastima teorije grafova i kombinatorne optimizacije, **bipartitna dimenzija** ili **biklikni pokrivač broja** grafa *G*&nbsp;=&nbsp;(*V*,&nbsp;*E*) je minimalan broj biklika (to je kompletni bipartitni podgraf), koji bi trebalo da pokrije sve grane u *E*. Kolekcija bikliknih pokrivača koji pokrivaju sve grane u *G* se zove **biklikni pokrivač grana**, ili ponekad **biklikni pokrivač**. Bipartitna dimenzija u *G* je često označena simbolom *d*(*G*).

## Primer
Primeri bikliknog pokrivača grana su dati u sledećim dijagramima:


File:Graph K3 3.png|Bipartitni graf...
Bipartite-dimension-biclique-cover.svg|...i pokrivenost sa četiri biklika
File:Zarankiewicz FigureC.png|crveni biklik pokrivenosti
File:Dilworth-via-König.svg|plavi biklik pokrivenosti
Bipartite-dimension-green-biclique.svg|zeleni biklik pokrivenosti
File:K 3 4.png|crni biklik pokrivenosti


## Formule za bipartitne dimenzije za neki graf

Biklikna dimenzije za kompletan graf od *n* čvorova K_n je \lceil \log_2 n\rceil . Bipartitna dimenzija krunskog grafa sa *2n* čvora jednak je \sigma(n) gde je
:\sigma(n)=\min \left\{\,k \mid n \le \binom{k}{\lfloor k/2 \rfloor} \,\right\}
inverzna funkcija centralnog binomnog koeficijenta (). Fišburn i Hamer () su definisali bipartitnu dimenziju za neke posebne grafove. Na primer, put P_n ima d(P_n) = \lfloor n/2 \rfloor i ciklus C_n ima d(C_n)=\lceil n/2\rceil.

## Izračunavanje bipartitne dimenzije

Zadatak izračunavanja bipartitne dimenzije za dati graf *G* je problem optimizacije. Problem rešavanja bipartitne dimenzije može se formulisati kao:

PRIMER: graf G=(V,E) i pozitivan ceo broj k.
PITANJE: Da li *G* zaista ima biklikni prekrivač grana koji sadrži najviše k biklika?

Ovaj problem se javlja kao problem **GT18** u knjizi Gerija i Džonsona o '''NP'''-kompletnosti, i dosta je direktna reformulacija drugog problema rešavanja porodice ograničenog skupa.

Bazni problem se pojavljuje kao problem **SP7** u knjizi Gerija i Džonsona. Ovde, za porodicu \mathcal{S}=\{S_1,\ldots,S_n\} podskupova ograničenog skupa \mathcal{U}, **osnovni skup** za \mathcal{S} je još jedna porodica podskupova \mathcal{B} = \{B_1,\ldots,B_\ell\} od \mathcal{U} tako da svaki skup S_i kao unija nekih osnovnih elemenata iz \mathcal{B}. Skup osnovnog problema se sada prikazuje ovako:

PRIMER: Ograničeni skup \mathcal{U}, porodica \mathcal{S}=\{S_1,\ldots,S_n\} podskupova \mathcal{U} i pozitivan ceo broj *k*.
PITANJE: Da li postoji osnovni skup ne veći od k za \mathcal{S}?

Ovaj problem je dokazan da je '''NP'''-kompletan od strane Orlina (), čak i za bipartitne grafove. Stokmejer () je ranije dokazao da je **NP**-kompletnost formula osnovnog baznog problema. Problem ostaje **NP**-težak, čak i ako ograničimo našu pažnju na bipartitne grafove čija je bipartitna dimenzija zagarantovana da bude najviše O(\log\,\!n), gde *n* označava veličinu datog problema (). Sa pozitivne strane, problem je rešiv u polinomijalnom vremenu na bipartitnom *domino-slobodnim grafovima* ().

Što se tiče postojanja približnih algoritama, Simon () je dokazao da problem ne može biti lepo objašnjen (ako se pretpostavi da je '''P'''&nbsp;≠&nbsp;'''NP'''). Zaista, bipartitnu dimenziju je **NP**-težak približio unutar |V|^{1/3-\epsilon} za svako ustaljeno \epsilon>0, već za bipartitne grafove ().
U suprotnosti sa time, dokazuje da je problem prilagodljiv ustaljenim parametrima je vežba dizajniranja jezgrovitih algoritama, kako se pojavljuje u udžbeniku Daunija i Felousa (). Flajšner, Mudžuni i Zajder () takođe su obezbedili konkretnu granicu veličine rezultujećeg jezgra, što je u međuvremenu unapredio Nor et al (). Zapravo, za dati bipartitni graf sa *n* čvorova, može se na vreme zaključiti da je O(f(k))+n^3 sa f(k) = 2^{k2^{k-1}+3k} nebitno da li je njegova bipartitna dimenzija najviše *k* ().

## Aplikacije
Problem određivanja bipartitne dimenzije grafa se pojavljuje u raznim kontekstima računarstva. Na primer, u računarskim sistemima, različitim korisnicima sistema može biti dozvoljen ili odbijen pristup raznim resursima. U sistemu za kontrilu pristupa] zasnovanog na ulozi, uloga snabdeva pravo pristupa skupu resursa. Korisnik može da poseduje *višestruke uloge* i ima dozvolu da pristupi svim resursima koje mu odobravaju neke od njegovih uloga. Takođe, uloga može biti u vlasništvu više korisnika. Problem sa ulogama jeste naći minimalni skup resursa, tako da sve uloge svih korisnika pružaju pristup svim naznačenim resursima. Skup korisnika zajedno sa skupom resursa u sistemu prirodne indukcije bipartitni graf, čije grane predstavljaju dozvole. Svaki biklik u svom grafu je potencijalna uloga, a optimalno rešenje glavnog problema je upravo minimalni biklik pokrivača grana ().

Slični scenario se može naći i u kompjuterskoj bezbednosti, tačnije u emitovanju. U tom slučaju, više poruka mora biti pojedinačno poslato kompletu prijemnika, preko neproverenog kanala. Svaka poruka mora da bude kodirana korišćenjem nekog *kriptografskog ključa* poznatog samo onim prijemnicima kojima su namenjene. Svaki prijemnik može imati više *ključeva za šifrovanje*, a svaki ključ će biti raspodeljen između više prijemnika. Problem optimalnog ključa jeste pronaći minimalni skup ključeva za šifrovanje za obezbeđivanje sigurnog prenosa. Kao što je gore navedeno, problem se može podesiti pomoću bipartitnog grafa čiji se minimalni broj bikliknih prekrivača grana podudara sa reševanjem za optimalni problem pronalaženja ključa ().

Drugačija aplikacija može se naći u biologiji, gde se minimalni broj bikliknih pokrivenosti grana koristi u matematičkim obrascima leukocitnog antigena kod ljudi (HLA) ().

## Reference
* 
* .
* .
* .
* .
* .
* .
* .
* .
* .
* .
* 
* .
* .
* .
* .

## Vanjske veze
*  Blog entry about bipartite dimension  (David Eppstein)