Ориентиран график. Дефиниција на Пример за матрица за соседство со насочен график

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

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

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

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

На пример, во сложената евалуација на примерокот (во геологијата, на пример), насоката на работ укажува на предност. Нормален систем на преференци не треба да има циклуси.

Тања Наташа

така што секогаш можете да направите избор, во спротивно треба да го преиспитате системот на преференции.

Еден правец.

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

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

Во јазикот на теоријата на графови, тој е формулиран на следниов начин: под кој услов може да се ориентираат рабовите на графот G така што за кој било пар од неговите темиња има ориентирана патека што ги поврзува?

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

Ќе се повика раб E = (A, B). поврзувачки раб, или истмусако тоа е единствената патека од А до Б (или обратно).

Поврзувачкиот раб ги дели сите темиња на графикот во две групи: оние до кои може да се стигне од А без да се помине по работ Е и оние до кои може да се дојде од B без да се помине покрај E. Графикот во овој случај се состои од два дела G 1 и G 2 поврзани само со работ E (сл. a и a+1).

На картата на градот, поврзувачкото ребро е единствениот автопат што поврзува одделни делови од градот. Јасно е дека доколку на ваков автопат се воспостави еднонасочен сообраќај, тогаш не би имало премин од еден до друг дел на градот.

Ако работ E i = (A i, B i) не се поврзува, тогаш постои друга патека што ги поврзува A i и B i и не поминува низ E i. Затоа, таков раб ќе се нарече цикличен раб.

сл.2 Поврзување сл. 2+1 Завршно (поврзување) Сл. 2+2 Циклично

ребро ребро

Теорема 1 Ако Г- поврзан график, тогаш секогаш е можно да се ориентираат цикличните рабови од Г , оставајќи ги поврзувачките рабови ненасочени, така што секој пар темиња во овој график може да се поврзе со насочена патека.

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

Оваа теорема можеме да ја докажеме со прикажување на начин за правилно ориентирање на графикот. Ајде да избереме внатре Г произволен раб E \u003d (A, B) . Ако Е - поврзувачки раб, ќе остане двостран, а потоа ќе може да се оди од НО до AT и назад (сл. 2+3).

сл.2+3 сл. 2+4

Ако Е е цикличен раб, тогаш тој е вклучен во некој циклус ОД, на кој можете да ја поставите цикличната ориентација (сл.2+4).

Да претпоставиме дека веќе сме ориентирале некој дел Х брои Г, така што од кое било теме на графикот Х можете да отидете на кое било друго нејзино теме во согласност со правилата за еднонасочен сообраќај. Од графиконот Г е поврзан, тогаш или Х одговара на целиот графикон g, или има раб E \u003d (A, B), што не припаѓа Х , но едно од нејзините темиња, да речеме НО , припаѓа Х .

Ако Е - поврзувачко ребро АБ , тогаш ќе остане двострано. Потоа за кое било теме X брои Х може да се најде ориентиран синџир Р поврзување X со А , што значи (преку работ Е ), и со AT . Назад од врвот AT преку работ Е можете да отидете на НО , а потоа - по должината на синџирот за ориентација З - од НО до X (Слика a+5). Прикачување Е до Х , веќе добиваме повеќетоброи Г со потребните својства. Ако работ E \u003d (A, B) е циклична, припаѓа на некој циклус ОД . Ја поставивме насоката за ОД од НО пред AT и понатаму ОД до првиот врв Д од ОД во сопственост на Х (сл. a+6).

оризот. а+5 сл. а+6

Ајде да ги додадеме сите овие рабови на Х . Нека X - произволно теме од Х , А На - кое било теме ОД ; може да се најде ориентиран синџир Р , во сопственост Х и поврзување X Со НО а потоа заедно ОД оди на врвот На од ОД . Назад од На можете да одите заедно ОД до врвот Д , а од него - припадност Х ориентиран синџир З - од Д до X . Затоа, насочениот график добиен со додавање на Х наведените рабови на циклусот ОД , ги задоволува и бараните услови. Продолжувајќи со овој процес, на крајот го ориентираме оригиналниот график на потребниот начин Г .

Теме степени.

За насочени графикони, на секое теме го имаме бројот p(A) на појдовните и бројот p*(A) на влезните рабови. Вкупен бројребрата е еднаква на:

