Темата за графиките е интересна, полезна и плашеща тема. Теория на графите - "Студентски ужас". Графичните алгоритми са удивителен ум на хората, които са ги открили.

Какво е графика? За да отговоря на този въпрос за моите читатели, ще опиша темата малко по свой начин.
Графиката е набор от обекти.
В повечето задачи това са еднотипни обекти. (Много градове, или много къщи, или много хора, или много нещо друго от същия тип)

За да разрешите проблеми с такова множество, трябва да обозначите всеки обект от това множество като нещо. Обичайно е това нещо да се нарича върхове на граф.

Удобно е да се описват графики и основни дефиниции със снимки, така че трябва да бъдат включени снимки, за да прочетете тази страница.

Както писах по-рано, графиката е набор от обекти. Тези обекти обикновено са от един и същи тип. Най-лесно може да се даде пример в градовете. Всеки от нас знае какво е град и какво е път. Всеки от нас знае, че може да има или да няма пътища до града. Като цяло, всеки набор от обекти може да се характеризира като графика.

Ако говорим за броя като градове, тогава пътищата могат да бъдат положени между градовете или могат да бъдат унищожени някъде, да не са построени, или градът обикновено се намира на остров, няма мост и представляват интерес само павирани пътища. Въпреки факта, че няма път до такъв град, този град може да бъде включен в набор от анализирани обекти и всички обекти, взети заедно, съставляват набор от обекти или, по-просто, графика.

Със сигурност сте чели учебници и сте виждали такава нотация G(V,E) или нещо подобно. И така, V е някой един обект от цялото множество обекти. В нашия случай наборът от обекти са градове, следователно V е определен град. Тъй като обектите не са непременно градове и думата обект може да бъде объркваща, такъв обект от множеството може да се нарече точка, точка или нещо друго, но най-често се нарича връх на графиката и се обозначава с буквата V.
В програмирането това обикновено е колона или ред от двумерен масив, където масивът се нарича или матрица на съседство, или матрица на инцидентност.

В литературата, в интернет и изобщо, където и да се пише нещо за графи, ще срещнете такива понятия като дъги и ръбове. Тази фигура показва ръбовете на графика. Тези. това са три ръба E1, E2 и E3.

Дъгата и ръбът се различават по това, че ръбът е такава двупосочна връзка. Търсеше, отиде при съсед, искаше, върна се от съсед. Ако не е много ясно, можете да си представите къща, летище, летящ самолет и парашутист. Парашутистът може да отиде от дома си до летището, но когато дойде на летището, не забравяйте, че е забравил щастливия си парашут у дома, след това се върнете у дома и вземете парашут. - Такъв път, по който можете да вървите напред-назад, се нарича ребро.
Ако парашутистът е в самолета и скача от самолета, но той е забравил да сложи щастливия си парашут в самолета, ще може ли парашутистът да вземе това, което е забравил? Път, който върви само в една посока, се нарича дъга. Обикновено се казва, че ръбът свързва два върха, а дъгата преминава от един връх към друг.

На тази фигура графиката има само дъги. Дъгите на графиката са обозначени със стрелки, тъй като наличната посока е толкова ясна. Ако графът се състои само от такива дъги, тогава такъв граф се нарича насочен.

Често ще срещате понятията за съседство и инцендентност. На фигурата два ръба, които отиват в една и съща точка, са маркирани в червено. Такива ръбове, подобно на описаните по-горе върхове, се наричат ​​също съседни.

Много не е описано, но тази информация може да помогне на някого.

ОБЩИНСКО АВТОНОМНО ОБЩООБРАЗОВАТЕЛНО ЗАВЕДЕНИЕ СРЕДНО ОБРАЗОВАТЕЛНО УЧИЛИЩЕ № 2

Подготвени

Легкоконец Владислав, 10А ученик

Практическа употребаТеории на графите

Ръководител

Л.И. Носкова, учител по математика

ул.Брюховецка

2011 г

1. Въведение………………………………………………………………………………………….3

2. Историята на появата на теорията на графите……………………………………………………..4

3. Основни дефиниции и теореми на теорията на графите……………………………….………6

4. Задачи, решени с помощта на графики……………………………..………………………..8

4.1 Известни задачи………………………………….………………………...8

4.2 Няколко интересни задачи………………………………….……………..9

5. Приложение на графики в различни областиживота на хората……………………………...11

6. Решаване на проблеми………………………………………………………………………………...12

7. Заключение………………….…………………………………………………………….13

