Graf

Za druge upotrebe, pogledajte stranicu Graf (višeznačna odrednica).

Označeni graf sa 6 čvorova i 7 grana

Graf je apstraktni matematički objekat, a crtež koji se sastoji od tačaka i linija je samo geometrijska predstava grafa. Međutim, uobičajeno je da se takva slika naziva grafom. Kako je graf sastavljen iz tačaka i linija, koje spajaju po dve tačke, onda je odatle moguće izvesti i formalnu definiciju grafa. Graf je struktura koja se sastoji od skupa objekata u kojima su neki parovi objekata na neki način „povezani“. Objekti odgovaraju matematičkim apstrakcijama koje se nazivaju vrhovi (koji se takođe nazivaju čvorovi ili tačke) i svaki od povezanih parova temena se naziva ivica (takođe se naziva veza ili linija). Tipično, graf se prikazuje u dijagramskom obliku kao skup tačaka ili krugova za vrhove, spojenih linijama ili krivinama za ivice. Grafovi su jedan od predmeta proučavanja u diskretnoj matematici.

Ovakva uopštena definicija omogućuje da graf primenjujemo ne samo u matematici, već i u informatici, elektrotehnici i tehnici uopšte, a takođe i u hemiji, lingvistici, ekonomiji i mnogim drugim oblastima.

Grafovi su osnovni predmet koji proučava teorija grafova. Reč „graf“ je u ovom smislu prvi upotrebio Dž. Dž. Silvester 1878. godine u direktnoj vezi između matematike i hemijske strukture (ono što je nazvao hemijsko-grafičkom slikom).

Definicije

Kako je već prethodno napomenuto u definisanju pojma grafa se koristimo pojmovima iz teorije skupova. Tako jedna stroga definicija glasi

Graf je uređeni par G = (X, ρ), gde je X konačan neprazan skup, a ρ binarna relacija u H.

Dok jedna druga dopušta i beskonačan broj čvorova (i grana)

Neka je X neprazan skup i ρ binarna relacija u H. Uređeni par G = (X, ρ) naziva se graf. Elementi skupa H su čvorovi grafa, a elementi skupa ρ grane grafa.

Pojam grafa je moguće generalisati ako prihvatimo da je moguće da postoji više od jedne grane iste orijentacije, odnosno da mogu postojati i višestruke petlje. Takav graf se onda zove multigraf. Običan graf je onda poseban slučaj multigrafa.

Definicija takvog multigrafa bi bila

Neka je X neprazan skup i U jedna kombinacija sa ponavljanjem skupa H². Uređeni par G = (X, U) naziva se multigraf.

U svakom slučaju, graf je zadat ako su zadata dva skupa, skup čvorova i skup grana.

Vrste grafa

Graf koji ima konačan broj čvorova se zove konačan graf. Analogno, graf sa beskonačnim brojem čvorova se zove beskonačan graf.

Ako je svejedno da li je grana grafa AB isto što i BA i to važi za sve grane grafa, onda je ρ simetrična relacija, a graf je simetričan ili neorijentisan. Kod takvih grafova se izostavljaju strelice na crtežu.

Ako sve grane na grafu imaju strelice, odnosno orijentisane su, tada je ceo graf orijentisan ili antisimetričan. Povezan graf je takav neorijentisani graf kod koga se bilo koja dva čvora mogu povezati putem. Ako postoje dva čvora koja se ne mogu povezati, graf je nepovezan.

Multigraf je generalizacija koja omogućava da više ivica ima isti par krajnjih tačaka. U nekim tekstovima multigrafovi se jednostavno nazivaju grafovima.

Ponekad je dozvoljeno da grafovi sadrže petlje, koje su ivice koje spajaju vrh sa samim sobom. Za dozvoljavanje petlji, gornja definicija mora biti promenjena definisanjem ivica kao multiskupova dva vrha umesto dva skupa. Ovakvi generalizovani grafovi se nazivaju grafovi sa petljama ili jednostavno grafovi kada je iz konteksta jasno da su petlje dozvoljene.

