Елементи на теорията на графите и математическото програмиране. Пътища и цикли

Учебно издание

Ююкин Николай Алексеевич

ЛР бр. Подписано за печат

Уч. Изд. л.., .

Воронежски държавен технически университет

394026 Воронеж, пр. Московски. четиринадесет

КАТАЛОГ НА МАГНИТНИ ДИСКОВЕ

Председател висша математикаи физическо и математическо моделиране

НА. Ююкин

ДИСКРЕТНА МАТЕМАТИКА Част 1. Елементи на теорията на графите

Урок

НА. Ююкин

ДИСКРЕТНА МАТЕМАТИКА Част 1. Елементи на теорията на графите

Урок

Воронеж 2004г

ВЪВЕДЕНИЕ

Това ръководство може да се използва в курса "Дискретна математика" от студенти на VSTU, обучаващи се в следните специалности:

090102 - Компютърна сигурност;

090105 - Комплексна информационна сигурност на автоматизирани системи;

090106 - Информационна сигурносттелекомуникационни системи.

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

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

AT учебно ръководствоочертава основите, основните методи и алгоритми на теорията на графите. Ето n-графи и диграфи; изоморфизми; дървета; Ойлерови графики; равнинни графики; покрития и самостоятелни комплекти; силна свързаност

в диграфи; Марков верижен графов анализ; алгоритми за намиране на най-кратки пътища в графи; задача за намиране на Хамилтонов цикъл

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

Целта на дисциплината е да формира студентите теоретични знания, практически умения в областта на моделирането на процеси и явления в природните науки и технологиите

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

За постигането на тази цел служат следните задачи:

да изучава възможно най-широк кръг от концепции на теорията на графите;

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

владеят методи за оптимизация;

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

Дисциплината "Дискретна математика" е една от приложните математически дисциплини. Базира се на знанията, придобити от студентите при изучаването на дисциплините "Алгебра" и " математическа логикаи теорията на алгоритмите”. В уч. общо професионалени специални дисциплини.

1. ОСНОВНИ ПОНЯТИЯ НА ТЕОРИЯТА НА ГРАФИТЕ.

1.1. Проблеми на теорията на графите.

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

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

Първа задача. Проблемът за мостовете на Кьонигсберг е поставен и решен от Ойлер през 1786 г. Градът е бил разположен на бреговете и двата острова на река Преголя. Островите са били свързани между себе си и бреговете чрез седем моста, както е показано на фигурата.

Възникна въпросът: възможно ли е, след като излезете от къщата, да се върнете обратно, преминавайки през всеки мост точно веднъж?

Втора задача. Проблемът с три къщи и три кладенеца. Има три къщи и три кладенеца.

Изисква се да се начертае пътека от всяка къща до всеки кладенец, така че пътеките да не се пресичат. Задачата беше

решен от Понтрягин и независимо от Куратовски в

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

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

1.2. Основни определения.

Граф G= (V,E ) е набор от две множества - непразно множество от върхове V и множество от неподредени и подредени двойки от върхове E . По-нататък ще бъдат разгледани крайни графи, т.е. графи с краен набор от върхове и крайно семейство двойки. Неподредена двойка върхове се нарича ребро, а подредена двойка се нарича дъга.

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

ственни геометрични свойстваребра (дължина, кривина), както и взаимно споразумениевърхове на равнината.

Върховете, които не принадлежат на нито едно ребро (дъга), се наричат изолирани. Върховете, свързани с ребро или дъга, се наричат съседни. Ребро (дъга) и всеки от двата му върха се наричат инцидент.

Казват, че ръбът (u, v) свързва върховете u и v, а дъгата (u, v) започва от върха u и завършва във върха v, докато u се нарича начало, а v е край на тази дъга.

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

Граф без цикли и множество ребра се нарича прост. Един прост граф се нарича пълен, ако за всяка двойка негови върхове има ребро (дъга), което ги свързва. Пълен граф с n върха се означава с K n . Например, това са графики

Граф, състоящ се от един изолиран връх (K 1 ), се нарича тривиален.

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

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

1.3. Степени на върха на графиката.

