Nothing Special   »   [go: up one dir, main page]

Пређи на садржај

Граф

С Википедије, слободне енциклопедије
(преусмерено са Undirected graph)
Означени граф са 6 чворова и 7 грана

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

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

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

Дефиниције

[уреди | уреди извор]

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

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

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

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

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

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

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

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

Врсте графа

[уреди | уреди извор]

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

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

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

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

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

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

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

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

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

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

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

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

У ивици (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) ∈ V2, xy}, функција инциденције која пресликава сваку ивицу у уређени пар врхова (то јест, ивица је повезана са два различита темена).

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

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

[уреди | уреди извор]

Мешовити граф је граф у коме неке ивице могу бити усмерене, а неке неусмерене. То је уређена тројка 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. 
  2. ^ See:
  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. 

Литература

[уреди | уреди извор]

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

[уреди | уреди извор]