Generalno, skup temena V treba da je konačan; ovo implicira da je skup ivica takođe konačan. Beskonačni grafovi se ponekad razmatraju, ali se češće posmatraju kao posebna vrsta binarne relacije, pošto se većina rezultata na konačnim grafovima ne proteže na beskonačan slučaj, ili im je potreban prilično drugačiji dokaz.

Usmereni graf

Glavni članak: Usmereni graf

Usmereni graf sa tri vrha i četiri usmerene ivice (dvostruka strelica predstavlja ivicu u oba smera)

Usmereni graf ili digraf je graf u kome ivice imaju orijentacije.

U jednom ograničenom, ali veoma razumnom smislu termina, usmereni graf je par G = (V, E) koji sadrži:

• V, skup temena (koja se nazivaju i čvorovi ili tačke);
• E ⊆ {(x,y) | (x,y) ∈ V², x ≠ y},, skup ivica (koji se nazivaju i usmerene ivice, usmerene veze, usmerene linije, strelice ili lukovi) koji su uređeni parovi vrhova (to jest, ivica je povezana sa dva različita temena).

Da bi se izbegla dvosmislenost, ovaj tip objekta se može nazvati upravo usmerenim jednostavnim grafom.

U ivici (x,y) usmerenoj od x do y, temena x i y se nazivaju krajnjim tačkama ivice, x repom ivice i y glavom ivice. Za ivicu se kaže da spaja x i y i da je incidentna na x i na y. Teme može postojati u grafu i ne pripadati ivici. Ivica (y,x) se naziva obrnuta ivica (x,y). Više ivica, koje nisu dozvoljene prema gornjoj definiciji, su dve ili više ivica sa istim repom i istom glavom.

U još jednom opštem smislu termina koji dozvoljava više ivica, usmereni graf je uređena trojka G = (V, E, ϕ) koja sadrži:

• V, skup temena (koji se nazivaju čvorovi ili tačke);
• E, skup ivica (koji se nazivaju usmerene ivice, usmerene veze, usmerene linije, strelice ili lukovi);
• ϕ : E → {(x,y) | (x,y) ∈ V², x ≠ y}, funkcija incidencije koja preslikava svaku ivicu u uređeni par vrhova (to jest, ivica je povezana sa dva različita temena).

Da bi se izbegla dvosmislenost, ovaj tip objekta se može nazvati upravo usmerenim multigrafom.

Mešoviti graf

Glavni članak: Mešoviti graf

Mešoviti graf je graf u kome neke ivice mogu biti usmerene, a neke neusmerene. To je uređena trojka G = (V, E, A) za mešoviti jednostavan graf i G = (V, E, A, ϕ_E, ϕ_A) za mešoviti multigraf sa V, E (neusmerene ivice), A (usmerene ivice), ϕ_E i ϕ_A definisane kao gore. Usmereni i neusmereni grafovi su posebni slučajevi.

Ponderisani graf

Ponderisani graf sa deset vrhova i dvanaest ivica

Ponderisani graf ili mreža je graf u kome je svakoj ivici dodeljen broj (težina). Takve težine mogu predstavljati, na primer, troškove, dužine ili kapacitete, u zavisnosti od problema. Takvi grafovi se javljaju u mnogim kontekstima, na primer u problemima najkraće putanje kao što je problem trgovačkog putnika.

Pojmovi

Grana grafa koja polazi iz jednog čvora i završava u istom čvoru se zove petlja.

Nepovezan graf se sastoji od bar dva nepovezana dela. Takvi delovi se zovu komponente povezanosti grafa.

Ako se udaljavanjem jednog čvora iz grafa on raspada, odnosno broj komponenata povezanosti se povećava, tada je taj čvor artikulacioni čvor.

Ako se udaljavanjem jedne grane graf raspada, grana se zove most grafa.

Stepen čvora grafa je broj grana grafa koji imaju kraj u čvoru. Ako grana spaja čvor sa samim sobom, onda se ona računa dva puta.

