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

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу
Усмерени граф.
Оријентисан граф са одговарајућом матрицом суседства

У математици, а посебно у теорији графова, у усмерен граф (или диграф)- је граф, или скуп чворова, повезаних гранама, где гране имају правац. У формалном смислу, усмерен граф-то је уређен пар G = (V, A) (понекад у ознаци G = (V, E)). [1]

  • V је  скуп чији се елементи зову врхови, чворови, или тачке;
  • А(понекад и Е) је скуп одређених парова чворова, које се називаоју стрелицама, усмереним гранама (понекад само гранама са одговарајућим скупом по имену Е уместо A),или директне линије.

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

Усмерени граф се зове једноставан диграф , ако он има више стрела (две или више гране, који повезују два чвора у истом правцу) и ако нема циклусе (гране, повезују чворове са самим собом). Усмерени граф се зове усмерени мултиграф или мултидиграф ако он може да има неколико стрела (а понекад и циклусе). У овом другом случају, гране формирају мултискуп, а не скуп, уређених парова чворова.

Основни појмови[уреди]

Грана (x,y) сматра се усмереном од чвора x до чвора y; Y се зове глава а x се зове реп гране (стрелице); Y је директан следбеник од x-a,  а x је директан претходник од y. Ако пут води од x-а ка y код, y је следбеник од x и достижан (могуће је стићи до тог чвора) од x. X је претходник y-a. Грана (y,x) се зове обрнутом граном (x,y).

Додајући оријентацију неодређеном графу, тј постављајучи смер сваке гране, од обичног графа добијамо усмерен граф. Било који граф који се направи на овакав начин назива се орјентисан граф. Међу усмереним графовима, орјентисајни графови су они који немају 2 циклуса (највише једна грана (x,y) и једна грана (y,x) могу бити гране графа).[2]

Тежински усмерени граф је усмерени граф са одређеним тежинама (вредностима) које се додају уз сваку грану, сличан је као тежински граф.

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

Матрица суседства мултидиграфа који има циклусе, је матрица са целим вредностима, редовима и колонама који одговарају чворовима, где је недијагонално пољe аij - број грана од чвора i до чвора ј, a дијагонално пољеаii - број циклуса у чвору i.

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

Улазни и излазни степен[уреди]

Оријентисан граф, са означеним чворовима (улазни степен, излазни степен).

Улазни степен чвора (u)  у ознаци deg-(u) представља број грана којима је чвор u завршни чвор. Излазни степен чвора (u) у ознаи deg+(u) представља број грана којима је чвор u почетни чвор.

Нека је G = (V, E) и v∈V. Чвор који има deg-(u)=0 назива се извором, и он је порекло свих осталих инцидентних грана.

Слично томе, чвор који има deg+(v)=0 назива се понор.

Ако чвор није ни извор , ни понор, тада се он зове унутрашњи.

Формула за степен чвора у усмереном графу је

Ако за сваки чвор важи v∈V, deg+(v) = deg−(v), тада се тај граф назива балансиран оријентисан граф.[3]

Низ степена[уреди]

Низ степена директног графа је низ парова, његових улазних и излазних степена, за пример који је горе наведен, имамо низ степена ((2, 0), (2, 2), (0, 2), (1, 1)). Два графа су изоморфна ако имаји исти низ степена, мада понекад се може десити да графови иако нису изоморфни имају исти низ степена

Проблем реализације графа је задатак проналажења усмереног графа са задатим низом степена који су дати у облику целобројних парова. Низ, који је низ степена неког усмереног графа, односно за који проблем реализације усмереног графа има решење, зове се усмерени граф или усмерен графички низ. Овај проблем може бити решен уз помоћ Клеитман–Ван алгоритма или уз помоћ Фулкерсон–Чен–Анстее теореме.

Повезаност усмереног графа[уреди]

Усмерен граф је слабо повезан (или само повезан[4]), ако је неусмерен основни граф, добијен заменом свих грана у директном графу са неусмереним гранама,повезан граф. Усмерен граф је јако повезан или јак, ако садржи директан пут из у чвор y, и директан пут из чвора y до чвора x, за сваки пар чворова (x,y). Јаке компоненте су најјачи повезани подграфови.

Класе усмереног графа[уреди]

Симетрични диграф је усмерени граф у коме свака грана која њему припада, има своју инверзну грану, која такође њему припада. Симетричан, безцикличан усмерен је еквивалентан графу са гранама замењеним са паром инверзних грана. Број неусмерених грана је једнак половини броју усмерених грана.

Једноставан оријентисан ацикличан граф.

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

Турнир на 4 врха.

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

Види још[уреди]

Референце[уреди]

  1. ^ Bang-Jensen & Gutin (2000)
  2. ^ Diestel (2005), Section 1.10.
  3. ^ Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., стр. 460, ISBN 978-81-203-3842-5 
  4. ^ Bang-Jensen & Gutin (2000) pp. 19 in the 2007 edition; pp. 20 in the 2nd edition (2009).

Литература[уреди]