8. Списък с литература………….…………………………………………………………………………………………………………… ……………………………………………………………………………………………………………………………………… …………………………………………………………………………………………………………………….

9. Приложение………………………………………………………………………………………15

Въведение

Роден да решава пъзели и занимателни игри, теорията на графите вече се превърна в прост, достъпен и мощен инструмент за решаване на проблеми, свързани с широк кръг от проблеми. Графиките са буквално вездесъщи. Под формата на графики можете например да интерпретирате пътни карти и електрически вериги, географски картии молекули химични съединения, връзки между хора и групи от хора. През последните четири десетилетия теорията на графите се превърна в един от най-бързо развиващите се клонове на математиката. Това се дължи на изискванията на бързо разширяваща се област на приложение. Използва се при проектирането на интегрални схеми и схеми за управление, при изучаване на автомати, логически схеми, блок-схеми на програми, в икономиката и статистиката, химията и биологията, в теорията на планирането. Ето защо уместносттемата се дължи, от една страна, на популярността на графиките и свързаните с тях изследователски методи, а от друга страна, не е разработена, цялостна системаизпълнението му.

Решение на много житейски задачиизисква дълги изчисления и понякога тези изчисления не носят успех. Ето в какво се състои изследователски проблем. Възниква въпросът: възможно ли е да се намери просто, рационално, кратко и елегантно решение за тяхното разрешаване. По-лесно ли е да решавате проблеми, ако използвате графики? Това определи тема на моето изследване: "Практическо приложение на теорията на графите"

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

Изследователска хипотеза.Графичният метод е много важен и широко използван в различни области на науката и човешкия живот.

Цели на изследването:

1. Да се ​​проучи литературата и интернет ресурсите по този въпрос.

2. Проверете ефективността на графовия метод при решаване на практически задачи.

3. Направете заключение.

Практическо значениеизследванияе, че резултатите несъмнено ще предизвикат интереса на много хора. Някой от вас не се ли е опитвал да изгради родословно дърво на вашето семейство? И как да го направите правилно? Ръководителят на транспортна фирма вероятно трябва да реши проблема с по-рентабилното използване на транспорта при превоз на стоки от дестинация до няколко населени места. Всеки ученик се изправи пред логически задачи за трансфузия. Оказва се, че те се решават лесно с помощта на графики.

Работата използва следните методи: наблюдение, търсене, подбор, анализ.

Историята на възникването на теорията на графите

Математикът Леонхард Ойлер (1707-1783) се смята за основател на теорията на графите. Историята на възникването на тази теория може да бъде проследена чрез кореспонденцията на великия учен. Ето и превода латински текст, което е взето от писмото на Ойлер до италианския математик и инженер Маринони, изпратено от Санкт Петербург на 13 март 1736 г.

„Веднъж ми дадоха проблем за остров, разположен в град Кьонигсберг и заобиколен от река, през която са прехвърлени седем моста.

[Приложение Фиг.1]Въпросът е дали някой може да ги обикаля непрекъснато, минавайки по един път през всеки мост. И тогава бях информиран, че все още никой не е успял да направи това, но никой не е доказал, че е невъзможно. Този въпрос, макар и банален, ми се стори все пак достоен за внимание, защото нито геометрията, нито алгебрата, нито комбинаториката са достатъчни за неговото решение. След дълго мислене открих лесно правило, основано на напълно убедително доказателство, с помощта на което е възможно незабавно да се определи във всички задачи от този вид дали такъв обход може да се направи през произволен брой и произволно разположени мостове или не. Мостовете на Кьонигсберг са разположени така, че да могат да бъдат представени на следващата фигура [Приложение Фиг.2], където A означава остров, а B , C и D са части от континента, разделени една от друга с речни ръкави

Относно открития от него метод за решаване на проблеми от този вид, Ойлер пише:

„Това решение, по своето естество, изглежда има малко общо с математиката и не ми е ясно защо това решение трябва да се очаква от математик, а не от който и да е друг човек, тъй като това решение се поддържа само от разума и няма нужда да се включват, за да се намери това решение, каквито и да било закони, присъщи на математиката. Така че, не знам как се оказва, че въпросите, които имат много малко общо с математиката, е по-вероятно да бъдат решени от математиците, отколкото от други."

И така, възможно ли е да заобиколите мостовете на Кьонигсберг, като преминете само веднъж през всеки от тези мостове? За да намерим отговора, нека продължим писмото на Ойлер до Маринони:

