Увод
в теорията на графите
1. Теория
на графите
1.1.
Основни
понятия
Графът е нелинейна, динамична структура от данни,
изградена от възли (върхове) и връзки между тях наречени ребра (клони, дъги).
В този смисъл графът се дефинира като съвкупност от две множества – множеството на възлите V и множеството на ребрата Е: G(V,E) .
Е може да се представи като множество от двойки (x,y), където x и y принадлежат
на
V. x
и y
се наричат съседни възли.
Когато двойката е наредена, т.е. (x,y)≠ (y,x), то реброто се нарича ориентирано.
Когато двойката е ненаредена, т.е. (x,y)= (y,x), то реброто се нарича неориентирано.
Всяко неориентирано ребро може да се представи като съвкупност от две
ориентирани ребра с различни посоки.
Бримка – ребро, за което
началния и крайния възел съвпадат. 
Паралелни ребра- ребра, които
свързват едни и същи възли. 
Неориентиран
граф- граф, които съдържа само неориентирани ребра,
без бримки и без паралелни пътища.
Ориентиран граф- граф, които съдържа само ориентирани ребра.
Степен
на възел в неориентиран граф е количествена
характеристика, която определя броя на ребрата, свързани с дадения възел (броя
на съседните възли).
Степен
на входа на възел в ориентиран граф е количествена
характеристика, която определя броя на входящите във възела ребра.
Степен
на изхода на възел в ориентиран граф е количествена характеристика,
която определя броя на изходящите от възела ребра.
Изолиран възел – възел със
степен 0.
Висящ възел – възел със степен
1.
Път в граф – наредена
последователност от съседни възли.
Цикъл (контур)- път, за който
началния и крайния възел съвпадат.
Прост цикъл – цикъл, в който
няма повтарящи се възли.
|
|
Пътища П1: 5-4-2-1 П2: 1-2-3-4-5 П3: 1-2-4-3-2-1 П4: 1-2-4-3-1 П3 и П4 - цикли П4 - прост цикъл |
Хамилтонов цикъл – цикъл, който
включва всички възли на графа точно по веднъж.
Ойлеров цикъл – цикъл, който
включва всички ребра на графа точно по веднъж.
Не всички графи притежават хамилтонов и ойлеров цикъл. Поради това, графите които притежават хамилтонов цикъл се наричат хамилтонови графи, а тези които притежават ойлеров цикъл- ойлерови графи.
1.2.
Видове графи
Пълен граф – граф, за който има ребра между всеки два върха.
, където n е броя на възлите.
Празен
граф – граф на който всички възли са висящи (няма нито
един клон)
G(V,E) , E – празно множество.
Брой ребра = 0
Допълнителен
граф – Възлите на основния и допълнителния граф
съвпадат. Ако в основния граф има път между два възела, то в допълнителния няма
и обратно.
е допълнителен
за G(V,E) ако V1ºV и Е1 Ç Е = празно множество.
Регулярен
граф – всички възли са от еднаква степен. (Пълният
граф е регулярен със степен = n-1.)
Теглови граф – на възлите и/или
на клоните са присвоени тегла.
Равнинен граф – може да се
изобрази в равнината без да се пресичат ребра.
Двудялов
граф – всички възли са разделени на две подмножества –
и V1 и V2 и всеки възел има свързващи ребра само към възли от другото
подмножество.
Свързан граф – граф за който
между всички възли има път.
Несвързан граф – граф, за който съществуват възли без път между тях.
Всеки несвързан граф може да се представи като
съвкупност от краен брой свързани графи, наречени компоненти.
Компонента – максималния породен свързан граф, съдържащ даден възел.
1.3.
Представяне на графи
Графът може да бъде записан (представен) във
външната памет (външно представяне) и във вътрешната памет(вътрешно
представяне).
1.3.1. Външно представяне – 2 подхода:
· записва се номера на възела и след тире се изреждат неговите съседи;
Пример: 1-2 3 2-3 4 5 3-1 2 4 5 4-2 3 5 5-2 3 4
· на всеки ред от файла се записват съседите на възела, чиито номер съответства на номера на реда.
|
Пример: |
2 3 1 3 4 5 1 2 4 5 2 3 5 2 3 4 |
1.3.2. Вътрешно представяне
Вътрешното представяне може да се извърши по два основни начина: чрез матрица на съседство и чрез списъци на съседство.
1.3.2.1.Матрица на съседство
Създава се матрица по редовете и колоните на
която се поставят номерата на възлите. При битоничните матрици в местата на
връзка се записва 1, а при тегловните матрици (за тегловен граф)- теглото на
реброто.
|
|
1 |
2 |
3 |
4 |
|
|
1 |
0 |
1 |
1 |
0 |
0 |
|
2 |
1 |
0 |
1 |
1 |
1 |
|
3 |
1 |
1 |
0 |
1 |
1 |
|
4 |
0 |
1 |
1 |
0 |
1 |
|
5 |
0 |
1 |
1 |
1 |
0 |
Ако в графа няма бримки, по главния диагонал трябва да има само нули. Ако графът е неориентиран, матрицата е симетрична спрямо главния диагонал.
За представянето на графа са необходими n2 клетки в паметта – доста неикономично.
1.3.2.2.Списъци на съседство
При списъците на съседство са възможни 3 подхода: статично(два масива), полудинамично (масив+списъци) и динамично (списъчни структури).
· Статично представяне – използват се два масива: масив “съседи”, където последователно се изреждат номерата на съседите на всеки един възел в графа и масив ”начало”, където във всеки елемент се записва индекса, от който в масив “съседи” започва изреждането на съседите на възела, който има номер, равен на индекса на елемента в масив ”начало”.
· Полудинамично – в масива “начало” се записва адресът на записа на първия съсед. Всеки запис на съсед притежава по две полета: номер на възела и указател към следващия съсед. Указателя за следващ съсед на последния от списъка е нула.
· Динамично – за всеки възел се създава запис с две полета: номер на възела и указател към двойка указатели. Първият указател от двойката съдържа адреса на съсед, а втория- адреса на следващата двойка указатели.
2. Дърво
Дървото представлява свързан
нецикличен граф с някои допълнителни свойства.
Ориентирано дърво – свързан,
нецикличен насочен граф.
Неориентирано дърво – свързан,
нецикличен ненасочен граф.
Корен на дърво – възел със
степен на входовете 0. Възел, който няма входящи ребра, но има изходящи.
Листо на дърво – възел със
степен на изходите 0. Възел, който няма изходящи входящи ребра, но има входящи.
2.1.
Основни
понятия
За дъгата (x,y)
възелът х се нарича предшественик,
родител или баща,
а възелът у – приемник, наследник,
дете или син.
Поддърво – всички приемници на даден възел и свързващите ги дъги.
Разстояние между 2 възела, между които има път се нарича броят на дъгите по пътя между тях.
|
Разстоянието
между възлите 1 и 7 е 3. Разстоянието
между възлите 2 и 6 е 2. Разстоянието
между възлите 1 и 10 е 4. |
|
Дълбочина на възел – разстоянието между корена и възела.
Дълбочината
на възел 2 е 1.
Дълбочината
на възел 7 е 3.
Дълбочината на възел 10 е 4.
Височина
на възел – разстоянието между възела и
най-отдалеченото листо.
Височината
на възел 2 е 4.
Височината
на възел 2 е 3.
Височината
на възел 6 е 1.
Височината
на възел 7 е 0.
Височината на възел 10 е 0.
Височина на дърво - разстоянието между корена и най-отдалеченото листо.
Височината на дървото е 4.
Двоично
дърво – дървовидна структура от степен на изходите 2, т.е.
всеки възел има не повече от два наследника - ляв и десен.
Балансирано
дърво – дърво, за което и изпълнено условието:
разликата във височините на поддърветата на всеки негов възел е най-много 1.
|
|
|
|
НЕбалансирано дърво |
Балансирано дърво |
3. Обхождане
на граф
Дефиниция:
Обхождането на граф е процедура, която систематически по определен алгоритъм
обхожда всички върхове на графа.
3.1.
Обхождане на неориентиран граф в дълбочина
Обхождането започва от избран базисен възел. Продължава с първия съсед от списъка. Обхождането продължава в дълбочина като се прави опит с първия съсед на новопосетения възел. Ако той вече е бил посетен се прави опит с втория и т.н. И така докато се достигне до възел, на който всички съседи вече са били посетени. Пристъпва се към връщане назад да достигане на възел с поне един непосетен съсед, след което отново се прави обхождане в дълбочина. Обхождането продължава докато не се посетят всички възли от графа. Получава се скелетно дърво на графа.
Ребрата, които участват в скелетното дърво се наричат прави, а тези които не участват – обратни.
Всеки обратен клон заедно с пътя през скелетното дърво на графа между същите два възела се нарича фундаментален цикъл.
|
|
(6,3), (6,11) и (6, 13) са обратни клони. |
3.2.
Обхождане на неориентиран граф в ширина
Започва се от базовия възел. Неговото ниво е 0. Търсят се неговите съседи. Нивото на всичките му съседи се определя като 1. И така на всеки възел Х се търсят непосетените съседи и тяхното ниво се определя с 1 по-голямо от нивото на възела Х. (Започва се от възела с най-малък номер.)
|
|
Възел 6 е с ниво 0. Неговите съседи са с ниво 1:
Непосетените съседи на тези възли са от ниво 2:
Непосетените съседи на тези възли са от ниво 3:
|
|