Grana koja spaja čvor sa stepenom jedan je viseća grana.

Vidi još

• Teorija grafova
• Hipergraf
• Planarni graf

Literatura

• Balakrishnan, V. K. (1997). Graph Theory (1st izd.). McGraw-Hill. ISBN 978-0-07-005489-9. 
• Bang-Jensen, J.; Gutin, G. (2000). Digraphs: Theory, Algorithms and Applications. Springer. 
• Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. 
• Berge, Claude (1958). Théorie des graphes et ses applications (na jeziku: francuski). Paris: Dunod. 
• Biggs, Norman (1993). Algebraic Graph Theory (2nd izd.). Cambridge University Press. ISBN 978-0-521-45897-9. 
• Bollobás, Béla (2002). Modern Graph Theory (1st izd.). Springer. ISBN 978-0-387-98488-9. 
• Diestel, Reinhard (2005). Graph Theory (3rd izd.). Berlin, New York: Springer-Verlag. ISBN 978-3-540-26183-4. 
• Graham, R.L.; Grötschel, M.; Lovász, L. (1995). Handbook of Combinatorics. MIT Press. ISBN 978-0-262-07169-7. 
• Gross, Jonathan L.; Yellen, Jay (1998). Graph Theory and Its Applications. CRC Press. ISBN 978-0-8493-3982-0. 
• Gross, Jonathan L.; Yellen, Jay (2003). Handbook of Graph Theory. CRC. ISBN 978-1-58488-090-5. 
• Harary, Frank (1995). Graph Theory. Addison Wesley Publishing Company. ISBN 978-0-201-41033-4. 
• Iyanaga, Shôkichi; Kawada, Yukiyosi (1977). Encyclopedic Dictionary of Mathematics. MIT Press. ISBN 978-0-262-09016-2. 
• Zwillinger, Daniel (2002). CRC Standard Mathematical Tables and Formulae (31st izd.). Chapman & Hall/CRC. ISBN 978-1-58488-291-6. 
• Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. izd.). New York: Dover Publications. ISBN 978-0-486-67870-2. Pristupljeno 8. 8. 2012. CS1 održavanje: Format datuma (veza)
• Bang-Jensen, Jørgen; Gutin, Gregory (2000), Digraphs: Theory, Algorithms and Applications, Springer, ISBN 1-85233-268-9 
  (the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009. ISBN 1-84800-997-6.).
• Bang-Jensen, Jørgen; Gutin, Gregory (2018), Classes of Directed Graphs, Springer, ISBN 978-3319718408 .
• Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7 .
• Diestel, Reinhard (2005), Graph Theory (3rd izd.), Springer, ISBN 3-540-26182-6  (the electronic 3rd edition is freely available on author's site).
• Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley .
• Beck, M.; Blado, D.; Crawford, J.; Jean-Louis, T.; Young, M. (2013), „On weak chromatic polynomials of mixed graphs”, Graphs and Combinatorics, 31: 91—98, S2CID 253888441, arXiv:1210.4634 , doi:10.1007/s00373-013-1381-1 .
• Cowell, Robert G.; Dawid, A. Philip; Lauritzen, Steffen L.; Spiegelhalter, David J. (1999), Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks, Springer-Verlag New York, str. 27, ISBN 0-387-98767-3 
• Hansen, Pierre; Kuplinsky, Julio; de Werra, Dominique (1997), „Mixed graph colorings”, Mathematical Methods of Operations Research, 45 (1): 145—160, MR 1435900, S2CID 206790816, doi:10.1007/BF01194253 .
• Ries, B. (2007), „Coloring some classes of mixed graphs”, Discrete Applied Mathematics, 155 (1): 1—6, MR 2281351, doi:10.1016/j.dam.2006.05.004 .

Spoljašnje veze

• Weisstein, Eric W. „Graph”. MathWorld. 
• Number of directed graphs (or directed graphs) with n nodes from On-Line Encyclopedia of Integer Sequences