Kodiranje bojama
U informatici i teoriji grafova, metod kodiranja bojama efikasno pronalazi k-čvorova prostih puteva, k-čvorova ciklusa i druge podgrafove zadatog grafa koristeći algoritme verovatnoće. Ovaj metod pokazuje da se mnogi izomorfni problemi podgrafova (NP-kompletni problemi) mogu rešiti u polinomijalnom vremenu.

Teoriju i analizu metoda kodiranja bojama predložili su Noga Alon, Raphael Yuster, i Uri Zwick 1994. godine.

Vremenska složenost 

Sledeći rezultati mogu biti dobijeni metodom kodiranja bojama:

 Za svaku konstantu , ako graf  sadrži prost ciklus , onda se takav ciklus može naći u:
 O() očekivanom vremenu, ili
 O() vremenu najgoreg slučaja, gde je  eksponent množenja matrica.
 Za svaku konstantu , i svaki graf  koji je u nekoj netrivijalnoj familiji grafova, ako  sadrži prost ciklus veličine , onda se takav ciklus može naći u:
 O() očekivanom vremenu, ili
 O() vremenu najgoreg slučaja.
 Ako graf  sadrži podgraf izomorfan ograničenom stabloširinskom grafu koji ima  čvorova, onda se takav podgraf može pronaći u polinomijalnom vremenu.

Metod 
Da bi se pronašao podgraf  datog grafa , gde  može biti put ili ciklus, metoda kodiranja bojama počinje nasumičnim bojanjem svakog čvora grafa  sa  različitih boja, a zatim nalazi šarene kopije od  u obojenom grafu . Graf je šaren ako je svaki čvor u njemu obojen različitim bojama. Ova metoda funkcionise ponavljanjem (1) nasumičnog bojanja grafa i (2) pronalaženjem šarene kopije traženog podgrafa pa će se traženi podgraf pronaći u procesu ponavljanja.

Pretpostavimo da  postaje šarena sa nekom ne-nula verovatnoćom . Iz toga sledi da ako se nasumično bojanje ponavlja  puta, onda se očekuje da  postane šaren. Iako  ima malu vrednost, pokazano je da ako ,  je samo polinomijalno male vrednosti. Pretpostavimo ponovi da postoji algoritam takav da, dati graf  i bojanja koja označavaju svaki čvor grafa  jednom od  boja, nalazi šarenu kopiju , ako ona postoji, za neko izvršno vreme . Onda je očekivano vreme nalaženja kopije  u grafu , ako ista postoji, iznosi .

Primer 

Primer koji nalazi prost ciklus dužine  u grafu . 

Nasumičnim bojanjem, svaki prost ciklus ima verovatnocu  da postane šaren, kako postoji  različitih načina bojanja  čvorova puta, među kojima su  šarenih pojavljivanja. Onda se algoritam (dole opisan), sa vremenom izvršavanja  može koristiti da se pronađe šareni ciklus u nasumično obojanom grafu . Zbog toga je potrebno  ukupnog vremena da se pronađe jednostavan ciklus dužine  grafa .

Algoritam za traženje šarenog ciklusa radi tako što prvo pronalazi sve parove čvorova u V koji su povezani prostim putem dužine k − 1, zatim proverava da li su svaka dva čvora povezana. Pozivanjem funkcije za bojanje  da oboji graf , numerišu se svi skupovi boja  u dva potskupa ,  svaki veličine . Primeti se da  može biti podeljen na  i  shodno tome i  i  označavaju podgraf indukovanih  i  proporcijalno. Zatim se rekurzivno nalazi šareni put dužine  u svakoj od i . Pretpostavimo da Bulove matrice  i  predstavljaju povezanost svakog para čvorova  i  šarenim putem, proporcijalno, i neka  bude matrica koja opisuje susedstva između čvorova  i . Bulov proizvod  daje sve parove čvorova u  koji su povezani šarenim putem dužine . Dakle, rekurzivni odnos množenja matrica je , što obezbeđuje vreme izvršavanja . 