„Въпросът е да се определи дали е възможно да се заобиколят всички тези седем моста, минавайки през всеки само веднъж, или не. Моето правило води до следващото решениетози въпрос. Най-напред трябва да погледнете колко зони са разделени от вода – такива, които нямат друг преход от една към друга, освен през мост. AT този примерима четири такива секции - A, B, C, D. След това трябва да се разграничи дали броят на мостовете, водещи до тези отделни участъци, е четен или нечетен. И така, в нашия случай пет моста водят до участък А, а три моста към останалите, т.е. броят на мостовете, водещи към отделните участъци, е нечетен и този вече е достатъчен за решаване на проблема. Когато това се определи, ние прилагаме следното правило: ако броят на мостовете, водещи до всеки отделен раздел, беше дори, тогава обходът, за който въпросният, би било възможно, като в същото време би могло да се започне този обход от който и да е участък. Ако обаче две от тези числа са нечетни, тъй като само едното не може да бъде нечетно, тогава дори и тогава преходът може да се осъществи, както е предписано, но само началото на отклонението трябва непременно да бъде взето от един от тези два участъка, към които не четен броймостове. Ако в крайна сметка имаше повече от два участъка, към които води нечетен брой мостове, тогава такова движение по принцип е невъзможно ... ако тук могат да се цитират други, по-сериозни проблеми, този метод може да бъде още по-полезен и не трябва бъдете пренебрегнати ".

Основни определения и теореми на теорията на графите

Теорията на графите е математическа дисциплина, създадена от усилията на математиците, така че нейното представяне включва необходимите строги дефиниции. И така, нека пристъпим към организираното въвеждане на основните понятия на тази теория.

Определение 1.Графиката е колекция крайно числоточки, наречени върхове на графиката, и свързващи по двойки някои от тези върхове на линии, наречени ръбове или дъги на графиката.

Тази дефиниция може да се формулира по различен начин: графът е непразно множество от точки (върхове) и сегменти (ръбове), двата края на които принадлежат на дадено множество от точки

По-нататък ще бъдат означени върховете на графа с латински букви A, B, C, D. Понякога графиката като цяло ще бъде означена с единица Главна буква.

Определение 2.Върховете на графа, които не принадлежат на нито едно ребро, се наричат ​​изолирани.

Определение 3.Граф, състоящ се само от изолирани върхове, се нарича нулев - броя .

Нотация: O "– график с върхове и без ръбове

Определение 4.Граф, в който всяка двойка върхове е свързана с ребро, се нарича пълен.

Обозначение: U" – граф, състоящ се от n върха и ребра, свързващи всички възможни двойки от тези върхове. Такава графика може да бъде представена като n-ъгълник, в който са начертани всички диагонали

Определение 5.Степента на върха е броят на ръбовете, към които принадлежи върхът.

Определение 6.Граф, чиито степени на всички k върха са еднакви, се нарича хомогенен граф със степен k .

Определение 7.Допълнението към дадена графа е графа, състояща се от всички ребра и техните краища, които трябва да бъдат добавени към оригиналната графа, за да се получи пълна графа.

Определение 8.Граф, който може да бъде представен в равнина по такъв начин, че ръбовете му да се пресичат само във върховете, се нарича планарен.

Определение 9.Многоъгълник на планарен граф, който не съдържа никакви върхове или ръбове на графика вътре, се нарича негово лице.

Концепциите за плоска графика и лица на графика се използват при решаване на задачи за "правилното" оцветяване различни карти.

Определение 10.Пътят от A до X е последователност от ръбове, водещи от A до X, така че всеки два съседни ръба имат общ връх и нито един ръб не се появява повече от веднъж.

Определение 11.Цикълът е път, при който началната и крайната точка са еднакви.

Определение 12.Прост цикъл е цикъл, който не преминава през нито един от върховете на графа повече от веднъж.

Определение 13.дълъг път , положен на примка , е броят на ръбовете на този път.

Определение 14.Два върха A и B в графа се наричат ​​свързани (несвързани), ако в него съществува (не съществува) път, водещ от A до B.

Определение 15.Графът се нарича свързан, ако всеки два негови върха са свързани; ако графът съдържа поне една двойка несвързани върхове, тогава графът се нарича несвързан.

Определение 16.Дървото е свързана графа, която не съдържа цикли.

Триизмерен модел на графично дърво е например истинско дърво със сложно разклонена корона; реката и нейните притоци също образуват дърво, но вече плоско - на повърхността на земята.

Определение 17.Несвързан граф, състоящ се само от дървета, се нарича гора.

