ДРЖАВЕН ПЕДАГОШКИ УНИВЕРЗИТЕТ ВЛАДИМИР
АПСТРАКТ
„ТЕОРИЈА НА ГРАФИ“
Изведено:
Зудина Т.В.
Владимир 2001 година
1. Вовед
2. Историја на појавата на теоријата на графикони
3. Основни дефиниции на теоријата на графикони
4. Основни теореми на теоријата на графови
5. Проблеми за примена на теоријата на графикони
6. Примена на теоријата на графикони на училишен предмет по математика
7. Примена на теоријата на графикони во различни области на науката и технологијата
8. Неодамнешниот напредок во теоријата на графикони
§1. ИСТОРИЈА НА ПОЈАВА НА ТЕОРИЈАТА НА ГРАФИ.
За основач на теоријата на графикони се смета математичарот Леонхард Ојлер (1707-1783). Историјата на оваа теорија може да се следи преку кореспонденцијата на големиот научник. Еве превод на латинскиот текст, кој е преземен од писмото на Ојлер до италијанскиот математичар и инженер Маринони, испратено од Санкт Петербург на 13 март 1736 година [види. стр. 41-42]:
„Еднаш ме прашаа за проблем за островот лоциран во градот Кенигсберг и опкружен со река преку која се фрлаат седум мостови. Прашањето е дали некој може постојано да ги обиколува, поминувајќи само еднаш низ секој мост. И тогаш бев информираше дека никој сè уште не можел да го стори тоа, но никој не докажал дека тоа е невозможно. доволно за да се реши... По долго размислување, најдов едно лесно правило, засновано на сосема убедлив доказ, со чија помош може веднаш да се утврди во сите проблеми од овој вид дали може да се направи вакво заобиколување преку било кој број на мостови лоцирани на кој било начин или не.за да можат да бидат претставени на следната слика[сл.1] , на кој А означува остров и Б , В и Д - делови од континентот одделени еден од друг со речни гранки. Седумте мостови се означени со букви а , б , в , г , д , ѓ , е ".
(СЛИКА 1.1)
Во врска со методот што го открил за решавање проблеми од овој вид, Ојлер напишал [види. стр. 102-104]:
„Ова решение, по својата природа, очигледно нема врска со математиката и не разбирам зошто ова решение треба да го очекуваме од математичар, а не од кое било друго лице, бидејќи оваа одлука е поткрепена само со расудување, и не постои треба да се вклучи за да се најде ова решение, какви било закони својствени за математиката. Значи, не знам како излегува дека прашањата што имаат многу мала врска со математиката, почесто ги решаваат математичарите отколку другите“.
Значи, дали е можно да се заобиколат мостовите Кенигсберг со поминување само еднаш преку секој од овие мостови? За да го најдеме одговорот, да го продолжиме писмото на Ојлер до Маринони:
„Прашањето е да се утврди дали е можно да се заобиколат сите овие седум мостови, поминувајќи низ секој само еднаш, или не. Моето правило води до следново решение на ова прашање. Прво, треба да погледнете колку области има таму. се, одвоени со вода - такви, кои немаат друг премин од еден во друг освен преку мост. Во овој пример, има четири такви делови - А , Б , В , Д . Следното нешто што треба да се разликува е дали бројот на мостови што водат до овие одделни делови е парен или непарен. Значи, во нашиот случај, пет мостови водат до делот А, а по три моста водат до останатите, т.е. бројот на мостови што водат до одделни делови е непарен и само ова е доволно за да се реши проблемот. Откако ќе се утврди ова, го применуваме следново правило: ако бројот на мостови што водат до секој поединечен дел би бил парен, тогаш би можело да се работи за заобиколување, а во исто време би било можно да се започне оваа обиколница од која било делница. . Ако два од овие броеви беа непарни, зашто само еден не може да биде непарен, тогаш дури и тогаш може да се изврши транзицијата, како што е пропишано, но само почетокот на колото секако мора да се земе од еден од тие два дела до кои води непарниот број. мостови. Ако, конечно, имало повеќе од два делници до кои водат непарен број мостови, тогаш таквото движење е генерално невозможно... доколку тука се донесат други, посериозни проблеми, овој метод би можел да биде од уште поголема корист и треба да да не се занемарува“.
Образложението за горенаведеното правило може да се најде во писмото од Л. Ојлер до неговиот пријател Елер од 3 април истата година. Подолу ќе прераскажеме извадок од ова писмо.
Математичарот напишал дека транзицијата е можна доколку во делот на реката нема повеќе од две области, до кои водат непарен број мостови. За полесно да го замислиме ова, ќе ги избришеме веќе поминатите мостови на сликата. Лесно е да се провери дали ако почнеме да се движиме во согласност со правилата на Ојлер, поминеме еден мост и го избришеме, тогаш сликата ќе прикаже дел каде што повторно нема повеќе од две области до кои водат непарен број мостови, и ако таму се области со непарен број мостови ќе се наоѓаме во еден од нив. Продолжувајќи да продолжиме вака, еднаш ќе ги поминеме сите мостови.
Приказната за мостовите на градот Кенигсберг има модерно продолжение. Да отвориме, на пример, училишен учебник по математика уреден од Н.Ја. Виленкина за шесто одделение. Во него, на страница 98, под насловот развој на внимание и интелигенција, ќе најдеме проблем кој е директно поврзан со оној што Ојлер некогаш го решил.
Задача бр.569. На езерото има седум острови, кои се поврзани едни со други како што е прикажано на слика 1.2. На кој остров треба да ги однесе патниците со брод за да можат да го поминат секој мост и тоа само еднаш? Зошто патниците не можат да се превезуваат на островот? А ?
(СЛИКА 1.2)
Решение.Бидејќи овој проблем е сличен на проблемот на мостовите Кенигсберг, при неговото решавање ќе го користиме и правилото на Ојлер. Како резултат на тоа, го добиваме следниот одговор: бродот мора да ги испорача патниците на островот Еили Фза да можат да го поминат секој мост еднаш. Од истото правило на Ојлер произлегува дека потребното заобиколување е невозможно доколку се тргне од островот А .
Како заклучок, забележуваме дека проблемот со мостовите на Кенигсберг и слични проблеми, заедно со збир на методи за нивно проучување, сочинуваат многу важна гранка на математиката во практична смисла, наречена теорија на графови. Првата работа на графиконите му припаѓала на Л. Ојлер и се појавила во 1736 година. Последователно, Кениг (1774-1833), Хамилтон (1805-1865) и современите математичари Ц. Берге, О. Оре, А. Зиков работеа на графикони.
§2. ОСНОВНИ ТЕОРЕМИ НА ТЕОРИЈАТА НА ГРАФИ
Теоријата на графикони, како што беше споменато погоре, е математичка дисциплина создадена со напорите на математичарите, затоа нејзината презентација ги вклучува потребните строги дефиниции. Значи, да продолжиме со организирано воведување на основните концепти на оваа теорија.
Дефиниција 2.01. броие збирка од конечен број точки наречени врвовиграфик, и парови линии што поврзуваат некои од овие темиња, повикани ребраили лаковиграфикон.
Оваа дефиниција може да се формулира поинаку: броисе нарекува непразен сет на точки ( врвови) и сегменти ( ребра), чии два краја припаѓаат на дадена група точки (види Сл. 2.1).
(СЛИКА 2.1)
Во продолжение, темињата на графикот ќе ги означиме со латински букви А , Б ,В ,Д. Понекогаш графикот како целина ќе биде означен со една голема буква.
Дефиниција 2.02.Темињата на графикот што не припаѓаат на ниту еден раб се нарекуваат изолирани .
Дефиниција 2.03.Се нарекува график кој се состои само од изолирани темиња нула - брои .
Ознака: О " – график со темиња кој нема рабови (сл. 2.2).
(СЛИКА 2.2)
Дефиниција 2.04.Се нарекува графикон во кој секој пар темиња е поврзан со раб заврши .
Ознака: У " – графикон кој се состои од nтемиња и рабови што ги поврзуваат сите можни парови од овие темиња. Таков график може да се претстави како n– триаголник во кој се нацртани сите дијагонали (сл. 2.3).
(СЛИКА 2.3)
Дефиниција 2.05. Степен врвовие бројот на рабовите на кои припаѓа темето.
Ознака: стр (А) – теме степен А . На пример, на слика 2.1: стр (А)=2, стр (Б)=2, стр (В)=2, стр (Д)=1, стр (Е)=1.
Дефиниција 2.06.Број, степени од сите кчии темиња се идентични се вика хомогена брои степени к .
На сликите 2.4 и 2.5 се прикажани хомогени графикони од втор и трет степен.
(СЛИКА 2.4 и 2.5)
Дефиниција 2.07. Додаток дадена графиконе график кој се состои од сите рабови и нивните краеви кои мора да се додадат на оригиналниот график за да се добие целосен график.
Слика 2.6 го прикажува оригиналниот график Г , кој се состои од четири темиња и три отсечки, а на слика 2.7 - комплементот на овој график - графикот Г " .
(СЛИКА 2.6 и 2.7)
Гледаме дека на слика 2.5 има ребра А.Ц.И БДсе сечат во точка која не е теме на графикот. Но, има случаи кога даден график треба да биде претставен на рамнина на таков начин што неговите рабови се сечат само на темињата (ова прашање ќе биде разгледано подетално, во став 5).
Дефиниција 2.08.Графикот што може да се претстави на рамнина на таков начин што неговите рабови се сечат само на темињата се нарекува рамен .
На пример, на Слика 2.8 е прикажан планарен график кој е изоморфен (еднаков) на графикот на слика 2.5. Сепак, забележете дека не секој график е рамномерен, иако обратното е точно, односно секој планарен график може да биде претставен во вообичаената форма.
(СЛИКА 2.8)
Дефиниција 2.09.Се нарекува многуаголник на рамнински граф кој не содржи темиња или рабови на графикот раб .
Неформално, графикот може да се замисли како збир на точки и линии што ги поврзуваат овие точки, со или без стрелки.
Првото дело на теоријата на графикони како математичка дисциплина се смета за трудот на Ојлер (1736), кој го разгледувал проблемот на мостовите Кенингсберг. Ојлер покажа дека е невозможно да се заобиколат седумте градски мостови и да се врати на почетната точка со поминување на секој мост точно еднаш. Теоријата на графикони го доби својот следен поттик речиси 100 години подоцна со развојот на истражувањата во електричните мрежи, кристалографијата, органската хемија и другите науки.
Без да го забележиме тоа, постојано се среќаваме со графикони. На пример, графиконот е дијаграм на линии на метрото. Точките на него претставуваат станици, а линиите претставуваат маршрути за воз. Истражувајќи го нашето потекло и следејќи го назад до некој далечен предок, градиме таканаречено семејно стебло. И ова дрво е график.
Графиконите служат како погодно средство за опишување на односите меѓу објектите. Претходно користевме графикони како начин за визуелно претставување на конечни бинарни врски.
Но, графикот се користи не само како илустрација. На пример, со разгледување на графикон кој прикажува мрежа од патишта помеѓу населените места, можете да ја одредите маршрутата од точката А до точката Б. Ако има неколку такви правци, би сакале да ја изберете оптималната во одредена смисла, на пример најкраткиот или најбезбедниот. За да се реши проблемот со изборот, неопходно е да се извршат одредени пресметки на графикони. При решавање на вакви проблеми, погодно е да се користат алгебарски техники, а самиот концепт на графикот треба да се формализира.
Методите на теоријата на графикони се широко користени во дискретната математика. Невозможно е да се направи без нив кога се анализираат и синтетизираат различни дискретни конвертори: функционални блокови на компјутери, софтверски пакети итн.
Во моментов, теоријата на графикони опфаќа многу материјал и активно се развива. При неговото презентирање ќе се ограничиме само на дел од резултатите и главниот акцент ќе го ставиме на описот и оправдувањето на некои широко распространети алгоритми за анализа на графикони кои се користат во теоријата на формалните јазици.
Основни дефиниции
Графиконите, како што веќе беше забележано во примерите, се начин за „визуелизирање“ врски помеѓу одредени објекти. Овие врски можат да бидат „насочени“, како, на пример, во семејно стебло или „ненасочени“ (мрежа од двонасочни патишта). Во согласност со ова, во теоријата на графикони постојат два главни типа на графикони: насочен (или насочен) и ненасочен.
Методи на презентација
Досега дефиниравме насочени и ненасочени графикони, прикажувајќи ги со помош на цртежи. Графикот можете да го дефинирате како пар множества, следејќи ја дефиницијата, но овој метод е прилично тежок и е од теоретски интерес. Развојот на алгоритамски пристапи за анализа на својствата на графиконите бара други начини за опишување на графикони кои се посоодветни за практични пресметки, вклучително и користење на компјутер. Да ги погледнеме трите најчести начини за претставување на графикони.
Дрвја
Дефиниција 5.5. Ненасочено дрво е поврзан и ацикличен ненасочен график. Дефиниција 5.6. Упатено стебло е граф кој не е насочен кон контура во кој полустепенот на кое било теме не е поголем од 1 и има точно едно теме, наречено корен на насоченото дрво, чиј полустепен е 0.
Дрво со најмала тежина
Следниот проблем е познат во теоријата на графови како Штајнер: n точки се дадени на рамнина; треба да ги поврзете со прави отсечки на таков начин што вкупната должина на сегментите е минимална.
Методи за систематско поминување на темињата на графиконот
Важни проблеми во теоријата на графиконите се проблемите на глобалната анализа и на ненасочените и на насочените графици. Овие задачи вклучуваат, на пример, задача за наоѓање циклуси или контури, пресметување на должината на патеките помеѓу парови темиња, наведување патеки со одредени својства итн. Глобалната графска анализа треба да се разликува од локалната анализа, чиј пример е проблемот со определување на множества на претходници и наследници на фиксно теме на насочен граф.
Проблем на патеката во пондерирани насочени графикони
Графички изоморфизам
За насочен граф (V, E), множеството E од лакови може да се смета како график на бинарна директна врска достижливост дефинирана на множеството темиња. Во ненасочен график (V, E), множеството E од рабовите е множество од непоредени парови. За секој неуреден пар (u, v) ∈ E можеме да претпоставиме дека темињата u и v се поврзани со симетрична бинарна релација p, т.е. (u, v) ∈ р и (v, u) ∈ р.
Тополошко сортирање
Дефиниција 5.17. Упатена мрежа (или едноставно мрежа) е насочен графикон без контура*. Бидејќи мрежата е график без контура, може да се покаже дека има темиња (јазли) на мрежата со нула надвор-степен, како и темиња (јазли) со нула во-степен. Првите се нарекуваат мијалници или излези на мрежата, а вторите се нарекуваат извори или влезови на мрежата.
Елементи на цикломатика
Кога се дискутираше за алгоритам за пребарување на прво длабочина во ненасочен график, беше разгледано прашањето за пребарување на таканаречените фундаментални циклуси на графикот. Во овој случај, фундаменталниот циклус беше сфатен како циклус што содржи точно еден обратен раб, и беше воспоставена кореспонденција еден-на-еден помеѓу основните циклуси и обратните рабови; фундаменталните циклуси се појавуваат секогаш кога произволна поделба на сите рабови на ненасочен граф во дрва (формирајќи некоја максимална рабна шума на оригиналниот график) и инверзна, а во општ случај оваа партиција може да се специфицира целосно независно од алгоритмот за пребарување длабочина-прва. Првото пребарување во длабочина е само еден начин да се имплементира таква партиција.
Теоријата на графикони е гранка на дискретната математика која ги проучува објектите претставени како поединечни елементи (темења) и врските меѓу нив (лакови, рабови).
Теоријата на графикони потекнува од решението на проблемот на мостовите Кенигсберг во 1736 година од познатиот математичар Леонард Ојлер(1707-1783: роден во Швајцарија, живеел и работел во Русија).
Проблем за мостовите Кенигсберг.
Во прускиот град Кенигсберг на реката Прегал има седум мостови. Дали е можно да се најде пешачка рута која го поминува секој мост точно еднаш и почнува и завршува на истото место?
Графикот во кој постои маршрута која започнува и завршува на истото теме и поминува по сите рабови на графикот точно еднаш се нарекуваОјлеров график.
Низата темиња (можеби и повторени) низ кои минува саканата рута, како и самата рута, се нарекуваОјлеровиот циклус .
Проблемот со три куќи и три бунари.
Има три куќи и три бунари, некако сместени во авион. Нацртајте патека од секоја куќа до секој бунар за да не се вкрстуваат патеките. Овој проблем беше решен (се покажа дека нема решение) од Куратовски (1896 - 1979) во 1930 година.
Проблем со четири бои. Поделба на рамнина во области кои не се пресечуваат се нарекува со картичка. Областите на картата се нарекуваат соседни ако имаат заедничка граница. Задачата е да се обои картата на таков начин што нема две соседни области да бидат обоени со иста боја. Од крајот на 19 век, позната е хипотезата дека за ова се доволни четири бои. Хипотезата сè уште не е докажана.
Суштината на објавеното решение е да се испробаат голем, но конечен број (околу 2000) типови на потенцијални контрапримери на теоремата за четири бои и да се покаже дека ниту еден случај не е контрапример. Ова пребарување беше завршено од програмата за околу илјада часа работа на суперкомпјутер.
Невозможно е да се провери добиеното решение „рачно“ - опсегот на набројувањето е надвор од опсегот на човечките способности. Многу математичари го поставуваат прашањето: дали таков „програмски доказ“ може да се смета за валиден доказ? На крајот на краиштата, може да има грешки во програмата ...
Така, можеме само да се потпреме на програмските вештини на авторите и да веруваме дека тие направиле сè како што треба.
Дефиниција 7.1. брои Г= Г(В, Е) е збир од две конечни множества: V – повикани многу темињаи множеството Е од парови елементи од V, т.е. EÍV´V, повикан многу рабови, ако паровите се неуредени, или многу лакови, доколку паровите се нарачани.
Во првиот случај, графикот Г(В, Е) повикани неориентирани, во втората - ориентирана.
ПРИМЕР. График со множество темиња V = (a,b,c) и множество рабови E =((a, b), (b, c))
ПРИМЕР. График со V = (a,b,c,d,e) и E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (в, г)),
Ако e=(v 1 ,v 2), еОЕ, тогаш велат дека работ е e поврзуватемиња v 1 и v 2.
Се повикуваат две темиња v 1,v 2 соседните, ако има раб што ги поврзува. Во оваа ситуација, секое од темињата се нарекува инцидент соодветниот раб .
Две различни ребра соседните, ако имаат заедничко теме. Во оваа ситуација, секој од рабовите се нарекува случаен соодветно теме .
Број на темиња на графиконот Гда означиме v, а бројот на рабовите е д:
.
Геометрискиот приказ на графиконите е како што следува:
1) темето на графикот е точка во просторот (на рамнината);
2) раб на ненасочен график – отсечка;
3) лак на насочен граф – насочен сегмент.
Дефиниција 7.2.Ако во работ e=(v 1 ,v 2) се јавува v 1 =v 2, тогаш се вика работ e јамка. Ако графикот дозволува јамки, тогаш тој се нарекува графикон со јамки или псевдограф .
Ако графикот дозволува повеќе од еден раб помеѓу две темиња, тогаш тој се нарекува мултиграф .
Ако секое теме на граф и/или раб е означено, тогаш се нарекува таков график обележан (или натоварени ). Како ознаки обично се користат букви или цели броеви.
Дефиниција 7.3.Графикон Г (В , Е ) повикани потграф (или дел ) графикон Г(В,Е), Ако В В, Е Е. Ако В = В, Тоа Г повикани опфатен потграф Г.
Пример 7 . 1 . Даден е ненасочен график.
Дефиниција 7.4.Графикот се нарекува заврши , Ако било кој неговите две темиња се поврзани со раб. Целосен графикон со nтемиња се означува со К n .
Пребројува К 2 , ДО 3, ДО 4 и К 5 .
Дефиниција 7.5.Графикон Г=Г(В, Е) се нарекува дикотиледони , Ако Вможе да се претстави како унија на дисјунктни множества, да речеме В=АБ, така што секој раб има форма ( v јас , v ј), Каде v јас АИ v ј Б.
Секој раб поврзува теме од A со теме од B, но не се поврзани две темиња од A или две темиња од B.
Се нарекува бипартит граф целосен дикотиледон брои К м , n, Ако Асодржи мврвови, Бсодржи nтемиња и за секој v јас А, v ј Бние имаме ( v јас , v ј)Е.
Така, за сите v јас А, И v ј Бима раб што ги поврзува.
K 12 K 23 K 22 K 33
Пример 7 . 2 . Конструирај целосен бипартитен график К 2.4 и целосниот график К 4 .
График на единицаn-димензионална коцкаВО n .
Темињата на графикот се n-димензионални бинарни множества. Рабовите поврзуваат темиња кои се разликуваат во една координата.
Пример: 
Теорија на графикони- еден од најобемните делови на дискретна математика, широко користен во решавање на економски и менаџерски проблеми, во програмирање, хемија, дизајн и проучување на електрични кола, комуникации, психологија, психологија, социологија, лингвистика и други области на знаење. Теорија на графиконисистематски и доследно ги проучува својствата на графиконите, за кои може да се каже дека се состојат од множества точки и множества на линии кои ги претставуваат врските помеѓу овие точки. За основач на теоријата на графови се смета Леонхард Ојлер (1707-1882), кој го решил тогаш добро познатиот проблем на мостовите Кенигсберг во 1736 година.
Се градат графиконисо цел да се прикажат релациите на множества. Нека, на пример, биде сет А = {а1 , а 2 , ... ан)- многу луѓе, и секој елемент ќе биде прикажан како точка. Еден куп Б = {б1 , б 2 , ... б m)- многу врски (прави линии, лакови, сегменти - сè уште не е важно). На сетот Ададен е односот на запознавање меѓу луѓето од оваа група. Изградба на графиконод точки и спојници. Врските ќе поврзат парови на луѓе кои се познаваат. Секако, бројот на познанства на некои луѓе може да се разликува од бројот на познаници на други луѓе, а некои можеби и не познаваат никого (таквите елементи ќе бидат точки кои не се поврзани со ниту еден друг). Значи, имаме графикон!
Она што прво го нарековме „точки“ треба да се нарече темиња на графикот, а она што го нарековме „врски“ треба да се нарече рабови на графикот.
Теоријата на графикони не ја зема предвид специфичната природа на множествата АИ Б. Има голем број на многу различни специфични проблеми, при решавање на кои може привремено да се заборави на специфичната содржина на множествата и нивните елементи. Оваа специфичност на никаков начин не влијае на напредокот на решавањето на проблемот, без разлика на неговата тежина! На пример, кога се одлучува дали тоа е можно од точка адојде до поентата д, движејќи се само по линиите што ги поврзуваат точките, не е важно дали имаме работа со луѓе, градови, бројки итн. Но, кога проблемот е решен, добиваме решение кое е точно за секоја содржина што е моделирана како график. Затоа, не е изненадувачки што теоријата на графикони е една од најпопуларните алатки за создавање вештачка интелигенција: на крајот на краиштата, вештачката интелигенција може да разговара со соговорникот за прашања на љубовта, прашањата за музика или спорт и прашања за решавање на разни проблеми. , и го прави тоа без никаква транзиција (префрлување) , без која човек не може без во такви случаи.
И сега строгите математички дефиниции на графикот.
Дефиниција 1.Тоа се нарекува графиксистем на објекти од произволна природа (теме) и врски (рабови) што поврзуваат некои парови од овие објекти.
Дефиниција 2.Нека В– (непразно) множество темиња, елементи v∈В- врвови. Графикон Г = Г(В) со многу темиња Впостои одредено семејство на парови на формата: д = (а, б) , Каде а,б∈В , што покажува кои темиња остануваат поврзани. Секој пар д = (а, б) - раб на графикот. Еден куп У- многу рабови дграфикон. Врвови аИ б– крајните точки на работ д .
Графиконите како структура на податоци.Широката употреба на теоријата на графикони во компјутерските науки и информатичката технологија се должи на додавањето на концептот на графикон како структура на податоци на горенаведените дефиниции. Во компјутерските науки и информатичката технологија, графикот се дефинира како нелинеарна структура на податоци. Што е тогаш линеарна структура на податоци и како графиците се разликуваат од нив? Линеарните структури на податоци се карактеризираат со тоа што ги поврзуваат елементите преку врски од типот „просто соседство“. Линеарни структури на податоци се, на пример, низи, табели, списоци, редици, стекови, низи. Спротивно на тоа, нелинеарни структури на податоци се оние во кои елементите се наоѓаат на различни нивоа на хиерархијата и се поделени на три вида: оригинални, генерирани и слични. Значи, графикот е нелинеарна структура на податоци.
Зборот график е од грчко потекло, од зборовите „пишувам“, „опишувам“. Од почетокот на оваа статија знаеме што точно опишува графикот: ги опишува врските. Односно, секој график ги опишува односите. И обратно: секоја врска може да се опише како график.
Основни концепти на теоријата на графикони
Концептот на инциденца е неопходен и кога се развиваат алгоритми за решавање на многу практични проблеми со графикони. На пример, можете да се запознаете со имплементацијата на софтверот длабочина-прва траверза на графикот претставена со матрицата на инциденца. Идејата е едноставна: можете да се движите само низ темиња поврзани со рабови. И ако некои вредности се доделени на рабовите („скали“, најчесто во форма на броеви, таквите графикони се нарекуваат пондерирани или означени), тогаш може да се решат сложени применети проблеми, од кои некои се споменати во последниот став на оваа лекција.
Класични проблеми на теоријата на графикони и нивни решенија
Еден од првите објавени примери на работа на теоријата на графиконите и примената на графиконите е работата за „Проблемот на мостовите на Кенигсберг“ (1736), чиј автор е угледниот математичар од 18 век, Леонхард Ојлер. Проблемот содржи река, острови кои ги мие оваа река и неколку мостови. Прашање на проблемот: дали е можно, по напуштање на одредена точка, секој мост да се помине само еднаш и да се врати на почетната точка? (слика подолу)
Проблемот може да се моделира на следниов начин: една точка е прикачена на секоја копнена површина, а две точки се поврзани со линија ако и само ако соодветните земјишни површини се поврзани со мост (слика подолу, линиите за поврзување се нацртани во точки со точки) . Така, графикот е конструиран.
Одговорот на Ојлер на проблематичното прашање е како што следува. Доколку овој проблем има позитивно решение, тогаш во добиениот график би имало затворена патека што минува по рабовите и ќе го содржи секој раб само еднаш. Ако постои таква патека, тогаш секое теме мора да има само парен број на рабови. Но, добиениот график има темиња кои имаат непарен број на рабови. Затоа, проблемот нема позитивно решение.
Според востановената традиција, Ојлеров граф е график во кој е можно да се поминат сите темиња и во исто време да се помине еден раб само еднаш. Во него, секое теме мора да има само парен број на рабови. Проблем со средна тежина на Ојлеровите графици е во материјалот „Основни типови графикони“.
Во 1847 година, Кирхоф ја развил теоријата на дрвјата за да реши симултан систем на линеарни алгебарски равенки, овозможувајќи да се најде вредноста на струјата во секој проводник (лак) и во секое коло на електричното коло. Апстрахирајќи од електрични кола и кола што содржат отпори, кондензатори, индуктивности итн., тој ги разгледа соодветните комбинаторни структури кои содржат само темиња и врски (рабови или лаци), а за поврзувањата нема потреба да се земат предвид какви видови електрични елементи тие одговараат на . Така, Кирхоф го замени секое електрично коло со соодветен график и покажа дека за да се реши систем од равенки не е неопходно да се разгледува секој циклус од графиконот на електричното коло посебно.
Кејли во 1858 година, додека работел на чисто практични проблеми во органската хемија, открил важна класа на графикони наречени дрвја. Тој се обиде да ги наведе изомерите на заситените јаглеводороди, со даден број на јаглеродни атоми. Кејли прво го формулираше проблемот апстрактно: најдете го бројот на сите дрвја со стртемиња, од кои секое има темиња со степени 1 и 4. Тој не можеше веднаш да го реши овој проблем и почна да ја менува неговата формулација на таков начин што може да се реши нов проблем со набројување:
- вкоренети дрвја (во кои е избрано едно од темињата);
- сите дрвја;
- дрвја чии степени на теме не надминуваат 4;
- дрвја чии степени на теме се 1 и 4 (изнесување проблем од хемијата).
Графикон проблеми за зајакнување на основните концепти
Пример 1.Нека А- збир на броеви 1, 2, 3: А= (1, 2, 3) . Конструирај график за да се прикаже врската "
Решение. Очигледно, броевите 1, 2, 3 треба да бидат претставени како темиња на граф. Тогаш секој пар темиња мора да биде поврзан со еден раб. Решавајќи го овој проблем, дојдовме до такви основни концепти на теоријата на графикони како насочени и ненасочени графикони. Ненасочени графици се оние чии рабови немаат насока. Или, како што велат уште почесто, редоследот на двата краја на раб не е значаен. Всушност, на графиконот конструиран на самиот почеток на оваа лекција и кој го одразува односот на познанства меѓу луѓето не му требаат рабови насоки, бидејќи може да се тврди дека „личноста број 1“ е запознаена со „личноста број 2“ во иста мера. како „лице број 2“ со „лице број 1“. Во нашиот сегашен пример, еден број е помал од друг, но не и обратно. Според тоа, соодветниот раб на графикот мора да има насока што покажува кој број е помал од другиот. Тоа е, редоследот на краевите на рабовите е значаен. Таков график (со рабови кои имаат насока) се нарекува насочен график или диграф.
Значи, во нашето мноштво Абројот 1 е помал од бројот 2 и бројот 3, а бројот 2 е помал од бројот 3. Овој факт го прикажуваме со рабови кои имаат насока, која е прикажана со стрелки. Го добиваме следниот графикон:
Пример 2.Нека А- збир на броеви 2, 4, 6, 14: А= (2, 4, 6, 14) . Направете графикон за прикажување на релацијата „делива со“ на ова множество.
Решение. Во овој пример, некои од рабовите ќе имаат насока, а некои нема, односно градиме мешан график. Да ги наброиме односите во множеството: 4 се дели со 2, 6 се дели со 2, 14 се дели со 2, а секој број од ова множество се дели само по себе. Оваа релација, односно кога некој број е делив сам со себе, ќе се прикаже во форма на рабови што го поврзуваат темето со себе. Таквите рабови се нарекуваат јамки. Во овој случај, нема потреба да се дава насока на јамката. Така, во нашиот пример има три редовни насочени рабови и четири јамки. Го добиваме следниот графикон:
Пример 3.Нека дадени сетови А= (α, β, γ) и Б= (а, б, в) . Конструирај график за да ја прикаже врската „Декартов производ на множества“.
Решение. Како што е познато од дефиницијата Декартов производ на множества, нема подредени множества на елементи од истото множество. Тоа е, во нашиот пример, не можете да комбинирате грчки букви со грчки и латински со латински. Овој факт се прикажува како бипартитен график, односно оној во кој темињата се поделени на два дела така што темињата што припаѓаат на истиот дел не се поврзани едно со друго. Го добиваме следниот графикон:
Пример 4.Во агенцијата за недвижности се вработени менаџерите Игор, Сергеј и Петар. Објектите O1, O2, O3, O4, O5, O6, O7, O8 се сервисираат. Конструирај график за прикажување на односите „Игор работи со објекти О4, О7“, „Сергеј работи со предмети О1, О2, О3, О5, О6“, „Петар работи со објект О8“.
Решение. Графикот што ги прикажува овие врски исто така ќе биде бипартитен, бидејќи менаџерот не работи со менаџерот и објектот не работи со објектот. Меѓутоа, за разлика од претходниот пример, графикот ќе биде насочен. Всушност, на пример, Игор работи со објектот О4, но објектот О4 не работи со Игор. Честопати, кога таквото својство на односите е очигледно, потребата да се даде насока на рабовите може да изгледа како „математичка глупост“. Но, сепак, и ова произлегува од строгата природа на математиката, ако односот е едностран, тогаш е неопходно да се дадат насоки до рабовите. Во релационите апликации, оваа строгост се исплати, на пример, во програмите дизајнирани за планирање, каде што се користат и графикони и маршрутата по темињата и рабовите мора да помине строго во дадена насока. Значи, го добиваме следниов насочен бипартит граф:
И повторно на примери со бројки.
Пример 5.Нека се даде сет В = {2, 3, 5, 6, 15, 18} . Конструирај график кој имплементира релација што ги дефинира сите парови на броеви аИ бод многу В, при што при делење на вториот елемент со првиот добиваме количник кој е цел број поголем од 1.
Решение. Графикот што ги прикажува овие врски ќе биде ориентиран, бидејќи условот содржи спомнување на вториот и првиот елемент, односно работ ќе биде насочен од првиот елемент кон вториот. Од ова е јасно кој елемент е првиот, а кој вториот. Ајде да додадеме и некоја терминологија: ориентираните рабови обично се нарекуваат лаци. Ќе има 7 лакови во нашиот график: д1 = (3, 15) , д2 = (3, 18) , д3 = (5, 15) , д4 = (3, 6) , д5 = (2, 18) , д6 = (6, 18) , д7 = (2, 6) . Во овој пример, рабовите (лаците) на графикот се едноставно нумерирани, но сериските броеви не се единственото нешто што може да се додели на лакот. На лакот може да му се доделат и скали што значи, на пример, трошоците за испраќање товар од една до друга точка. Но, со лачните тежини ќе се запознаеме подоцна и подетално. Значи, го добиваме следниот насочен график:
Како што веќе знаеме од теоретскиот воведен дел, теоријата на графови не ја зема предвид специфичната природа на множествата и со помош на истиот графикон е можно да се дефинираат релации на множества со многу различни содржини. Односно, од оваа содржина може да се апстрахира при моделирање на задача. Ајде да продолжиме со примери кои го илустрираат ова извонредно својство на теоријата на графикони.
Пример 6.На парче шаховска табла со димензии 3 X 3 се поставени два бели витези и два црни витези како што е прикажано на сликата подолу.
Дали е можно да се преместат витезите во состојбата прикажана на следната слика, не заборавајќи дека две парчиња не можат да бидат на ист квадрат?
Решение. Во конструираниот график, паровите темиња ќе се поврзат со релацијата „витерски потег“. Односно, едното теме е она од кое заминал витезот, а другото е она до кое пристигнал, а средната ќелија на буквата „р“ ќе биде надвор од оваа врска. Го добиваме следниот графикон:
А сепак дизајнот се покажа како тежок. Во неа се видливи ќелиите на шаховска табла, а многу од рабовите на графикот се сечат. Дали е можно да се апстрахира од физичкиот изглед на шаховската табла и да се замисли врската поедноставно? Излегува дека тоа е можно. Во новиот график, соседните темиња ќе бидат оние што се поврзани со односот „витерски потег“, а не оние што се соседни на шаховската табла (слика подолу).
Сега е лесно да се види дека одговорот на прашањето за овој проблем е негативен. Во почетната состојба не постои црн витез помеѓу двајца бели витези, но во крајната состојба мора да постои овој црн витез. Рабовите на графиконот се поставени така што двајца соседни витези не можат да скокаат еден преку друг.
Пример 7.Проблемот за волкот, козата и зелката. На едниот брег од реката има човек (H), чамец, волк (V), коза (Kz) и зелка (Kp). Едно лице и не повеќе од еден од транспортираните предмети можат да бидат во чамецот истовремено. Човек мора да ги пренесе сите предмети на другата страна, почитувајќи го условот: волк не смее да се остави без надзор со коза и коза со зелка.
Решение. Во конструираниот график, темињата се конфигурации, а рабовите се врската „поврзување со едно возење со брод“ помеѓу конфигурациите. Конфигурацијата се однесува на распоредот на предметите на оригиналниот брег и на спротивниот брег. Секоја конфигурација се прикажува како ( А|Б), Каде А- предмети лоцирани на првобитниот брег, и Б- објекти лоцирани на спротивниот брег. Затоа, почетната конфигурација е - (PMCpKz| ) . На пример, по транспортирање на коза на другата страна, конфигурацијата ќе биде (VKp|ChKz) . Конечната конфигурација е секогаш ( |PMCpKz) . Сега можеме да изградиме график, веќе знаејќи што значат темињата и рабовите:
Да ги поставиме темињата на графикот така што рабовите да не се сечат, а соседните темиња се оние кои се поврзани со врска на графикот. Тогаш ќе биде многу полесно да ги видите врските (за да ја зголемите сликата, кликнете со левото копче на неа):
Како што можеме да видиме, постојат две различни континуирани правци од почетната конфигурација до конечната. Затоа, проблемот има две различни решенија (и двете се точни).
Теорија на графикони и најважните современи применети проблеми
Врз основа на теоријата на графикони, развиени се методи за решавање на применети проблеми во кои се моделираат многу сложени системи во форма на графикони. Во овие модели, јазлите содржат поединечни компоненти, а рабовите претставуваат врски помеѓу компонентите. Вообичаено, пондерираните графикони се користат за моделирање на транспортни мрежи, системи за редици и планирање на мрежата. Веќе разговаравме за нив; ова се графикони во кои тежините се доделуваат на лаците.
Графиконите на дрвото се користат, на пример, за конструирање дрва за одлучување(служат за анализа на ризик, анализа на можни добивки и загуби во услови на неизвесност). Користење на теоријата на графикони, развиена и други бројни математички моделида решаваат проблеми од одредени предметни области.
Графикони и проблем со текот
Формулирање на проблемот. Постои систем на водоводни цевки, претставен со графиконот на сликата подолу.
Секој лак на графиконот претставува цевка. Броевите над лаците (скалите) се капацитетот на цевката. Јазли се места каде цевките се поврзани. Водата тече низ цевките само во една насока. Јазол С- извор на вода, јазол Т- залиха. Потребно е да се максимизира волуменот на вода што тече од изворот до одводот.
За да го решите проблемот со протокот, можете да го користите методот Форд-Фулкерсон. Идејата на методот: пребарувањето за максимален проток се врши во чекори. На почетокот на алгоритмот, протокот е поставен на нула. На секој следен чекор се зголемува вредноста на протокот, за што се бара комплементарен пат низ кој пристигнува дополнителниот проток. Овие чекори се повторуваат се додека постојат дополнителни патеки. Проблемот успешно се применува во различни дистрибуирани системи: систем за напојување, комуникациска мрежа, железнички систем и други.
Графикони и мрежно планирање
При планирање на проблемите на сложени процеси кои се состојат од многу работни места, од кои некои се изведуваат паралелно, а некои секвенцијално, широко се користат пондерирани графикони, познати како PERT мрежи.
PERT - Програма (Проект) Техника за евалуација и преглед - техника за евалуација и анализа на програми (проекти), која се користи во управувањето со проекти.
Мрежата PERT е пондериран ацикличен насочен график во кој секој лак претставува задача (дејство, операција), а тежината на лакот е времето потребно за да се заврши.
Ако има лакови во мрежата ( а, б) И ( б, в), потоа работата претставена со лакот ( а, б) мора да се заврши пред работата претставена со лакот ( б, в) . Секое теме ( vз)ја претставува временската точка до која целата работа, дефинирана со лакови што завршуваат на теме ( vз).
Во ваква колумна:
- едно теме, кое нема претходници, го одредува времето на започнување на работата;
- едно теме, кое нема следбеници, одговара на временскиот момент кога се комплетира множеството дела.
Патеката со максимална должина помеѓу овие темиња на графикот (од почетокот до крајот на работниот процес) се нарекува критична патека. За да се намали времето потребно за завршување на целиот комплекс на работа, неопходно е да се најде работа што лежи на критичната патека и да се намали нејзиното времетраење со, на пример, привлекување дополнителни изведувачи, механизми и нови технологии.
Целиот блок „Теорија на графикони“
Теоријата на графикони е гранка од математиката која се користи во компјутерските науки и програмирањето, економијата, логистиката и хемијата.
Што е график
Графичките дијаграми често се користат за да се опише структурата на системите. Елементите во нив се претставени со кругови, точки, квадрати итн., а врските меѓу елементите се претставени со линии или стрелки. Во овој случај, не е важно ниту како се прикажани елементите, ниту должината или обликот на линиите - важно е само кои елементи се поврзани. Значи, графикот е пар од формата (A, M), каде што A е конечно множество темиња, а M е збир на рабови - линии што поврзуваат некои темиња.
Основни концепти на теоријата на графикони
Ориентираниот график или диграф (види слика подолу) има ориентирани рабови, наречени лакови и прикажани со стрелки. Лакот може да се означи со подреден пар темиња што ги поврзува, почеток и крај.
Ненасочен график (види слика подолу) има рабови кои се нацртани како линии без ориентација. Според тоа, парот темиња поврзани со раб е неуреден. И двете од овие темиња се краеви на работ.
Ако темињата a и b се краеви на раб (или почеток и крај на лакот) на графиконот, тогаш темињата a и b се вели дека се склопени на овој раб (лак), а работ (лак) е исто така инцидент на темињата a и b. Ако темињата a и b се краеви на раб, тогаш тие (a и b) се нарекуваат соседни.
Најчесто, ги разгледуваме графиците чии рабови се од еден тип - без разлика дали се насочени или не.
Ако рабовите имаат ист почеток и крај, тогаш тие се нарекуваат повеќекратни рабови, а графикот во кој се присутни се нарекува мултиграф.
Теоријата на графикони го користи и концептот на „јамка“ - раб што излегува и оди во истото теме. Графикот кој има јамки се нарекува псевдограф.
Најчести се ненасочените графикони, кои немаат повеќекратни рабови и без јамки. Таквите графикони се нарекуваат обични. Тие немаат повеќе рабови, така што можеме да идентификуваме раб и соодветниот пар темиња.
Секое теме на диграфот се карактеризира со:
- Половина степен на исход. Ова е бројот на лакови што излегуваат од него.
- Половина степен на пристап. Ова е бројот на лакови кои влегуваат во дадено теме.
Збирот на полустепените на внесувањето на диграф, како и збирот на полустепените на исходот, се еднакви на вкупниот број на лакови на графикот.
Во ненасочен график, секое теме се карактеризира со степенот на темето. Ова е бројот на рабовите што се склопуваат на теме. Вкупниот збир на степените на темињата на графикот е бројот на рабовите помножен со два: секој раб ќе придонесе со придонес кој е еднаков на два.
Темето со степен 0 се нарекува изолирано.
Висечко теме е теме со степен 1.
Теоријата на графикони нарекува празен график во кој нема рабови. Целосен график е обичен график во кој било кои 2 темиња се соседни.
Пондерираните графикони се графикони на чии темиња или рабови (лакови), или и на темињата и на рабовите (лакови) одеднаш, им се доделуваат одредени броеви. Тие се нарекуваат ваги. Втората слика покажува ненасочен график чии рабови се пондерирани.
Графикони: изоморфизам
Концептот на изоморфизам се користи во математиката. Конкретно, теоријата на графови ја дефинира на следниов начин: два графика U и V се изоморфни ако во овие графикони постои биекција помеѓу множествата на нивните темиња: секои 2 темиња во графот U се поврзани со раб ако и само ако во График V истите се поврзани со врвни темиња (кои може да имаат различни имиња). Сликата подолу покажува два изоморфни графикони во кои бијекцијата опишана погоре постои помеѓу темињата обоени во исти бои и на првиот и на вториот графикон.
Патеки и циклуси
Патека во ненасочен или насочен граф е низа од рабови, каде што секој следен започнува на темето каде што завршува претходниот. Едноставна патека е онаа во која сите темиња, освен можеби почетокот и крајот, и рабовите се различни. Циклус во диграф е патека чии почетни и завршни темиња се совпаѓаат и која вклучува најмалку еден раб. Циклус во ненасочен график е патека која содржи најмалку три различни рабови. На втората слика, циклусот е, на пример, патеката (3, 1), (6, 3), (1, 6).
Теоријата на графикони во програмирањето се користи за конструирање графички дијаграми на алгоритми.