Kako ovaj algoritam pronalazi samo krajnje tačke šarenog puta, postoji i drugi algoritam od Alona i Naora koji pronalazi šarene puteve koji mogu izgrađivati sami sebe.

Otklanjanje slučajnosti 
Otklanjanje nasumičnosti kod kodiranja bojama podrazumeva nabrajanja mogućih boja grafa, takva da slučajnost kod bojanja više nije potrebna. Da bi ciljni podgraf  u grafu  bio otkriven, nabrajanje mora da sadrži bar jedan primer gde je  šaren. Da bi se ovo postiglo, dovoljno je da se nabraja -savršenih familija  heš funkcija od  to . Po definiciji,  je k-savršen za svaki podskup  od  gde je , postoji heš funkcija  takva da je  savršena. Drugim rečima, mora postojati heš funkcija u  koja boji bilo kojih datih  čvorova sa  različitih boja.

Postoji nekoliko različitih pristupa da se izgradi tako savršena heš familija:

 Najbolju eksplicitnu konstrukciju napisali su: Moni Naor, Leonard J. Schulman i Aravind Srinivasan u kojoj se može dobiti familija veličine . Ovaj način ne zahteva da traženi podgraf postoji u originalnom problemu pronalaženja podgrafa.
 Drugu eksplicitnu konstrukciju napisali su Jeanette P. Schmidt i Alan Siegel. Ovde je porodica veličine .
 Još jedna konstrukcija se pojavljuje u originalnom dokumentu Noge Alona. Prvo se napravi k-savršena familija, koja mapira  do , zatim se napravi još jedna k-savršena familija koja mapira  do . U prvom koraku, moguće je konstruisati familiju sa  slučajnih bitova koji su gotovo  mudro nezavisni i prostor potreban za generisanje tih slučajnih bitova može biti mali . U drugom koraku, su Jeanette P. Schmidt i Alan Siegel pokazali da veličina takve -savršene familije može biti . Shodno tome, komponovanjem -savršene familije od oba koraka, može se dobiti -savršena familija veličine  koja mapira od  do .

Upotreba 
Od skoro, kodiranje bojama privlači mnogo pažnje u polju bioinformatike. Jedan od primera je otkrivanje signalnih puteva u protein-protein interakciji. Drugi primer je da se otkrije i prebroji broj motiva u PPI. Proučavanjem oba omogućava dublje razumevanje sličnosti i razlika mnogih bioloških funkcija, procesa i struktura među organizmima.

Zbog velike količine prikupljenih podataka (o genima), potraga puteva i motiva može veoma dugo trajati. Međutim, korišćenjem kodiranja bojama, motivi ili signalni putevi sa  čvorova u mreži  sa  čvorova vertices mogu se naći veoma efikasno, u polinomijalnom vremenu. To omogućava istraživanja složenijih i većih struktura u protein-protein interakcijama. Više detalja se može pronaći.

Literatura 
-{
 Alon, N., Yuster, R., and Zwick, U. 1994. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing (Montreal, Quebec, Canada, May 23–25, 1994)
 Alon, N., Yuster, R., and Zwick, U. 1995. Color-coding. J. ACM 42, 4 (Jul. 1995)
 Coppersmith–Winograd Algorithm
 Naor, M., Schulman, L. J., and Srinivasan, A. 1995. Splitters and near-optimal derandomization. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (October 23–25, 1995)
 Schmidt, J. P. and Siegel, A. 1990. The spatial complexity of oblivious k-probe Hash functions. SIAM J. Comput. 19, 5 (Sep. 1990)
 Naor, J. and Naor, M. 1990. Small-bias probability spaces: efficient constructions and applications. In Proceedings of the Twenty-Second Annual ACM Symposium on theory of Computing (Baltimore, Maryland, United States, May 13–17, 1990)
 Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., and Sahinalp, S. C. 2008. Biomolecular network motif counting and discovery by color coding. Bioinformatics 24, 13 (Jul. 2008)
 Hüffner, F., Wernicke, S., and Zichner, T. 2008. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection. Algorithmica 52, 2 (Aug. 2008)
}-