Определение 18.Дърво, всичките n върха на което са номерирани от 1 до n, се нарича дърво с преномерирани върхове.

И така, ние разгледахме основните определения на теорията на графите, без които би било невъзможно да се доказват теореми и следователно да се решават проблеми.

Проблеми, решени с помощта на графики

Известни предизвикателства

Проблемът с пътуващия търговец

Проблемът с пътуващия търговец е един от най-известните проблеми в теорията на комбинаториката. Поставена е през 1934 г. и най-добрите математици са си счупили зъбите за нея.

Изложението на проблема е следното.
Пътуващият търговец (пътуващият търговец) трябва да напусне първия град, да посети градове 2,1,3..n веднъж в неизвестен ред и да се върне в първия град. Разстоянията между градовете са известни. В какъв ред трябва да се обикалят градовете, така че затвореният път (обиколка) на пътуващия търговец да е най-кратък?

Метод за решаване на проблема с пътуващия търговец

Алчен алгоритъм „отидете до най-близкия (в който още не сте влезли) град.“
Този алгоритъм се нарича „алчен“, защото в последните стъпки трябва да платите скъпо за алчността.
Помислете например за мрежата на фигура [приложение фиг.3]представляваща тесен ромб. Нека продавачът започне от град 1. „Отидете до най-близкия град” ще го отведе до град 2, след това 3, след това 4; на последната стъпка ще трябва да платите за алчност, връщайки се по дългия диагонал на ромба. Резултатът е не най-кратката, а най-дългата обиколка.

Проблемът с мостовете на Кьонигсберг.

Задачата е формулирана по следния начин.
Град Кьонигсберг е разположен на брега на река Прегел и два острова. Различните части на града бяха свързани със седем моста. В неделя гражданите се разхождаха из града. Въпрос: възможно ли е да се разхождате по такъв начин, че след като излезете от къщата, да се върнете, минавайки точно веднъж през всеки мост.
Мостовете над река Прегел са разположени както на снимката[Приложение Фиг.1].

Помислете за графика, съответстваща на мостовата схема [приложение фиг.2].

За да отговорим на въпроса на задачата, достатъчно е да разберем дали графиката е Ойлер. (Поне един връх трябва да има четен брой мостове). Невъзможно е, разхождайки се из града, да минеш веднъж през всички мостове и да се върнеш.

Няколко интересни предизвикателства

1. "Маршрути".

Задача 1

Както си спомняте, ловецът мъртви душиЧичиков посещава по веднъж известни земевладелци. Той ги посети в следния ред: Манилов, Коробочка, Ноздрев, Собакевич, Плюшкин, Тентетников, генерал Бетришчев, Петух, Констанжолго, полковник Кошкарев. Намерена е схема, върху която е скицирал Чичиков взаимно споразумениеимоти и селски пътищасвързването им. Определете кое имение на кого принадлежи, ако Чичиков не е минавал по нито един от пътищата повече от веднъж [приложение фиг.4].

Решение:

Според пътната карта се вижда, че Чичиков започва пътуването си с имението E и завършва с имението O. Забелязваме, че само два пътя водят до имението B и C, така че Чичиков трябваше да кара по тези пътища. Нека ги отбележим с удебелени линии. Определят се участъците на трасето, преминаващи през А: АС и АВ. Чичиков не е пътувал по пътищата АЕ, АК и АМ. Нека ги зачеркнем. Да отбележим с дебела линия ED ; задраскайте DK. Задраскайте MO и MN; маркирайте с удебелена линия MF ; задраскайте FO ; отбелязваме FH , NK и KO с дебела линия. Нека намерим единствения възможен маршрут при даденото условие. И получаваме: имението E - принадлежи на Манилов, D - Коробочка, C - Ноздрев, A - Собакевич, V - Плюшкин, M - Тентетников, F - Бетришчев, N - Петух, K - Констанжолго, O - Кошкарев [приложение фиг.5].

Задача 2

Фигурата показва карта на района [приложение фиг.6].

Можете да се движите само по посока на стрелките. Всяка точка може да бъде посетена не повече от веднъж. По колко начина можете да стигнете от точка 1 до точка 9? Кой маршрут е най-кратък и кой най-дълъг.

Решение:

Последователно "разслоете" схемата в дърво, като започнете от връх 1 [приложение фиг.7]. Да вземем дърво. Номер възможни начинипопадения от 1 до 9 е равен на броя на "висящите" върхове на дървото (има 14 от тях). Очевидно най-краткият път е 1-5-9; най-дългата е 1-2-3-6-5-7-8-9.

