Графовите се математички структури кои се користат за моделирање на широк дијапазон реални ситуации во кои е потребно да се изразат релациите/ врски помеѓу објектите. На пример, со помош на граф можеме да претставиме како одредени лица се поврзани меѓусебно на социјалната мрежа Facebook (кој е пријател со кого), како градовите се поврзани меѓусебно со патишта, но и да ги претставиме врските кај електричните мрежи, водоводните мрежи и слично.

Познат е случајот на средновековната копија на мапа од V век која содржела мрежа на патишта на Римското царство со имиња на градови и должина на патиѓтата помеѓу нив, доволно информаии да се најде најкраткиот пат помеѓу два града.

Темиња, ребра, типови графови

Графот е севкупност од точки и линии кои поврзуваат парови од точките. Точките на графот се нарекуваат темиња (за означуање објекти), а линиите кои ги поврзуваат темињата се нарекуваат ребра (за означување на врските помеѓу темињата). Темињата се поврзуваат врз основа на определена законитост за графот, а темињата кои се поврзани со ребро ги нарекуваме соседи.

Значи граф се дефинира како двојка (V,E), каде што V е множество темиња, а Е е множество ребра и притоа на секое ребро му е придружен пар темиња преку т.н. функција на соседство Е -> V x V.

Теоријата на графови наоѓа широка примена во реалниот свет. Од низата примери, би ги издвоиле: − поврзувањето со пријателите на социјалните мрежи (секој корисник е теме, а кога корисниците се поврзуваат, тие создаваат ребро, користење на GPS/Google Maps/Yahoo Maps (за пронаоѓање најкраток пат, минимална тура, за пребарување на Google (пребарување веб-страници поврзани меѓусебно со хиперлинкови; секоја страница е теме, врската помеѓу две страници е ребро); анализи во биологијата и другите науки.

Пример Доколку разгледуваме пријателства помеѓу различни лица на социјалната мрежа Facebook, и сакаме истите да ги претставиме со помош на граф темињата ќе бидат луѓето, а за секое пријателство, ќе нацртаме ребро од едното до другото лице.

Ако на ребрата им зададеме и некаква насока, тогаш ребрата ги нарекуваме ориентирани ребра, а графот го нарекуваме ориентиран граф или скратено орграф.

Доколку ребрата немаат никаква насока, тогаш ребрата ги нарекуваме неориентирани ребра, а графот со вакви ребра се нарекува неориентиран граф.

Нека V1 и V2 се две темиња од ориентиран граф. Ако постои ребро помеѓу V1 и V2, и стрелката се движи од V1 кон V2, тогаш реброто го запишуваме како е = (V1 , V2 ) при што V1 се нарекува почеток на реброто е (претходник на V2), а V2 се нарекува крај на реброто е (следбеник на V1).

Ако има случај е = (V1, V1), тоа ребро се нарекува лупа.

Во графот може да постојат паралелни ребра (тоа се повеќе ребра помеѓу две исти темиња).

На пример, ако зборувавме за градови и патишта помеѓу нив, сосема е нормално (и често), да постојат повеќе патишта помеѓу два града – на пример, едниот во една насока, а другиот во друга насока; или пак, стар пат и понов пат. Ова е претставено на следната слика.

Графот G=(V,E) се нарекува прост граф, каде што V е конечно непразно множество темиња и Е не содржи лупи ( јазли) и паралелни ребра. Бројот на ребра чии што еден крај е темето Vi, се нарекува степен на тоа теме Vi. Степен на едно теме Vi најчесто се обележува со d (Vi)

Во практиката, многу често се сретнуваат графови кај кои на секое ребро му е придружен реален број што може да претставува: растојание, цена, проточност, профит итн. На пример, ако зборуваме за градови и патишта, можеби ќе имаме информации за должината на самите патишта (на пример, дека патот од Скопје до Тетово е долг 40 километри, итн). Ваквите графови каде што за секое ребро е дефиниран и одреден реален број кој ја означува неговата тежина, растојание, или некоја друга слична мерка, се нарекуваат тежински графови.

Под маршрута во граф подразбираме конечна наизменична низа на темиња и ребра што почнува и завршува со теме v₀e₁v₁e₂ . . . v _n-1 e_n v_n Должина на маршрутата се одредува според бројот на поминатите ребра.

Маршрутата во која сите ребра се различни ја нарекуваме верига.

Маршрутата во која сите темиња се различни ќе ја нарекуваме пат или патека.

Обично кај патот се дозволува првото и последното теме да се еднакви и тогаш тој е затворен пат или циклус.

Множеството темиња може да се подели на подмножества темиња меѓу кои постои пат. Овие подмножества се нарекуваат сврзани компоненти на графот G. Неориентираниот граф G е сврзан ако постои точно една сврзана компонента т.е. ако било кои две темиња се поврзани со пат. Сврзаните графови што немаат циклус се нарекуваат дрва или стебла. Планарен се нарекува оној граф што може да биде графички претставен во рамнината така што ребрата претставени со произволни линии немаат пресек.

Циклуси, дрва

Два други термини кои може да ги слушнете при дискутирањето на разни графови се циклуси и дрва. Циклус претставува пат во еден граф каде што, тргнувајќи од едно теме и патувајќи низ графот, можеме повторно да се вратиме кај истото тоа теме. На пример, ако разгледуваме патишта во една држава, циклус може да претставува патот Скопје -> Куманово -> Велес -> Скопје (да тргнеме од Скопје, па од таму да патуваме до Куманово, па од Куманово до Велес, па од Велес до Скопје). Најчесто, при решавањето на разни задачи поврзани со графовите, ќе забележиме дека истите многу полесно се решаваат доколку графот не содржи циклуси.

Дрво претставува неориентиран граф (ребрата немаат насока), каде што темињата се меѓусебно поврзани со точно еден пат (не постои повеќе од еден начин да се стигне од било кое теме до било кое друго теме). Нормално, ова значи и дека дрвата не содржат циклус, но и дека истите имаат точно (N – 1) ребро, каде што N е бројот на темиња. Имено, точно (N-1) ребро се потребни за да се поврзат N темиња, на начин што постои точно еден пат помеѓу било кои две темиња во тој граф.

Претставување на графови

Иако постојат повеќе начини на претставување на графови, ќе се фокусираме на двата најмногу споменувани начини:
- користење на матрица на соседство (може да се користи кога работиме со графови кои имаат релативно мал број на темиња),
- користење на листи на соседство .

Претставувањето со матрици може да биде:

1) Со матрица на соседство (квадратна матрица Аnxn –> n е број на темиња во графот), при што A[i, j] = 1 ако постои врска меѓу теме i и теме j и A[i, j] = 0 ако не постои врска меѓу теме i и теме j. Предноста овде е што веднаш можеме да провериме дали постои врска мегу 2 темиња или не.

Значи Матрица на соседство е матрица составена само од единици и нули – ако постои патека меѓу две темиња, тогаш се запишува 1, а во спротивно 0. Кај орграфот, постоењето патека е ограничено со насоката на реброто.

2) Со матрица А nxm (n е број на темиња, а mе број на ребра), при што:

Користење листи на соседство.

За секое теме во графот чуваме по една листа во која што ни се запишани темињата до кои постои ребро. На пример, за граф со 5 темиња, тоа може да изгледа вака:

Од темето означено со индекс 0 постојат ребра до темињата означени со 2 и 3. Од темето означено со индекс 2, постојат ребра до темињата означени со 0 и 4, итн... Од темето означено со 1, не постојат ребра до ниту едно друго теме.

Листа на соседство на ориентиран граф

Листа на соседство на неориентиран граф

Доколку работиме со тежински графови, наместо листите да ни содржат само броеви (како [2, 3]), тие може да се составени од пар од броеви, каде што првиот елемент ќе означува до кое теме покажува реброто, а вториот број неговата тежина – на пример, [ (2, 5), (3, 7) ], со што имаме претставено дека од тоа теме постои ребро до темето 2 (со тежина 5), и до темето 3 (со тежина 7). При тоа, тежините можат да претставуваат должина или некоја друга мерка за проточност (на пример, колку литри вода може да се испраќаат по таа цевка во еден час, итн).

https://mendo.mk/Lecture.do?id=36 За графови