N \u003d p (A 1) + p (A 2) + ... + p (A n) \u003d p * (A 1) + p * (A 2) + ... + p * (A n)

Достапно различни типовиграфикони за кои степените на темињата имаат некои посебни својства. Пребројувањето се нарекува хомогена, ако степените на сите негови темиња се еднакви на истиот број r: за секое теме A:

p(A) = p * (A) = r

Вежба

Конструирај хомогени насочени графикони со степен r = 2 со n = 2,6,7,8 темиња.

ОДНОСИ.

Врски и графикони.

Секој математички систем се занимава со множество од некои предмети или елементи. (Знаци: алгебра, геометрија)

Со цел да се изгради математичка теорија, ни требаат не само самите овие елементи, туку и односипомеѓу нив. (Примери: за броеви a > b; во геометријата - еднаквост на триаголници, // прави; во теоријата на множества - еднаквост и вклучувања на множества.)

Сите овие односи се однесуваат на два објекти, па затоа се нарекуваат бинарни односи, или едноставно односи, постојат и други видови на односи, на пример тројни односикои се однесуваат на три објекти. (На пример, точката А лежи помеѓу точките Б и В).

Да воведеме општа дефиниција за бинарната релација R: аRв - в е во однос на R до a.

На пример, релацијата a > b значи дека b припаѓа на множеството на сите броеви помали од a

Всушност, секој насочен граф G дефинира некаква релација во множеството од неговите темиња. Овој сооднос може да се запише како: AGв. Тоа значи дека графикот има насочен раб што оди од a до b.

Посебни услови.

Нека е дадена некоја релација R. Ако елементот a е во однос R со самиот себе, тогаш тој одговара на јамка во графикот

Релација R за која условот аRв е задоволен за било кој а, се нарекува рефлектирачки.

Ако условот aRv не е задоволен за ниту еден елемент, тогаш се повикува R антирефлексивен став.Во овој случај, ниту едно од темињата на графикот нема јамка.

За секоја релација R може да се дефинира обратен сооднос R*, под претпоставка дека аR * в ако и само ако аRв.

Од дефиницијата на инверзната релација може да се види дека ако графикот G што одговара на R има раб (a, b), тогаш графикот G * што одговара на R * мора да има раб (c, a). Со други зборови, графикот G * е инверзен на G, т.е. график со исти рабови како G, но спротивно ориентиран.

Релацијата се нарекува симетрични, ако од аРв следи вРа.

Симетрична релација одговара на график со ненасочени рабови; обратно, графикот со ненасочени рабови дефинира некаква симетрична врска.

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

Сооднос транзитивно, ако од двата услова aRb и bRc произлегува дека aRc.

Графикот на преодна релација го има следново карактеристично својство: за секој пар рабови (a, b), (b, c) постои затворањераб. Применувајќи го ова својство постојано, заклучуваме дека ако овој график има насочен пат од темето X до темето Y, тогаш постои и насочен раб (x, y).

Да претпоставиме дека постои график G со насочени рабови кој не е преоден. Во сите случаи, насочен граф G може да се направи транзитивен со додавање насочени рабови на него додека не се прицврсти затворач за секој пар од неговите последователни рабови. Така добиениот нов граф G m се нарекува преодно затворањеГрофот Г.

Односите на еквивалентност.

Релацијата на еквивалентност, обично означена со ~, ги има следните три својства:

еден). Рефлексивност: a ~ a;

2). Симетрија: од a ~ до z до ~ a;

3). Преодност: од a ~ до и до ~ c Þ a ~ c.

Всушност, релацијата еквивалентност е генерализација на својството на еднаквост.

Релацијата за еквивалентност воведува партиција во множеството темиња разделени класи на еквивалентност.

Нека B i е множеството темиња на графикот на еквивалентност G кои се еквивалентни на темето i. Тогаш сите темиња кои припаѓаат на B i се поврзани со рабови, т.е. Во i - комплетен график G i . На секое теме на таков график има јамка Графикот G се дели на множество од поврзани компоненти G i .

Делумна нарачка.

Став делумна нарачкае (на примерот на множества):

еден). Рефлексивност: A Ê A