2 "Групи, запознанства"

Задача 1

Участниците в музикалния фестивал, след като се срещнаха, размениха пликове с адреси. Докажи това:

а) четен брой пликове са изпратени общо;

б) броят на участниците, разменили пликове нечетен брой пъти, е четен.

Решение: Нека участниците във фестивала са A 1 , A 2 , A 3 . . . , И n са върховете на графиката, а ръбовете свързват двойки върхове, представляващи момчета, които са си разменили пликове [Приложение Фиг.8]

Решение:

а) степента на всеки връх A i показва броя на пликовете, които участникът A i е дал на своите приятели. Общ бройпрехвърлените обвивки N е равно на сумата от степените на всички върхове на графа N = стъпка. Стъпка 1+. A 2 + + . . . + стъпка. И n -1 + стъпка. И n, N =2p, където p е броят на ръбовете на графиката, т.е. N е четно. Затова бяха изпратени четен брой пликове;

б) в равенството N = стъпка. Стъпка 1+. A 2 + + . . . + стъпка. И n -1 + стъпка. И n сборът на нечетните членове трябва да е четен, а това може да бъде само ако броят на нечетните членове е четен. А това означава, че броят на участниците, разменили пликове нечетен брой пъти, е четен.

Задача 2

Веднъж Андрей, Борис, Володя, Даша и Галя се съгласиха да отидат на кино вечерта. Решиха да се договорят за избора на кино и сеанса по телефона. Освен това беше решено, че ако не е възможно да се обадите на някого, пътуването до киното ще бъде отменено. Вечерта не всички се събраха на кино и затова посещението на киното пропадна. На другия ден започнаха да разкриват кой на кого се е обадил. Оказа се, че Андрей се обади на Борис и Володя, Володя на Борис и Даша, Борис на Андрей и Даша, Даша на Андрей и Володя, а Галя на Андрей, Володя и Борис. Кой не успя да се обади и затова не дойде на срещата?

Решение:

Нека начертаем пет точки и ги обозначим с буквите A, B, C, D, E. Това са първите букви от имената. Нека свържем тези точки, които съответстват на имената на момчетата, които са се обадили.

[приложение фиг.9]

От снимката се вижда, че всеки от момчетата - Андрей, Борис и Володя - е звънял на всички останали. Ето защо тези момчета дойдоха на кино. Но Галя и Даша не успяха да се обадят (точките D и D не са свързани с сегмент) и следователно, в съответствие със споразумението, те не дойдоха на кино.

Използването на графики в различни области от живота на хората

Освен посочените примери, графите намират широко приложение в строителството, електротехниката, управлението, логистиката, географията, машиностроенето, социологията, програмирането, автоматизацията. технологични процесии производство, психология, реклама. И така, от всичко по-горе неопровержимо следва практическата стойност на теорията на графите, чието доказване беше целта това учение.

Във всяка област на науката и технологиите се срещате с графики. Графиките са прекрасни математически обекти, с които можете да решавате математически, икономически и логически задачи, различни пъзели и да опростявате условията на задачи по физика, химия, електроника, автоматизация. Удобно е да се формулират много математически факти на езика на графиките. Теорията на графите е част от много науки. Теорията на графите е една от най-красивите и визуални математически теории. AT последно времеТеорията на графите намира все повече приложения в приложни въпроси. Появи се дори компютърната химия - сравнително млада област на химията, основана на приложението на теорията на графите.

Молекулярни графики, използвани в стереохимията и структурната топология, химията на клъстерите, полимерите и др., са неориентирани графики, които показват структурата на молекулите [приложение фиг.10]. Върховете и ръбовете на тези графики съответстват на съответните атоми и химически връзкимежду тях.

Молекулярни графики и дървета: [приложение фиг.10] a, b - мултиграфи респ. етилен и формалдехид; в мол. изомери на пентан (дървета 4, 5 са ​​изоморфни на дърво 2).

В стереохимията на организмите най-много често използват молекулярни дървета - основните дървета на молекулярните графи, които съдържат само всички върхове, съответстващи на C атоми. дървета и установяването на техния изоморфизъм ви позволяват да определите кея. структури и намерете общ бройизомери на алкани, алкени и алкини

Протеинови мрежи

Протеинови мрежи - групи от физически взаимодействащи протеини, които функционират в клетка съвместно и по координиран начин, контролирайки взаимосвързаните процеси, протичащи в тялото [приложение фиг. единадесет].

