Неформално, графикот може да се замисли како збир на точки и линии што ги поврзуваат овие точки, со или без стрелки.
Првото дело на теоријата на графови како математичка дисциплина се смета за трудот на Ојлер (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. Упатена мрежа (или едноставно мрежа) е насочен графикон без контура*. Бидејќи мрежата е график без контура, може да се покаже дека има темиња (јазли) на мрежата со нула надвор-степен, како и темиња (јазли) со нула во-степен. Првите се нарекуваат мијалници или излези на мрежата, а вторите се нарекуваат извори или влезови на мрежата.
Елементи на цикломатика
Кога се дискутираше за алгоритам за пребарување на прво длабочина во ненасочен график, беше разгледано прашањето за пребарување на таканаречените фундаментални циклуси на графикот. Во овој случај, фундаменталниот циклус беше сфатен како циклус кој содржи точно еден обратен раб, и беше воспоставена кореспонденција еден-на-еден помеѓу основните циклуси и обратните основни циклуси секогаш кога се појавува произволна поделба на сите рабови на ненасочен график; дрва (формирајќи некоја максимална рабна шума на оригиналниот график) и инверзна, а во општ случај оваа партиција може да се специфицира целосно независно од алгоритмот за пребарување длабочина-прва. Првото пребарување во длабочина е само еден начин да се имплементира таква партиција.
Теоријата на графикони е гранка од математиката која се користи во компјутерските науки и програмирањето, економијата, логистиката и хемијата.
Што е график
Графичките дијаграми често се користат за да се опише структурата на системите. Елементите во нив се претставени со кругови, точки, квадрати итн., а врските меѓу елементите се претставени со линии или стрелки. Во овој случај, не е важно ниту како се прикажани елементите, ниту должината или обликот на линиите - важно е само кои елементи се поврзани. Значи, графикот е пар од формата (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).
Теоријата на графикони во програмирањето се користи за конструирање графички дијаграми на алгоритми.
Книгата на К. Берге е прва за теоријата на графикони на руски јазик. Во меѓувреме, во последниве години, интересот за теоријата нагло се зголеми и од страна на математичарите и од претставниците на широк спектар на дисциплини. Ова се објаснува со фактот дека методите на теоријата на графикони успешно решаваат бројни проблеми во теоријата на електрични кола, теоријата на транспортните синџири, теоријата на информации, кибернетиката итн.
Во книгата на Берге, теоријата на графови е претставена последователно, почнувајќи од самите основи. Се претпоставува дека читателот има многу скромно математичко знаење, иако има одредена математичка култура. Текстот вклучува бројни, често смешни примери. Книгата може да се користи за првично проучување на теоријата на графикони. Во него и професионалните математичари ќе најдат многу интересни работи.
Алгоритам за директно идентификување на Ојлеров циклус.
[Флери]. Да разгледаме поврзан мултиграф G, чиишто темиња имаат парен степен и ќе се обидеме да го нацртаме со еден потег, без прибегнување кон корекции во веќе нацртаниот дел од траекторијата за време на процесот на изградба. Доволно е да се придржувате до следново правило:
1 Излегуваме од произволно теме a; Секој поминат раб го прекрстуваме.
2 Никогаш не одиме по таков раб и, кој во моментот што се разгледува е истмус (т.е., кога ќе се отстрани, графикот формиран од непрекрстени рабови се дели на две поврзани компоненти кои имаат најмалку по еден раб).
Следејќи го ова правило, секогаш ќе бидеме во поволна положба, бидејќи кога сме на x = a, графикот (на непрекрстените рабови) има две темиња со непарен степен: x и a; ако изолираните темиња се отфрлени, тогаш останува поврзан график, кој, врз основа на теорема 1, има Ојлеров синџир што започнува на x.
содржина
Вовед
Поглавје 1. Основни дефиниции
Сетови и повеќевредни мапирања
Графикон. Патеки и контури
Кола и циклуси
Поглавје 2. Прелиминарна студија за квазиуредноста
Квази ред дефиниран со графикон
Индуктивен график и основи
Поглавје 3. Редна функција и функција
Грунди за бесконечен график
Општи размислувања во врска со бесконечните графикони
Редна функција
Функции на грунди
Операции на графикони
Поглавје 4. Основни броеви на теоријата на графикони
Цикломатски број
Хроматски број
Број на внатрешна стабилност
Број на надворешна стабилност
Поглавје 5. Јадра на графикони
Теореми за постоење и единственост
Примена за Grundy функции
Поглавје 6. Игри со графикони
Игра Ним
Општа дефиниција на играта (со целосни информации)
Стратегии
Поглавје 7. Проблем со најкратката патека
Процеси по фази Некои генерализации
Поглавје 8. Транспортни мрежи
Проблем со максимален проток Проблем со најмал проток
Проблем со протокот компатибилен со поставената вредност
Бескрајни транспортни мрежи
Поглавје 9. Теорема за полусили
Полу-степен на излез и влез
Поглавје 10. Усогласување на едноставен график
Проблем со максимален совпаѓање
Едноставен недостаток на графикони
Унгарски алгоритам
Генерализација на бесконечниот случај
Примена во теоријата на матрицата
Поглавје 11. Фактори
Хамилтонови патеки и Хамилтонови контури
Наоѓање фактор
Наоѓање на делумен график со дадени полустепени
Поглавје 12. Графички центри
Центри
Радиус
Поглавје 13. Дијаметар на силно поврзан график
Општи својства на силно поврзани графикони без јамки
Дијаметар
Поглавје 14. Графичка матрица на соседство
Примена на конвенционални матрични операции
Проблеми со броење
Проблем со лидерот
Користење на Булови операции
Поглавје 15. Матрици на инциденти
Целосно унимодуларни матрици
Целосно унимодуларни системи
Цикломатски матрици
Поглавје 16. Дрвја и дрва од предците
Дрвја
Аналитичко истражување
Големи дрвја
Поглавје 17. Ојлеровиот проблем
Ојлер циклуси Ојлерови контури
Поглавје 18. Усогласување на произволен график
Теорија на наизменична кола
Наоѓање делумен график со дадени степени на теме
Совршено совпаѓање
Примена на бројот за внатрешна стабилност
Поглавје 19. Фактороиди
Хамилтонови циклуси и фактороиди
Неопходен и доволен услов за постоење на фактороид
Поглавје 20. Поврзување на графикони
Точки за артикулација
Графикони без артикулации
h-поврзани графикони
Поглавје 21. Планарни графикони
Основни својства
Генерализација
Дополнувања
I. Исклучена општа теорија, игри
II. За транспортните задачи
III. За употребата на потенцијалните концепти во транспортните мрежи
IV. Нерешени проблеми и недокажани претпоставки
V. За некои основни принципи на броење (Ј. Риге)
VI. Дополнувања на рускиот превод (А.А. Зиков и Г.И. Кожухин)
Литература
Теорија на графикони и книгата на C. Berge (поговор на рускиот превод)
Индекс на знаци
Индекс на имиња
Индекс на тема.
Преземете ја е-книгата бесплатно во пригоден формат, гледајте и читајте:
Преземете ја книгата Теорија на графикони и нејзините апликации, Berge K. - fileskachat.com, брзо и бесплатно преземање.
Теоријата на графикони е гранка на дискретната математика која ги проучува објектите претставени како поединечни елементи (темења) и врските меѓу нив (лакови, рабови).
Теоријата на графикони потекнува од решението на проблемот на мостовите Кенигсберг во 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-димензионални бинарни множества. Рабовите поврзуваат темиња кои се разликуваат во една координата.
Пример: 
Графиконите се забавна, наградувачка и застрашувачка тема. Теорија на графикони - „Ужас на студентите“. Графиком алгоритмите се неверојатните умови на луѓето кои ги откриле.
Што е график? За да одговорам на ова прашање за моите читатели, ќе ја опишам темата малку поинаку.
График е збир на објекти.
Во повеќето проблеми тоа се предмети од ист тип. (Многу градови, или многу куќи, или многу луѓе, или многу други работи од ист тип)
За да ги решите проблемите со таков сет, треба да го назначите секој објект од овој сет како нешто. Општо е прифатено токму ова да се нарекува темиња на графикот.
Удобно е да се опишуваат графикони и основни дефиниции со слики, затоа мора да се вклучат слики за да се прочита оваа страница.
Како што напишав претходно, графикот е збир на објекти. Овие предмети обично се од ист тип. Најлесен начин да се даде пример е во градовите. Секој од нас знае што е град, а што пат. Секој од нас знае дека може да има или нема патишта до градот. Општо земено, секој сет на објекти може да се карактеризира како график.
Ако зборуваме за графикот како за градови, тогаш може да се градат патишта меѓу градовите, или може да се уништи некаде, да не се гради, или градот генерално се наоѓа на остров, нема мост, а интерес се само асфалтираните патишта. . И покрај фактот што нема пат до таков град, овој град може да биде вклучен во многу анализирани објекти, а сите предмети земени заедно сочинуваат збирка предмети или, поедноставно кажано, графикон.
Сигурно сте читале учебници и сте ја виделе оваа ознака G(V,E) или нешто слично. Значи, V е некој објект од целиот сет на објекти. Во нашиот случај, множеството објекти се градови, затоа, V е специфичен град. Бидејќи објектите не се нужно градови, а зборот објект може да биде збунувачки, таков објект од множеството може да се нарече точка, точка или нешто друго, но најчесто се нарекува теме на графикот и се означува со буквата В.
Во програмирањето, ова е обично или колона или ред од дводимензионална низа, каде што низата се нарекува или матрица на соседство или матрица на инциденца.
Во литературата, на Интернет и генерално секаде каде што се пишува нешто за графиконите, ќе наидете на концепти како што се лакови и рабови. Оваа слика ги прикажува рабовите на графиконот. Оние. тоа се три рабови Е1, Е2 и Е3.
Лакот и работ се разликуваат по тоа што раб е двонасочна врска. Сакаше, отиде кај комшијата, сакаше, се врати од комшијата. Ако не е многу јасно, тогаш можете да замислите куќа, аеродром, летачки авион и падобранец. Падобран може да оди од својот дом до аеродромот, но кога ќе пристигне на аеродромот, се сеќава дека го заборавил својот среќен падобран дома, а потоа се враќа дома и го зема падобранот. — Патот по кој можете да одите напред-назад се нарекува раб.
Ако падобранец е во авион и скока од авионот, но падобранецот заборавил да го стави својот среќен падобран во авионот, дали падобранот ќе може да го земе она што го заборавил? Патеката што оди само во една насока се нарекува лак. Обично велиме дека раб поврзува две темиња, а лак оди од едно теме до друго.
На оваа слика, графикот има само лакови. Лаците на графикот се означени со стрелки, бидејќи пристапната насока е толку јасна. Ако графикот се состои само од такви лакови, тогаш таквиот график се нарекува насочен.
 |
Честопати ќе наидете на концепти за близина и инциденца. На сликата со црвено се означени два рабови кои одат до една точка. Таквите рабови, како темињата опишани погоре, се нарекуваат и соседни. |
Многу не е опишано, но оваа информација може да помогне некому.