2). Транзитивност: ако A Ê B и B Ê C Þ A Ê C

3). Идентитет: ако A Ê B и B Ê Az A = B

Строги односи за вклучување -

еден). Анти-рефлексивност: ÉA никогаш не се случува;

2). Транзитивност: ако A É B и B É C, тогаш A É C

Релација за нарачка(во строга смисла) се нарекува строг редослед, a > b, за кој покрај претходните услови важи и следново:

состојба на комплетност.За кои било два елементи кои не се совпаѓаат во и a, една од двете релации a>b или b>a е секогаш задоволена.

Обично, делумно подредениот график е прикажан во подредена форма. Бидејќи за кои било рабови (a, b) и (b, c) има затворен раб (a, c), тој може да се испушти.

РАМНИ ГРАФИ.

Услови за рамни графикони.

Грофот Куратовски К 3.3

Графикон проблем за три куќи и три бунари

Грофот Куратовски К 5

Овие два графика НЕ ​​се РАМНИ!

Продолжување на графиконот- нови темиња беа поставени на некои рабови, па овие рабови

станаа елементарни синџири составени од неколку рабови.

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

Теорема на Куратовски

За да може графикот да биде рамен, потребно е и доволно да не содржи никаков график во себе што може да се компресира на граф K 3.3 или граф K 5.

Ојлерова формула

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

Од дефиницијата на полигоналните графикони произлегува дека тие се поврзани. Ние исто така бараме да не лежи многуаголник во друг. Граничните рабови на секој таков многуаголник формираат циклус, понекогаш наречен минимален циклус. Се нарекува делот од рамнината затворен во полигонот графикон лице. Графикот исто така има максимален циклус C 1, опкружувајќи ја целинатаграфикон со сите негови лица. Ќе го разгледаме делот од рамнината што лежи надвор од C 1, исто така како лице на графикон со граница C 1 - бескрајналице F ¥.

Означи со

број на темиња, рабови и лица простор многуаголник..

Ојлерова теорема

c - p + r = 2

Доказ:Формулата е очигледна за многуаголник со n рабови. Навистина, n темиња и n рабови, како и две лица F 1 F ¥

Додаваме ново лице на графикон со r лица со цртање по лицето F ¥ некој елементарен синџир што поврзува две темиња на максималниот графикон G. Ако овој лак има r рабови, тогаш треба да додадеме r - 1 ново темиња и едно ново лице. Но тогаш

c' - p' + r' = (c + r - 1) - (p + r) + (r + 1) = c - p + r (= 2!)

според хипотезата за индукција.

Матрични претстави.

1. Матрица на инциденти А.

а). За ненасочен график матрица на инциденцае матрица чии редови одговараат на темиња и чии колони одговараат на рабовите. Елементот на матрицата е еднаков на 1 ако темето е инцидентно на раб. Во спротивно, матричниот елемент ја зема вредноста 0.

б). За насочен график, елементот на матрицата на инциденца е +1 кога темето што се спушта на лакот е почетното теме на лакот (т.е., лакот потекнува од ова теме). Елементот е -1 кога лакот влегува во теме. Ако темето не е склопено со лакот, тогаш матричниот елемент е 0.

2. Матрица на циклуси В.

а). За ненасочен график, редовите на матрицата на циклусот одговараат на едноставните циклуси на графикот, а колоните одговараат на неговите рабови. Матричен елемент a ij =1 ако циклусот С i содржи раб e j . Во спротивно a ij =0.

б). За насочен граф ij =1, -1 или 0, во зависност од тоа дали ориентацијата на циклусот C i и лакот e j е иста или спротивна, или овој циклус воопшто не го содржи лакот e j.

3. Матрицата за соседство на темето (или едноставно матрицата за соседство) V е матрица чии редови и колони одговараат на темиња, а матричниот елемент a ij во случај на ненасочен график е еднаков на бројот на рабовите што ги поврзуваат темињата i и j . За насочен граф, елементот a ij е еднаков на бројот на рабови насочени од темето i кон темето j.

Основни теореми поврзани со матрични претставиграфикони.

1) Рангот (максималниот број на линеарно независни колони) на матрицата на инциденца А на поврзан график (насочен и ненасочен) со n темиња е еднаков на (n-1).