Йерархична системна графиканаречено дърво. Отличителна чертана едно дърво е, че има само един път между всеки два негови върха. Дървото не съдържа цикли и цикли.

Обикновено едно дърво, представляващо йерархична система, има един главен връх, който се нарича корен на дървото. Всеки връх на дървото (с изключение на корена) има само един предшественик - посоченият от него обект принадлежи към един клас от най-високо ниво. Всеки връх на дървото може да генерира няколко потомци - върхове, съответстващи на класове от по-ниско ниво.

За всяка двойка върхове на дърво има уникален път, който ги свързва. Това свойство се използва при намиране на всички предци, например по мъжка линия, на всяко лице, чието родословно дърво е представено като родословно дърво, което също е „дърво“ в смисъла на теорията на графите.

Пример за моето родословно дърво [приложение фиг.12].

Още един пример. Фигурата показва библейското родословно дърво [приложение фиг.13].

Разрешаване на проблем

1. Транспортна задача. Нека има база със суровини в град Краснодар, която трябва да бъде засадена в градовете Кримск, Темрюк, Славянск на Кубан и Тимашевск наведнъж, като същевременно харчите възможно най-малко време и гориво и се връщате обратно до Краснодар.

Решение:

Първо, нека направим графика на всички възможни начинипътуване [приложение фиг.14], като се вземат предвид реалните пътища между тези населени места и разстоянието между тях. За да разрешим този проблем, трябва да създадем друга графика, дърво [приложение фиг.15].

За удобство на решението обозначаваме градовете с номера: Краснодар - 1, Кримск - 2, Темрюк - 3, Славянск - 4, Тимашевск - 5.

Това доведе до 24 решения, но се нуждаем само от най-кратките пътища. От всички решения само две са удовлетворени, това са 350 км.

По същия начин е възможно и мисля, че е необходимо да се изчисли реален транспорт от един местностна другите.

Логическа задача за кръвопреливане.В една кофа има 8 литра вода и има две тенджери с вместимост 5 и 3 литра. необходимо е да излеете 4 литра вода в петлитрова тенджера и да оставите 4 литра в кофа, т.е. изсипете вода по равно в кофа и голяма тенджера.

Решение:

Ситуацията във всеки един момент може да се опише с три числа [приложение фиг.16].

В резултат на това получаваме две решения: едното в 7 хода, другото в 8 хода.

Заключение

Така че, за да научите как да решавате проблеми, трябва да разберете какви са те, как са подредени, от кои съставни частите се състоят от това какви инструменти се използват за решаване на проблеми.

Решавайки практически задачи с помощта на теорията на графите, стана ясно, че на всяка стъпка, на всеки етап от тяхното решаване е необходимо да се прилага творчество.

От самото начало, на първия етап, се крие във факта, че трябва да можете да анализирате и кодирате състоянието на проблема. Вторият етап е схематичен запис, който се състои от геометрично представянеграфики, като на този етап елементът на креативността е много важен, защото далеч не е лесно да се намерят съответствия между елементите на условието и съответните елементи на графиката.

Решаване транспортна задачаили задачата за съставяне на родословно дърво, заключих, че графичният метод със сигурност е интересен, красив и визуален.

Бях убеден, че графиките се използват широко в икономиката, управлението и технологиите. Теорията на графите се използва и в програмирането.Това не беше обсъдено в тази статия, но мисля, че това е само въпрос на време.

В този научен труд, математически графики, области на тяхното приложение, няколко задачи бяха решени с помощта на графики. Познаването на основите на теорията на графите е необходимо в различни области, свързани с управлението на производството, бизнеса (например схема на строителна мрежа, графици за доставка на поща). Освен това, докато работех върху научна работа, усвоих работата на компютър в текстов редактор на WORD. И така, задачи научна работазавършен.

И така, от всичко казано по-горе неопровержимо следва практическата стойност на теорията на графите, чието доказване беше целта на тази работа.

Литература

Бердж К.Теория на графите и нейните приложения. -М .: IIL, 1962.

Кемени Дж., Снел Дж., Томпсън Дж.Въведение в крайната математика. -М .: IIL, 1963.

Оре О.Графики и тяхното приложение. -М .: Мир, 1965.

Хари Ф.Теория на графите. -М .: Мир, 1973.

Зиков А.А.Теория на крайните графи. -Новосибирск: Наука, 1969.

Березина Л.Ю.Графики и тяхното приложение. -М .: Образование, 1979. -144 с.

