Граф

За друге употребе, погледајте страницу Граф (вишезначна одредница).

Граф је апстрактни математички објекат, а цртеж који се састоји од тачака и линија је само геометријска представа графа. Међутим, уобичајено је да се таква слика назива графом. Како је граф састављен из тачака и линија, које спајају по две тачке, онда је одатле могуће извести и формалну дефиницију графа. Граф је структура која се састоји од скупа објеката у којима су неки парови објеката на неки начин „повезани“. Објекти одговарају математичким апстракцијама које се називају врхови (који се такође називају чворови или тачке) и сваки од повезаних парова темена се назива ивица (такође се назива веза или линија).^[1] Типично, граф се приказује у дијаграмском облику као скуп тачака или кругова за врхове, спојених линијама или кривинама за ивице. Графови су један од предмета проучавања у дискретној математици.

Означени граф са 6 чворова и 7 грана

Оваква уопштена дефиниција омогућује да граф примењујемо не само у математици, већ и у информатици, електротехници и техници уопште, а такође и у хемији, лингвистици, економији и многим другим областима.

Графови су основни предмет који проучава теорија графова. Реч „граф“ је у овом смислу први употребио Џ. Џ. Силвестер 1878. године у директној вези између математике и хемијске структуре (оно што је назвао хемијско-графичком сликом).^[2][3]

Дефиниције

Како је већ претходно напоменуто у дефинисању појма графа се користимо појмовима из теорије скупова. Тако једна строга дефиниција гласи

Граф је уређени пар G = (X, ρ), где је X коначан непразан скуп, а ρ бинарна релација у Х.

Док једна друга допушта и бесконачан број чворова (и грана)^[4]

Нека је X непразан скуп и ρ бинарна релација у Х. Уређени пар G = (X, ρ) назива се граф. Елементи скупа Х су чворови графа, а елементи скупа ρ гране графа.

Појам графа је могуће генералисати ако прихватимо да је могуће да постоји више од једне гране исте оријентације, односно да могу постојати и вишеструке петље. Такав граф се онда зове мултиграф. Обичан граф је онда посебан случај мултиграфа.

Дефиниција таквог мултиграфа би била

Нека је X непразан скуп и U једна комбинација са понављањем скупа Х². Уређени пар G = (X, U) назива се мултиграф.

У сваком случају, граф је задат ако су задата два скупа, скуп чворова и скуп грана.

Врсте графа

Граф који има коначан број чворова се зове коначан граф. Аналогно, граф са бесконачним бројем чворова се зове бесконачан граф.

Ако је свеједно да ли је грана графа АБ исто што и БА и то важи за све гране графа, онда је ρ симетрична релација, а граф је симетричан или неоријентисан. Код таквих графова се изостављају стрелице на цртежу.

Ако све гране на графу имају стрелице, односно оријентисане су, тада је цео граф оријентисан или антисиметричан. Повезан граф је такав неоријентисани граф код кога се било која два чвора могу повезати путем. Ако постоје два чвора која се не могу повезати, граф је неповезан.

Мултиграф је генерализација која омогућава да више ивица има исти пар крајњих тачака. У неким текстовима мултиграфови се једноставно називају графовима.^[5][6]

Понекад је дозвољено да графови садрже петље, које су ивице које спајају врх са самим собом. За дозвољавање петљи, горња дефиниција мора бити промењена дефинисањем ивица као мултискупова два врха уместо два скупа. Овакви генерализовани графови се називају графови са петљама или једноставно графови када је из контекста јасно да су петље дозвољене.

Генерално, скуп темена V треба да је коначан; ово имплицира да је скуп ивица такође коначан. Бесконачни графови се понекад разматрају, али се чешће посматрају као посебна врста бинарне релације, пошто се већина резултата на коначним графовима не протеже на бесконачан случај, или им је потребан прилично другачији доказ.

Усмерени граф

Главни чланак: Усмерени граф

Усмерени граф са три врха и четири усмерене ивице (двострука стрелица представља ивицу у оба смера)

Усмерени граф или диграф је граф у коме ивице имају оријентације.

У једном ограниченом, али веома разумном смислу термина,^[7] усмерени граф је пар G = (V, E) који садржи:

• V, скуп темена (која се називају и чворови или тачке);
• E ⊆ {(x,y) | (x,y) ∈ V², x ≠ y},, скуп ивица (који се називају и усмерене ивице, усмерене везе, усмерене линије, стрелице или лукови) који су уређени парови врхова (то јест, ивица је повезана са два различита темена).

Да би се избегла двосмисленост, овај тип објекта се може назвати управо усмереним једноставним графом.