2). Рангот на матрицата на циклусот C на поврзан граф со m рабови и n темиња е (m-n+1).

Пример за користење на матрица за соседство.

Следното пресликување покажува дека графиконите G 1 и G 2 се изоморфни

Во матриците на соседството, редовите и колоните се истовремено пермутирани, што може да се изведе со помош на трансформација на сличност и пермутациона матрица.

A 2 \u003d PA 1 P", каде

P = , или p ij =d p(i),j (симбол на Кронекер)

а P“ е транспонираната матрица.

Пронаоѓањето на матрицата P може да биде незгодно.

Изоморфизмот на G 1 и G 2 значи дека A 1 и A 2 имаат исти сопствени вредности. Сепак, оваа состојба не е доволна (пример подолу).

Нека В, Дсе произволни множества и V??.Означи со V 2Декартов квадратен сет В.

Режиран граф или накратко диграф Гнаречен тројка V, D, в): каде в- одредено пресликување на множеството D во множеството V 2. Поставете елементи Ви Дсе нарекуваат, соодветно, темиња и лаци на диграфот Г. Множества темиња и лакови на диграф Гпогодно означено со VGи ДГсоодветно. Ако ѓ- лак, тогаш в(ѓ) е нарачан пар ( и, v), каде и : v J V. Лак ѓизлегувајќи од врвот ии оди на врвот v; од своја страна ии vнаречени крајни темиња на лакот ѓ; во иднина ќе пишуваме ѓ= (а понекогаш дури и - ѓ = УВако не постои опасност од забуна).

Кога пишувате произволен диграф, тој обично ќе биде претставен како Г = (В, Д).

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

Со секој диграф Г = (В, Д) природно поврзете го графикот Г о = (В, Е), наречена основа на дадениот диграф. За да се добие основата, потребно е во диграфот Гзаменете го секој лак ѓ= раб e = uv

На сл. 8 го прикажува диграфот и неговата основа

Слика 8

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

При што

Овој пат се нарекува (v за , v т) - стандардна рута; врвови v ои v тсе нарекуваат, соодветно, почетните и завршните темиња на таков пат. Ако v о = v т, тогаш или-рутата се нарекува затворена. Бројот на лакови што ја сочинуваат шемата е должината на шаблонот.

Патеката без повторување на лакови се нарекува орчан. Едноставна орчана е орчана без повторувачки темиња (освен можеби истите почетни и крајни темиња). Затворена едноставна орлиза се нарекува орцикл или контура.

Лесно е да се провери дека постоењето (и, v;) - orroute гарантира постоење на едноставен ( и, v) - орчепи.

Велат дека врвот vдостапно од врвот и, доколку постои ( и, v)рута. диграф Ге силно поврзан или оп-поврзан ако некое од неговите темиња е достапно од кое било друго теме. Очигледно, силно поврзан диграф е поврзан; обратното, се разбира, не е точно.

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

Теорема 1.3. Поврзан графикон Гсе ориентира ако и само ако секој негов раб не е мост.

Доказ. Нека брои Ге основата на диграфот Хи Гсодржи мост д. Потоа во Хима лак ѓ=, каде и, v- краеви на ребрата д. Очигледно во Хне ( u, v) - правци. Затоа, графикон Гне е ориентиран.

Назад, нека брои Гнема мостови, т.е. секој раб на графикот Гсодржани во еден циклус. Бидејќи секој циклус е ориентиран график, во графикот Гпостои максимално ориентиран потграф Х. Да се ​​увериме во тоа Х = Г. Да претпоставиме дека оваа еднаквост не е задоволена. Поради поврзаноста на графикот Гима раб e инцидент на темето vод Хи не лежи внатре Х. Според претпоставката, работ e лежи во некој циклус ОД. Означи со Пмножеството рабови на циклусот што не припаѓаат на потграфот Х. Тоа е лесно да се види, додавајќи на Хсите рабови од сетот П, повторно добиваме ориентабилен потграф, во спротивност со изборот Х.

Нека Ге произволен диграф. Степен на исход degvврвови vе бројот на сите лакови што ги имаат vкако почеток. Слично на тоа, степенот на влез degvе бројот на сите лакови за кои темето vе крајот. Диграф кој содржи Пврвови и тлакови ќе се нарекуваат ( n, т) е диграф.