„Образователен журнал на Сорос“ № 11 1996 г. (статия „Плоски графики“);

Гарднър М. "Математическо свободно време", М. "Мир", 1972 г. (глава 35);

Олечник С. Н., Нестеренко Ю. В., Потапов М. К. „Стар занимателни задачи", М. "Наука", 1988 (част 2, раздел 8; приложение 4);

Приложение

Приложение

П

Ориз. 6

Ориз. 7

Ориз. осем

Приложение

Приложение

Приложение

Приложение

П

Ориз. четиринадесет

Приложение

Приложение

Книгата на К. Берж е първата по теория на графите на руски език. Междувременно в последните годиниинтересът към теорията рязко нарасна както от страна на математиците, така и от представители на най-много различни дисциплини. Това се обяснява с факта, че методите на теорията на графите успешно решават много проблеми на теорията електрически вериги, теория на транспортната верига, теория на информацията, кибернетика и др.
В книгата на Берге теорията на графите е представена последователно, започвайки от самите основи. Предполага се, че читателят има много скромни математически познания, въпреки че има известна математическа култура. В текста са включени множество, често забавни примери. Книгата може да се използва за първоначално изучаване на теория на графите. Математиците-професионалисти също ще намерят много интересни неща в него.

Алгоритъм за директно идентифициране на цикъла на Ойлер.
[Фльори]. Да разгледаме свързан мултиграф G, чиито върхове имат дори степен, и ще се опитаме да го начертаем с един щрих, без да прибягваме до корекции на вече начертаната част от траекторията в процеса на изграждане. Достатъчно е да се придържате към следното правило:
1 Оставяме произволен връх a; Зачеркваме всеки преминат ръб.
2 Никога не минаваме по такова ребро u, което в разглеждания момент е провлак (т.е. при отстраняването на който графът, образуван от непресичани ръбове, се разделя на две свързани компоненти, имащи поне по едно ребро всяка),

Спазвайки това правило, ние винаги ще бъдем в благоприятна позиция, тъй като когато сме при x = a, графиката (от непресечени ръбове) има два върха с нечетна степен: x и a; ако изхвърлим изолираните върхове, тогава оставаме със свързана графа, която по силата на теорема 1 има път на Ойлер, започващ от x.

Съдържание
Въведение
Глава 1. Основни дефиниции
Множества и многозначни преобразувания
Графика. Пътища и контури
Вериги и примки
Глава 2
Квазиред, определен от графика
Индуктивна графика и бази
Глава 3
Grundy за безкрайната графика
Общи съображения за безкрайни графи
Поредна функция
Функции на Гранди
Операции върху графики
Глава 4
Цикломатично число
Хроматично число
Вътрешен номер за стабилност
Номер на външна стабилност
Глава 5
Теореми за съществуване и уникалност
Приложение към функциите на Grandi
Глава 6
Игра Nim
Обща дефиниция на играта (с пълни подробности)
Стратегии
Глава 7
Процеси по етапи Някои обобщения
Глава 8. Транспортни мрежи
Проблемът с най-големия поток Проблемът с най-малкия поток
Проблемът на потока, съвместим с множество стойности
Безкрайни транспортни мрежи
Глава 9
Степен на изход и вход
Глава 10
Проблемът с най-голямото съвпадение
Дефицит на проста графика
унгарски алгоритъм
Обобщение към безкрайния случай
Приложение към теорията на матриците
Глава 11. Фактори
Хамилтонов път и Хамилтонов контур
Намиране на фактор
Намиране на частична графика с дадени полустепени
Глава 12
центрове
Радиус
Глава 13
Общи свойства на силно свързаните графи без цикли
Диаметър
Глава 14
Прилагане на конвенционални матрични операции
Задачи за броене
Проблем с лидера
Прилагане на булеви операции
Глава 15
Напълно унимодуларни матрици
Напълно унимодулни системи
Цикломатични матрици
Глава 16
дървета
Аналитично изследване
големи дървета
Глава 17
Ойлерови цикли Контури на Ойлер
Глава 18
Теория на променливите вериги
Намиране на частичен граф с дадени степени на върховете
Перфектно съвпадение
Приложение към числото на вътрешната стабилност
Глава 19
Хамилтонови цикли и фактороиди
Необходими и достатъчно условиесъществуването на фактороид
Глава 20
артикулационни точки
Графики без стави
h-свързани графики
Глава 21
Основни свойства
Обобщение
Допълнения
I. Изкл обща теория, игри
II. Относно транспортните задачи
III. За използването, концепциите за потенциал в транспортните мрежи
IV. Нерешени проблеми и недоказани предположения
V. За някои основни принципи на броенето (J. Riga)
VI. Допълнения към руския превод (А.А. Зиков и Г.И. Кожухин)
Литература
Теория на графите и книгата на К. Берж (послеслов към руския превод)
Индекс на символа
именен индекс
Предметен индекс.