Степента (валентността) (означение d (v) или deg (v) на връх v на проста графа G е броят на ребра или дъги, инцидентни на даден връх v. Когато се изчислява валентността на върховете на псевдографа, всеки цикъл трябва да се брои два пъти.

Ако степените на всички върхове на n-графа са равни на k , тогава графът се нарича редовен (хомогенен)градуси k. Ако степента на върха е 0, тогава той е изолиран. Ако степента на върха е равна на 1, тогава върхът се нарича краен (висящ, задънен).

За орграф се извиква броят на дъгите, излизащи от връх v

vaetsya половин степен на резултат				(v ), и входящи - полу-

нов залез d			(v ), докато връзката d (v )=

	(v)+	(v).

Теорема на Ойлер: Сумата от степените на върховете на граф е

два пъти броя на ръбовете, т.е.

d(vi)



			(v)

Където n е броят на върховете; m е броят

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

1.4. Графичен изоморфизъм.

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

белези (цифри). Разчитайте напълно дефиниран в строгия смисъл, ако номерирането на неговите върхове и ръбове е фиксирано. В този случай графите G 1 и G 2 се наричат равни (нотация G 1 =G 2 ), ако техните набори от върхове и ребра съвпадат. Две графики или псевдографи G 1 = (V 1 ,E 1 ) и G 2 = (V 2 ,E 2 ) се наричат-

	изоморфен (нотация G	Ако има

	съпоставяния едно към едно: 1)	: V 1V 2
: E 1 E 2 така, че за всеки два върха u , v в графиката
	релацията ((u ,v )) ((u ), (v )) е валидна.

	Две прости графики (без цикли и множество ребра) G 1		и G2

се оказват изоморфни, ако има взаимно идентични

картографиране на стойността

: V 1V 2

Така че

(u ,v ) ((u ), (v )).

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

Рефлексивност -

G1,

освен това биекцията

е идентичната функция.

Симетрия.

с биекция

преходност.

G1G2

биекция

1,а

с биекция

след това G G

с биекция

2 (1) .

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

ЕСЕ

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

Изпълнено:

Зудина Т.В.

Владимир 2001г

1. Въведение

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

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

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

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

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

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

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

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

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

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

(ФИГУРА 1.1)

По отношение на открития от него метод за решаване на проблеми от този вид, Ойлер пише [вж. стр. 102-104]:

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

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

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

Обосновката за горното правило може да се намери в писмо от Л. Ойлер до неговия приятел Елер от 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.Многоъгълник на плоска графа, който не съдържа никакви върхове или ръбове на графиката вътре, се нарича ръб, край .

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

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

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

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

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

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

Със сигурност сте чели учебници и сте виждали такава нотация 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 са части от континента, разделени една от друга с речни ръкави

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

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

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

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

Определение 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

Ориз. осем

Приложение

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

Приложение

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

Примери за използване на теория на графите.

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

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

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

Д. Кьониг предлага да наричаме такива схеми "графики" и систематично да изучаваме техните свойства.

В перфектно различни дисциплинитрябва да се използват подобни теореми; по този начин, концепцията за "инцидентна матрица", въведена от Kirchhoff за изследване на електрически вериги, е привлечена от A. Poincaré към топологията, когато създава своя "analysis situs"; понятието "съединителна точка", познато отдавна в социологията, впоследствие се появява в електрониката; Невъзможно е да се изброят всички подобни примери. За да можем да приложим теорията на графите в такива разнообразни области, тя трябва да бъде в най-високата степенабстрактно и формално.

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

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

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

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

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

Теорията на графите е била „откривана“ независимо много пъти: тя с основателна причинаможе да се счита за клон на приложната математика. Наистина, най-ранното известно споменаване на тази теория се намира в работата на Ойлер и въпреки че проблемът, с който се занимава, може да се разглежда като обикновен пъзел, той все пак възниква от практиката.

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

Друг подход към графиките, свързан с разглеждането на пъзели, е предложен от Хамилтън. След това се появи известната четирицветна хипотеза, която все още е широко известна.

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

Проблемът с Кьонигсбергския мост

Бащата на теорията на графите (както и на топологията) е Ойлер (1707-1782), който през 1736 г. решава проблем, който е широко известен по това време, наречен проблем на Кьонигсбергския мост.

В град Кьонигсберг имаше два острова, свързани със седем моста с бреговете на река Прегол и един с друг, както е показано на фигурата.

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

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

Приносът на Ойлер за решаването на този проблем е, че той доказа невъзможността за такъв маршрут.

Фигура 1. Парк в град Кьонигсберг, 1736 г

Фигура 2. Графика за проблема с мостовете в Кьонигсберг

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

Оказа се "брой". Тази графика е показана на фигура 2., където точките са маркирани със същите букви като четирите части на земята.

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

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

Графът, показан на фигурата, е свързан, но не всеки от неговите върхове е инцидентен (принадлежи) на четен брой ребра.

Електрически вериги

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

Физик по образование, той подходи към решаването на проблеми като математик. Абстрахирайки се от електрически вериги и вериги, които съдържат съпротивления, кондензатори, индуктивности и т.н., той разглежда съответните комбинаторни структури, съдържащи само върхове и връзки (ръбове или дъги), а за връзките не е необходимо да се посочва какви видове електрически елементи съответстват към..

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

Фигура 3. Мрежа N, съответстващата й графика G.

Вместо това той предложи просто но ефективна методология(което по-късно се превърна в стандартна процедура), според която е достатъчно да се ограничим само до независими прости цикли на графа, дефинирани от някое от неговите "обхващащи дървета". Фигура 3 показва пример за електрическа верига N, съответстваща графика G.

Химични изомери

Справяне с чисто практически задачи органична химия, Кейли през 1857 г. открива важен клас графи, наречени дървета.

Той се опита да изброи изомерите на наситените (наситени) въглеводороди ОТн з 2 n + 2 с даден брой въглеродни атоми n; фигура 4.

Фигура 4. Изобутан

В социалната психология.

През 1936 г. психологът Кърт Лоу и n предположи, че "жизненото пространство" на индивида може да бъде представено с помощта на равнинна карта 1).

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

Фигура 5. Карта и съответната й графика.

Подчертаваме, че К. Лев и n всъщност се занимава с графики, както може да се види от Фигура 5.

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

Предложението на Левин се отнася само за равнинни карти, тъй като той винаги рисува чертежите си върху равнина. Впоследствие идеята на К. Левин е развита в социометричните процедури.

В теорията на организацията

Графиките могат да бъдат представени не само в строга класическа форма. И така, жизненият цикъл на компанията I. Adizes е представен в следната форма.

Фигура 6 Кръговат на животакомпании

функционален организационна структура Тя е изградена на принципа на разпределение на функциите в организацията и създаването на подструктури от край до край за управление на функциите.

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

Ориз. Функционална организационна структура

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

Тази теория се превърна в "теория на графите".

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

Нека започнем с дефиниция, теорията на графите няма уникална дефиниция, три дефиниции са представени по-долу, но има и други.

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

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

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