Надворешните и во-степените се поврзани на следниот очигледен начин.

Лема 1. Нека Г- произволно ( n, т) е диграф. Потоа

Ова тврдење е слично на Лема 1 од Sec. 1.1; често се нарекува орлема на ракување.

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

Основни концепти

Формално, диграфот D = (V , E) (\displaystyle D=(V,E))се состои од многу V (\displaystyle V), чии елементи се нарекуваат врвови, и поставува E (\displaystyle E)подредени парови темиња u , v ∈ V (\displaystyle u,v\in V).

Лак (u, v) (\приказ стил (u,v)) случаенврвови u (\displaystyle u)и v (\displaystyle v). Во исто време, тие го велат тоа u (\displaystyle u) - почетен врвлакови, и v (\displaystyle v) - терминален врв.

Поврзување

рутаво диграф се нарекува наизменична низа темиња и лакови, љубезен v 0 ( v 0 , v 1 ) v 1 ( v 1 , v 2 ) v 2 . . . v n (\стил на приказ v_(0)\(v_(0),v_(1)\)v_(1)\(v_(1),v_(2)\)v_(2)...v_(n))(темињата може да се повторат). Должина на патеката- бројот на лакови во него.

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

Колопостои затворена патека.

За половина патсе отстранува ограничувањето на насоката на лаците, на на половина пати полу-контура.

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

Максимум силнасе нарекува потграфот силна компонента; еднострана компонентаи слаба компонентасе дефинираат на сличен начин.

кондензацијадиграф D (\displaystyle D)наречен диграф чии темиња се силни компоненти D (\displaystyle D), и лакот во D ⋆ (\displaystyle D^(\star ))означува присуство на најмалку еден лак помеѓу темињата вклучени во соодветните компоненти.

Дополнителни дефиниции

Насочен ацикличен графикили хамаке диграф без контура.

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

Слика и својства на сите диграфи со три јазли

Легенда: ОД- слаб, ОС- еднострано, СС- силен, Х- е насочен график, Г- е хамак (ациклична), Т- е турнир

0 лакови	1 лак	2 лакови	3 лакови	4 лакови	5 лакови	6 лакови
празен, Н, Г	Н, Г		ОС	CC	CC	целосна, CC
		ОС, Н, Г	CC, N, T	CC
		C, N, G	ОС, Н, Г, Т	ОС
		C, N, G	ОС

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

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

Математиката не функционира со содржината на нештата, туку со нивната структура, апстрахирајќи ја од сè што е дадено како целина. Користејќи ја само оваа техника, можеме да заклучиме за некои објекти како и за графиконите. А бидејќи теоријата на графови е дел од математиката, воопшто не и е важно што, во принцип, е објект; единствено важно е дали е график, т.е. дали ги има својствата потребни за графиконите. Затоа, пред да дадеме примери, во предметот што се разгледува го издвојуваме само она што, според нас, ќе ни овозможи да покажеме аналогија, бараме нешто заедничко.

Да се ​​вратиме на компјутерската мрежа. Има одредена топологија и може конвенционално да се прикаже како голем број компјутери и патеки што ги поврзуваат. Сликата подолу покажува целосно мрежена топологија како пример.

Тоа е во основа графикон. Петте компјутери се темиња, а врските (патеките за сигнализација) меѓу нив се рабови. Заменувајќи ги компјутерите со темиња, добиваме математички објект - график кој има 10 рабови и 5 темиња. Можете да ги нумерирате темињата произволно, а не нужно на начинот на кој тоа е направено на сликата. Вреди да се напомене дека во овој пример не се користат јамки, односно таков раб што го напушта темето и веднаш влегува во него, но може да се појават јамки во проблеми.

Еве неколку важни ознаки кои се користат во теоријата на графикони:

• G=(V, E), овде G е граф, V се неговите темиња, а E се рабовите;
• |V| – редослед (број на темиња);
• |Д| – големина на графиконот (број на рабови).

Во нашиот случај (сл. 1) |V|=5, |E|=10;