Безплатно сваляне електронна книгав удобен формат, гледайте и четете:
Изтеглете книгата Теория на графите и нейните приложения, Berge K. - fileskachat.com, бързо и безплатно изтегляне.

ВЛАДИМИРСКИ ДЪРЖАВЕН ПЕДАГОГИЧЕСКИ УНИВЕРСИТЕТ

ЕСЕ

"ТЕОРИЯ НА ГРАФИТЕ"

Изпълнено:

Зудина Т.В.

Владимир 2001г

1. Въведение

2. Историята на възникването на теорията на графите

3. Основни дефиниции на теорията на графите

4. Основни теореми на теорията на графите

5. Задачи за приложение на теорията на графите

6. Приложение на теорията на графите в училищен курсматематика

7. Приложение на теорията на графите в различни области на науката и технологиите

8. Последни постижениятеория на графите

§едно. ИСТОРИЯ НА ТЕОРИЯТА НА ГРАФИТЕ.

Математикът Леонхард Ойлер (1707-1783) се смята за основател на теорията на графите. Историята на възникването на тази теория може да бъде проследена чрез кореспонденцията на великия учен. Ето превод на латинския текст, който е взет от писмото на Ойлер до италианския математик и инженер Маринони, изпратено от Санкт Петербург на 13 март 1736 г. [вж. стр. 41-42]:

"Веднъж ми предложиха проблема с остров, разположен в град Кьонигсберг и заобиколен от река, през която са прехвърлени седем моста. Въпросът е дали някой може непрекъснато да ги заобикаля, минавайки само веднъж през всеки мост. досега той не е успя да направи това, но никой не е доказал, че е невъзможно. Този въпрос, макар и банален, ми се стори, обаче, достоен за внимание, защото нито геометрията, нито алгебрата, нито комбинаторното изкуство са достатъчни за неговото решение ... След много размишления намерих лесно правило, базирано на напълно убедително доказателство, с помощта на което във всички задачи от този вид може веднага да се определи дали такава верига може да се направи чрез произволен брой и произволно разположени мостове или не. така че да могат да бъдат представени на следващата фигура[Фиг. 1] , на която А означава остров и б , ° С и D са части от континента, разделени една от друга с речни ръкави. Седемте моста са обозначени с букви а , b , ° С , д , д , f , ж ".

(ФИГУРА 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.Нарича се граф, в който всяка двойка върхове е свързана с ребро пълен .

Обозначаване: U " – графика, състояща се от нвърхове и ръбове, свързващи всички възможни двойки от тези върхове. Такава графика може да бъде представена като н- квадрат, в който са начертани всички диагонали (фиг. 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 ребрата ACи BDсе пресичат в точка, която не е връх на графиката. Но има случаи, когато даден граф трябва да бъде представен на равнина по такъв начин, че неговите ръбове да се пресичат само във върховете (този въпрос ще бъде разгледан подробно по-късно, в параграф 5).

Определение 2.08.Граф, който може да бъде представен в равнина по такъв начин, че ръбовете му да се пресичат само във върховете, се нарича апартамент .

Например Фигура 2.8 показва планарна графика, която е изоморфна (равна на) графиката на Фигура 2.5. Имайте предвид обаче, че не всяка графика е равнинна, въпреки че обратното е вярно, т.е. всяка равнинна графика може да бъде представена по обичайния начин.

(ФИГУРА 2.8)

Определение 2.09.Многоъгълник на плоска графа, който не съдържа никакви върхове или ръбове на графиката вътре, се нарича ръб, край .

Теорията на графите е клон на математиката, използван в компютърните науки и програмирането, икономиката, логистиката и химията.

Какво е графика

Често графичните диаграми се използват за описание на структурата на системите. Елементите в тях са изобразени с кръгове, точки, квадрати и др., а връзките между елементите са показани с линии или стрелки. В този случай не е важно нито как са изобразени елементите, нито дължината или формата на линиите - има значение само кои елементи са свързани. И така, графиката е двойка от формата (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) е цикъл.

Теорията на графите в програмирането се използва за изграждане на графични диаграми на алгоритми.