У ивици (x,y) усмереној од x до y, темена x и y се називају крајњим тачкама ивице, x репом ивице и y главом ивице. За ивицу се каже да спаја x и y и да је инцидентна на x и на y. Теме може постојати у графу и не припадати ивици. Ивица (y,x) се назива обрнута ивица (x,y). Више ивица, које нису дозвољене према горњој дефиницији, су две или више ивица са истим репом и истом главом.

У још једном општем смислу термина који дозвољава више ивица,^[7] усмерени граф је уређена тројка G = (V, E, ϕ) која садржи:

• V, скуп темена (који се називају чворови или тачке);
• E, скуп ивица (који се називају усмерене ивице, усмерене везе, усмерене линије, стрелице или лукови);
• ϕ : E → {(x,y) | (x,y) ∈ V², x ≠ y}, функција инциденције која пресликава сваку ивицу у уређени пар врхова (то јест, ивица је повезана са два различита темена).

Да би се избегла двосмисленост, овај тип објекта се може назвати управо усмереним мултиграфом.

Мешовити граф

Главни чланак: Мешовити граф

Мешовити граф је граф у коме неке ивице могу бити усмерене, а неке неусмерене. То је уређена тројка G = (V, E, A) за мешовити једноставан граф и G = (V, E, A, ϕ_E, ϕ_A) за мешовити мултиграф са V, E (неусмерене ивице), A (усмерене ивице), ϕ_E и ϕ_A дефинисане као горе. Усмерени и неусмерени графови су посебни случајеви.

Пондерисани граф

Пондерисани граф са десет врхова и дванаест ивица

Пондерисани граф или мрежа^[8][9] је граф у коме је свакој ивици додељен број (тежина).^[10] Такве тежине могу представљати, на пример, трошкове, дужине или капацитете, у зависности од проблема. Такви графови се јављају у многим контекстима, на пример у проблемима најкраће путање као што је проблем трговачког путника.

Појмови

Грана графа која полази из једног чвора и завршава у истом чвору се зове петља.

Неповезан граф се састоји од бар два неповезана дела. Такви делови се зову компоненте повезаности графа.

Ако се удаљавањем једног чвора из графа он распада, односно број компонената повезаности се повећава, тада је тај чвор артикулациони чвор.

Ако се удаљавањем једне гране граф распада, грана се зове мост графа.

Степен чвора графа је број грана графа који имају крај у чвору. Ако грана спаја чвор са самим собом, онда се она рачуна два пута.

Грана која спаја чвор са степеном један је висећа грана.

Види још

• Теорија графова
• Хиперграф
• Планарни граф

Референце

1. Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. изд.). New York: Dover Pub. стр. 19. ISBN 978-0-486-67870-2. Приступљено 8. 8. 2012. „A graph is an object consisting of two sets called its vertex set and its edge set.”CS1 одржавање: Формат датума (веза)
2. See:

   • Sylvester, J. J. (1878). „Chemistry and Algebra”. Nature. 17 (432): 284. Bibcode:1878Natur..17..284S. S2CID 26451061. doi:10.1038/017284a0.
   • Sylvester, J. J. (1878). „On an Application of the New Atomic Theory to the Graphical Representation of the Invariants and Covariants of Binary Quantics, with Three Appendices”. American Journal of Mathematics. 1 (1): 64—104. JSTOR 2369436. doi:10.2307/2369436.
3. Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. стр. 35. ISBN 978-1-58488-090-5.
4. Дискретне математичке структуре, Драгош Цветковић
5. Bender & Williamson 2010, стр. 149.
6. Graham et al., p. 5.
7. Bender & Williamson 2010, стр. 161.
8. Strang, Gilbert (2005), Linear Algebra and Its Applications (4th изд.), Brooks Cole, ISBN 978-0-03-010567-8^{[мртва веза]}
9. Lewis, John (2013), Java Software Structures (4th изд.), Pearson, стр. 405, ISBN 978-0133250121
10. Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics (International student изд.). Boston: PWS-KENT Pub. Co. стр. 463. ISBN 978-0-53492-373-0. „A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e.”

Литература

• Balakrishnan, V. K. (1997). Graph Theory (1st изд.). 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 (на језику: француски). Paris: Dunod.
• Biggs, Norman (1993). Algebraic Graph Theory (2nd изд.). Cambridge University Press. ISBN 978-0-521-45897-9.
• Bollobás, Béla (2002). Modern Graph Theory (1st изд.). Springer. ISBN 978-0-387-98488-9.
• Diestel, Reinhard (2005). Graph Theory (3rd изд.). 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 изд.). Chapman & Hall/CRC. ISBN 978-1-58488-291-6.
• Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. изд.). New York: Dover Publications. ISBN 978-0-486-67870-2. Приступљено 8. 8. 2012.CS1 одржавање: Формат датума (веза)
• 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.  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 изд.), 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, стр. 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.

Спољашње везе

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