Кога било кое друго теме е достапно од кое било теме, тогаш се нарекува таков график неориентираниповрзан график (сл. 1). Ако графикот е поврзан, но овој услов не е задоволен, тогаш се нарекува таков график ориентиранаили диграф (сл. 2).

Насочените и ненасочените графови имаат поим за степен на теме. Вертекс степене бројот на рабовите што го поврзуваат со други темиња. Збирот на сите степени на графикот е еднаков на двојно поголем број на сите негови рабови. За слика 2, збирот на сите моќи е 20.

Во диграф, за разлика од ненасочениот график, можно е да се премести од темето h во темето s без средни темиња, само кога некој раб излегува од h и влегува во s, но не и обратно.

Насочените графикони ја имаат следната нотација:

G=(V, A), каде V се темиња, A се насочени рабови.

Третиот тип на графикони - измешаниграфикони (сл. 3). Имаат и насочени рабови и ненасочени. Формално, мешаниот график се запишува на следниов начин: G=(V, E, A), каде секоја од буквите во загради го означува и она што претходно му се припишувало.

На графиконот на слика 3, некои лакови се насочени [(e, a), (e, c), (a, b), (c, a), (d, b)], други се ненасочени [( е, г), (д, б), (г, в)...].

Два или повеќе графикони на прв поглед може да изгледаат различни во нивната структура, што произлегува поради нивната различна претстава. Но, тоа не е секогаш случај. Да земеме два графикони (сл. 4).

Тие се еквивалентни еден на друг, бидејќи без промена на структурата на еден график, можете да изградите друг. Таквите графикони се нарекуваат изоморфни, т.е., да има својство дека секое теме со одреден број рабови во еден граф има идентично теме во друг. Слика 4 прикажува два изоморфни графикони.

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

Во кој било од графиконите што ги разгледавме, можно е да се избере патека и, згора на тоа, повеќе од една. Пате низа од темиња, од кои секое е поврзано со следниот со помош на раб. Ако првото и последното теме се совпаѓаат, тогаш таквата патека се нарекува циклус. Должината на патеката се одредува според бројот на рабовите што ја сочинуваат. На пример, на слика 4.а, патеката е низата [(e), (a), (b), (c)]. Оваа патека е потграф, бидејќи за неа важи дефиницијата за вториот, имено: графикот G'=(V', E') е потграф на графикот G=(V, E) само ако V' и E' припаѓаат на V, E.

Во претходните поглавја презентиравме некои од главните резултати од теоријата на ненасочени графици. Сепак, ненасочените графикони не се доволни за да опишат некои ситуации. На пример, кога се претставува сообраќајна карта со график чии рабови одговараат на улици, мора да се додели ориентација на рабовите за да се покаже дозволената насока на движење. Друг пример е компјутерска програма моделирана со график чии рабови го претставуваат протокот на контрола од еден сет на инструкции до друг. Во оваа претстава на програмата, на рабовите исто така мора да им се даде ориентација за да се покаже насоката на контролниот тек. Друг пример на физички систем кој бара насочен график за да се претстави е електричното коло. Примените на насочени графикони и сродните алгоритми се дискутирани во Поглавје. 11-15.

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

5.1. Основни дефиниции и концепти

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

Упатениот график се состои од две множества: конечно множество V, чии елементи се нарекуваат темиња, и конечно множество E, чии елементи се нарекуваат рабови или лаци. Секој лак е поврзан со подреден пар темиња.

Симболите се користат за означување темиња, а симболите се користат за означување на лакови. Ако , тогаш се нарекуваат крајни темиња, и - почетно теме, - крајно теме . Сите лакови кои имаат ист пар на почетни и крајни темиња се нарекуваат паралелни. Лакот се нарекува јамка ако упадното теме е и неговото почетно и крајно теме.

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

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

На пример, ако е таков како Нивниот), насочен график може да се претстави со сл. 5.1. Во овој график - паралелни лаци и - јамка.

Ориз. 5.1. Ориентиран график.

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

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

Степенот на темето е бројот на лакови што се спуштаат на него. Во-степенот на темето е бројот на лакови кои влегуваат во V], а надвор-степенот е бројот на излезни лакови. Симболите и b" го означуваат минималниот надворешен и во-степен на насочениот график. Слично на тоа, симболите го означуваат максималниот надворешен и во-степен, соодветно.