Графовски алгоритми
U informatici i teoriji grafova , metod kodiranja bojama efikasno pronalazi k-čvorova prostih puteva , k-čvorova ciklusa i druge podgrafove zadatog grafa koristeći algoritme verovatnoće . Ovaj metod pokazuje da se mnogi izomorfni problemi podgrafova ( NP-kompletni problemi ) mogu rešiti u polinomijalnom vremenu . Teoriju i analizu metoda kodiranja bojama predložili su Noga Alon , Raphael Yuster , i Uri Zwick godine . Vremenska složenost Sledeći rezultati mogu biti dobijeni metodom kodiranja bojama : Za svaku konstantu , ako graf sadrži prost ciklus , onda se takav ciklus može naći u : O ( ) očekivanom vremenu , ili O ( ) vremenu najgoreg slučaja , gde je eksponent množenja matrica . Za svaku konstantu , i svaki graf koji je u nekoj netrivijalnoj familiji grafova , ako sadrži prost ciklus veličine , onda se takav ciklus može naći u : O ( ) očekivanom vremenu , ili O ( ) vremenu najgoreg slučaja . Ako graf sadrži podgraf izomorfan ograničenom stabloširinskom grafu koji ima čvorova , onda se takav podgraf može pronaći u polinomijalnom vremenu . Metod Da bi se pronašao podgraf datog grafa , gde može biti put ili ciklus , metoda kodiranja bojama počinje nasumičnim bojanjem svakog čvora grafa sa različitih boja , a zatim nalazi šarene kopije od u obojenom grafu \ . Graf je šaren ako je svaki čvor u njemu obojen različitim bojama . Ova metoda funkcionise ponavljanjemnasumičnog bojanja grafa ipronalaženjem šarene kopije traženog podgrafa pa će se traženi podgraf pronaći u procesu ponavljanja . Pretpostavimo da postaje šarena sa nekom ne-nula verovatnoćom \ . Iz toga sledi da ako se nasumično bojanje ponavlja puta , onda se očekuje da postane šaren . Iako ima malu vrednost , pokazano je da ako , je samo polinomijalno male vrednosti . Pretpostavimo ponovi da postoji algoritam takav da , dati graf i bojanja koja označavaju svaki čvor grafa jednom od boja , nalazi šarenu kopiju , ako ona postoji , za neko izvršno vreme \ . Onda je očekivano vreme nalaženja kopije u grafu , ako ista postoji , iznosi \ . Primer Primer koji nalazi prost ciklus dužine u grafu \ . Nasumičnim bojanjem , svaki prost ciklus ima verovatnocu da postane šaren , kako postoji različitih načina bojanja čvorova puta , među kojima su šarenih pojavljivanja . Onda se algoritam ( dole opisan ) , sa vremenom izvršavanja može koristiti da se pronađe šareni ciklus u nasumično obojanom grafu \ . Zbog toga je potrebno ukupnog vremena da se pronađe jednostavan ciklus dužine grafa \ . Algoritam za traženje šarenog ciklusa radi tako što prvo pronalazi sve parove čvorova u V koji su povezani prostim putem dužine k − 1 , zatim proverava da li su svaka dva čvora povezana . Pozivanjem funkcije za bojanje da oboji graf , numerišu se svi skupovi boja u dva potskupa , svaki veličine \ . Primeti se da može biti podeljen na i shodno tome i i označavaju podgraf indukovanih i proporcijalno . Zatim se rekurzivno nalazi šareni put dužine u svakoj od i \ . Pretpostavimo da Bulove matrice i predstavljaju povezanost svakog para čvorova i šarenim putem , proporcijalno , i neka bude matrica koja opisuje susedstva između čvorova i \ . Bulov proizvod daje sve parove čvorova u koji su povezani šarenim putem dužine \ . Dakle , rekurzivni odnos množenja matrica je , što obezbeđuje vreme izvršavanja \ . Kako ovaj algoritam pronalazi samo krajnje tačke šarenog puta , postoji i drugi algoritam od Alona i Naora koji pronalazi šarene puteve koji mogu izgrađivati sami sebe . Otklanjanje slučajnosti Otklanjanje nasumičnosti kod kodiranja bojama podrazumeva nabrajanja mogućih boja grafa , takva da slučajnost kod bojanja više nije potrebna . Da bi ciljni podgraf u grafu bio otkriven , nabrajanje mora da sadrži bar jedan primer gde je šaren . Da bi se ovo postiglo , dovoljno je da se nabraja -savršenih familija heš funkcija od to \ . Po definiciji , je k-savršen za svaki podskup od gde je , postoji heš funkcija takva da je savršena . Drugim rečima , mora postojati heš funkcija u koja boji bilo kojih datih čvorova sa različitih boja . Postoji nekoliko različitih pristupa da se izgradi tako savršena heš familija : Najbolju eksplicitnu konstrukciju napisali su : Moni Naor , Leonard J . Schulman i Aravind Srinivasan u kojoj se može dobiti familija veličine \ . Ovaj način ne zahteva da traženi podgraf postoji u originalnom problemu pronalaženja podgrafa . Drugu eksplicitnu konstrukciju napisali su Jeanette P . Schmidt i Alan Siegel . Ovde je porodica veličine \ . Još jedna konstrukcija se pojavljuje u originalnom dokumentu Noge Alona . Prvo se napravi k-savršena familija , koja mapira do , zatim se napravi još jedna k-savršena familija koja mapira do \ . U prvom koraku , moguće je konstruisati familiju sa slučajnih bitova koji su gotovo mudro nezavisni i prostor potreban za generisanje tih slučajnih bitova može biti mali \ . U drugom koraku , su Jeanette P . Schmidt i Alan Siegel pokazali da veličina takve -savršene familije može biti \ . Shodno tome , komponovanjem -savršene familije od oba koraka , može se dobiti -savršena familija veličine koja mapira od do \ . Upotreba Od skoro , kodiranje bojama privlači mnogo pažnje u polju bioinformatike . Jedan od primera je otkrivanje signalnih puteva u protein-protein interakciji . Drugi primer je da se otkrije i prebroji broj motiva u PPI . Proučavanjem oba omogućava dublje razumevanje sličnosti i razlika mnogih bioloških funkcija , procesa i struktura među organizmima . Zbog velike količine prikupljenih podataka ( o genima ) , potraga puteva i motiva može veoma dugo trajati . Međutim , korišćenjem kodiranja bojama , motivi ili signalni putevi sa čvorova u mreži sa čvorova vertices mogu se naći veoma efikasno , u polinomijalnom vremenu . To omogućava istraživanja složenijih i većih struktura u protein-protein interakcijama . Više detalja se može pronaći . Literatura - { Alon , N . , Yuster , R . , and Zwick , U . Color-coding : a new method for finding simple paths , cycles and other small subgraphs within large graphs . In Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing ( Montreal , Quebec , Canada , May25 , Alon , N . , Yuster , R . , and Zwick , U . Color-coding . J. ACM( Jul . Coppersmith–Winograd Algorithm Naor , M . , Schulman , L. J . , and Srinivasan , A . Splitters and near-optimal derandomization . In Proceedings of theh Annual Symposium on Foundations of Computer Science ( October25 , Schmidt , J. P. and Siegel , A . The spatial complexity of oblivious k-probe Hash functions . SIAM J. Comput.( Sep . Naor , J. and Naor , M . Small-bias probability spaces : efficient constructions and applications . In Proceedings of the Twenty-Second Annual ACM Symposium on theory of Computing ( Baltimore , Maryland , United States , May17 , Alon , N . , Dao , P . , Hajirasouliha , I . , Hormozdiari , F . , and Sahinalp , S. C . Biomolecular network motif counting and discovery by color coding . Bioinformatics( Jul. Hüffner , F . , Wernicke , S . , and Zichner , T . Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection . Algorithmica( Aug . }- Графовски алгоритми