Елементи на теорията на графите
3. Подграфи. Компоненти за свързване ……………………………………………………………….. 11
6. Операции върху графики. Критерий за планарност на графиките…………………….……….. 21
7. Задачи за самостоятелно решаване……………………………………………………………. 23
Предложените насоки несъмнено ще бъдат полезни за студентите от специалностите "приложна математика", "класическа математика" и "математическа икономика", които изучават дискретна математика в Института по математика и математика на ONU. Аз, аз, Мечников.
Елементи на теорията на графите.
1. Графики и техните елементи.
Теорията на графите води началото си от известния математик от Българската академия на науките Леонард Ойлер, който решава проблема с Кьонигсбергския мост през 1736 г. Той показа, че е невъзможно да се заобиколят седемте градски моста на град Кьонигсберг (разположен на два острова и по бреговете на река Прегал) и да се върне в началната точка, като се премине по всеки от седемте моста точно по веднъж. Теорията на графите получава следващия си тласък почти 100 години по-късно с развитието на изследванията в електрическите мрежи, кристалографията, органичната химия и други науки.
Графиките служат като удобно средство за описване на връзки между обекти. Работим с графики през цялото време. Например мрежа от магистрали, въздушни комуникации, нефтопроводи или газопроводи са примери за графики.
За да въведем формална дефиниция на графика, имаме нужда от следното
Определение 1.1. Нека ни е дадено някакво непразно множество M от елементи с произволен характер. Тогава набор от n места (кортеж) над множеството M е произволна последователност от n елемента от това множество (може да се разглеждат и безкрайни множества). В това, което следва, ние ще дефинираме множества от n места върху M с помощта на кръгли или ъглови скоби, като изброим елементите на множествата, т.е. във формата ( a 1 , a 2 ,…, a n ) или 1 , а 2,…, a n и обозначаваме тяхното множество с M n Така:
Определение 1.2. От формална гледна точка обикновеният граф G е кортеж (набор) от два обекта G= V,U , където V е произволно непразно крайно множество, чиито елементи се наричат върхове на графа, а U е произволно подмножество на множеството от подмножества от два елемента V (2) на множеството V, чиито елементи се наричат ребра (или дъги) на графиката.
От дефиницията на граф веднага следва, че всяко ребро (дъга) на графиката u = < v i ,v j >U се дефинира от някаква двойка върхове v i ,v j V. Също така е ясно, че един обикновен граф не може да има ребра от формата < v i ,v i >( контури ) и че не може да има отделни ръбове, обозначени с една и съща двойка върхове (множество или успоредни ръбове). Ако допуснем съществуването на множество ребра в граф, тогава такъв граф се нарича мултиграф. Ако допуснем съществуването както на множество ребра, така и на цикли в графа, тогава такъв граф се нарича псевдограф.
Графиките са начин за "визуализация" на връзките между определени обекти. Тези връзки могат да бъдат или „непосочни“ (като мрежа с две платна), или „посочни“ (като родословно дърво). Съответно има два вида графики в теорията на графите:
неориентирани и насочени графи. По-нататък ще наричаме графите неориентирани графи, а насочените графи - диграфи. Тъй като посоките на ръбовете не са установени за неориентирани графи, редът на изброяване на върховете, когато се описва конкретен ръб на графиката, е маловажен и следователно символиката на теорията на множествата се използва за обозначаване на ръбове -
ребро се означава като набор от два върха, т.е. < v i ,v j >. За диграфите посоките на ръбовете са от съществено значение, а следователно и ръбовете на диграфаще бъдат обозначени с множества (v i,v j) и наречени дъги. Граф, съдържащ както неориентирани, така и насочени ребра, се нарича смесен граф.
Има разлики в терминологията за графики и диграфи. Нека извършим (съгласно [3]) „паралелно“ въвеждане на основните понятия за графи и диграфи, което ни позволява визуално да ги сравним.