Множествата на кое било теме се дефинираат на следниов начин: . На пример, на графиконот на сл. 5.1.

Забележете дека јамката ги зголемува полу-степените и на влезот и на излезот од ова теме. Следното тврдење е последица на фактот дека секој лак го зголемува за 1 збирот на полустепените и на влезот и на излезот на насочен график.

Теорема 5.1. Во насочен график со лакови

Збир на во-степени = Збир на надвор-степени = m.

Подграфи и генерирани потграфи на насочен график се дефинирани на ист начин како и во случајот со ненасочени графикони (оддел 1.2).

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

Упатена патека на насочен граф е конечна низа од темиња

Што е лак на графикот G. Таквата рута обично се нарекува насочена -рута, а почетното теме е последното теме на трасата, а сите други темиња се внатрешни. Почетните и крајните темиња на насочената патека се нарекуваат нејзини крајни темиња. Забележете дека лаците, а со тоа и темињата, може да се појават повеќе од еднаш во насочена патека.

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

Ориентирана патека се нарекува ориентирана патека ако сите нејзини лаци се различни. Ориентирана патека е отворена ако нејзините крајни точки се различни, во спротивно е затворена.

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

Затворен ориентиран синџир се нарекува ориентиран циклус или контура ако неговите темиња, со исклучок на терминалните, се различни.

За насочен график се вели дека е ацикличен или без контура ако нема контури. На пример, насочениот график на Сл. 1 е ацикличен. 5.2.

Ориз. 5.2. Ациклично насочен график.

Ориз. 5.3. Силно поврзан насочен график.

Секвенца од темиња во насочен граф G се нарекува патека во G ако е патека во основниот ненасочен график. На пример, низата во графикот на сл. 5.2 е рута, но не е ориентирана.

Синџирот, патеката и циклусот на насочен график се дефинирани слично.

За насочен график се вели дека е поврзан ако основниот ненасочен график е поврзан.

Подграфот на насочен граф G се нарекува компонента на графикот G ако е компонента на графикот

Темињата на насочен граф G се вели дека се силно поврзани ако има насочени патеки од и назад до G. Ако е силно поврзан со тогаш, очигледно, е силно поврзан со . Секое теме е силно поврзано со себе.

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

За насочен граф се вели дека е силно поврзан ако сите негови темиња се силно поврзани. На пример, графикот на сл. 5.3.

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

Размислете за насочен график. Лесно е да се види дека секое од неговите темиња припаѓа на точно една силно поврзана компонента на графикот G. Затоа, множествата темиња на силно поврзани компоненти формираат партиција на темето множество Y на графикот

Ориз. 5.4. Графикон и неговата кондензација.

На пример, насочениот график на Сл. 5.4, ​​а има три силно поврзани компоненти со вертекс множества и кои формираат партиција на темето множество на насочен график.

Интересно, насочениот график може да содржи лакови кои не се вклучени во ниту една силно поврзана компонента на графикот. На пример, ниту една силно поврзана компонента не вклучува лакови во графиконот на сл. 5.4, ​​а.

Така, иако својството „силно поврзано“ повлекува разделување на темето множество на графикот, може да не генерира разделување на множеството лакови.

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

Графикот што произлегува од контракцијата на сите лакови на силно поврзани компоненти на насочен графикон G се нарекува кондензиран график на G. Кондензацијата на графикот прикажана на сл. 5.4, ​​а, е прикажано на сл. 5.4б.

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

Рангот и цикломатскиот број на насочен граф се исти како оние на соодветниот ненасочен график. Ова значи дека ако насочен граф G има лакови, темиња и компоненти, тогаш рангирањето и цикломатскиот број на графот G се дадени со

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

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

Ориз. 5.5. Минимално поврзан насочен график.

Минимално поврзан е, на пример, графикот прикажан на сл. 5.5.

Очигледно, минимално поврзаните графикони не можат да имаат паралелни лаци и јамки.

Знаеме дека ненасочениот график е минимално поврзан ако и само ако е дрво (Пр. 2.13). Според теорема 2.5, дрвото има најмалку две темиња од степен 1. Затоа, минимално поврзаните ненасочени графикони имаат најмалку две темиња од степен 1.

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