ПЪТИЩА И СВЪРЗВАНЕ В ГРАФИКИ
ОСНОВНИ КОНЦЕПЦИИ
Графиките са математически модел, който може да се използва за представяне и изследване на формално описание на системи и процеси, състоящи се от краен брой фрагменти или компоненти, свързани помежду си чрез определени зависимости.
В същото време естеството на зависимостите на системните компоненти може да бъде произволно за конкретни системи в различни области на дейност.
Нека дадем примери за системи, чието изучаване и практическо използване е свързано с представянето под формата на краен брой компоненти и връзки между тях.
1.Транспортни мрежи. Компонентите на такива системи са отделни населени места или сгради, а връзките са индикация за наличието на пътища, които ги свързват.
2. Молекули на химични съединения. Части от такива системи са отделни атоми, които изграждат молекули, а връзките са химични съединения между атомите.
3. Електронни схеми. Като компоненти те включват функционални възли или елементи, а връзките показват наличието на проводници, свързващи възлите един с друг.
4. Административният апарат на институцията. Тук отделните длъжностни лица са части, а връзките показват наличието на служебна подчиненост между служителите на институцията.
Естествената форма на визуално назначаване на системи, представени чрез графики, е те да бъдат изобразени на равнина или в триизмерно пространство, така че частите на системите да са затворени области на пространството, а връзките да са дъги. Освен това, ако връзката между частите на системата се характеризира с наличието на посока от една част към друга, тогава съответната дъга е снабдена с указание за съответната посока.
Освен това се изисква избраните области, представляващи части от графиката, да нямат общи точки и дъгиотразяващите връзки не се пресичат и не съдържат области вътре в точките, съответстващи на части от системата.
Образ на система, за който са изпълнени горните условия, се нарича геометрична реализация на тази система.
Пример. Възможна е следната система на подчинение според службата на служителите от управленския апарат на определена фирма (фиг.5.1.):
Главен главен референт
ръководител правен отдел
Фиг.. 5.1.
ДЕФИНИЦИЯ И МЕТОДИ ЗА НАСТРОЙКА НА ГРАФИКИ
ДЕФИНИЦИЯ
Граф е всяка двойкаG = (V,U ), в коятоV е краен набор, наречен набор от върхове на графиката, иU е краен набор от ръбове на графа.
Всяко ребро на графа е представено или от една двойка върхове (а,b ), или от две противоположни двойки (a,b ) и (b,a ). Ако ребро отU е представено само от една двойка (a,b ), тогава то се нарича насочено ребро, водещо отa къмb. В този случайa се нарича начало, аb се нарича край на такова ребро.
Ако реброu е представено от две двойки (a,b ) и (b,a ), тогаваu се нарича ненасочено ребро. Всяко ненасочено ребро между върховетеa иb води както отa къмb, така и обратно. В този случай върховетеa иb са както началото, така и краищата на това ребро. Казва се, че едно ребро води както отa къмb,, така и отb къмa.
Всеки два върха, които са свързани с ребро, се наричат съседни.
Ще разглеждаме само такива графи, за които всички ребра са различни и едновременното свързване на една и съща двойка върхове с насочено и ненасочено ребро не е разрешено илидвойка противоположно ориентирани ръбове. Графите, които позволяват възможността за множество ребра, свързващи двойки върхове, се наричат мултиграфи. Такива графики не се разглеждат в този урок.
(В последния случай съответната двойка ръбове ще се третира като единичен ненасочен ръб.)
Тогава ръбовете на графите могат да бъдат представени просто чрез двойки върхове от формата (a,b ), за които е допълнително посочено; дали ръбът е насочен или не. В този случай броят на ръбовете на графиката е същият като броя на двойките върхове, които представляват ръбовете на графиката.
Следователно в това, което следва, ще приемем, чеU е набор от двойки върхове. В този случай всяко ребро е представено от една двойка върхове или две двойки. Тоест, акоG = (V,U ) и двойката (a,b ) представлява ребро на графикатаG, тогава нотацията (a,b ) нU е разрешена.
Забележка. Можем да предположим, че горните условия забраняват дублиране на ръбове. Въведените ограничения не ограничават изучаването на графите по-долу, чиито дефиниции и резултати могат да бъдат разширени или обобщени за случая на графи с произволен брой ребра между двойки върхове. Когато представяме графи с множество ребра, можем да приемем, че всяка двойка върхове в тях е свързана с най-много едно ребро, което е свързано с числова характеристика, равна на множеството ребра между двойки върхове. Това характеризиране на ръбовете е полезно в случаите, когато връзките, представени от ръбовете, принадлежат към различни класове или са снабдени с допълнителна информация за дължината, цената или пропускателната способност.
Ребро, чиито начални и крайни върхове съвпадат, се нарича цикъл.
Брой ръбове, излизащи от даден връхa и различни от цикли, се нарича степен на този връх и се обозначава катоd (a ). Връх a, за който е в сила равенствотоd (a ) = 0, се нарича изолиран.
Граф, чиито ребра са неориентирани, се нарича неориентиран граф.
Както вече беше отбелязано, най-простият начин за представяне на графики е тяхната геометрична реализация. В този случай върховете на графите обикновено се представят от точки в пространството, които са обозначени със символи за върхове.
Помислете за пример за геометрична спецификация на графика, показана на фиг.5.2.:
а
v
e
Cd
Ориз.5.2.
Графиките могат да бъдат начертани така, че дъгите, съответстващи на ръбовете, да се пресичат. Това представяне на графики не е геометрична реализация, но в някои случаи може да е полезно или за предпочитане.
В допълнение към визуалното геометрично представяне и представяне на графики се използват и други методи за присвояване. Те позволяват графите да бъдат представяни като структури, които могат да се съхраняват и обработват с помощта на специални алгоритми и програми.
Нека разгледаме основните начини за специфициране на графики с помощта на специални структури.
1.Списъци с ръбове
Представянето на произволен граф с помощта на списък с ръбове се състои от попълване на масив, съдържащ всички двойки върхове, представляващи ръбовете на графиката. Недостатъкът на този метод на представяне е възможността за загуба на информация за изолирани върхове.
Матрици на съседство
НекаG = (V,U ) е граф с върховеV = v1, .v n>. Тогава матрицата на съседство на тази графика е квадратна таблица с размерn ´ n, чиито редове и колони са поставени ведно-към-едно съответствие на върховете на множествотоV.
Стойността на елемента от тази матрица, разположен в пресечната точка наi ти ред иj та колона, се определя от правилото:
=
За графиката, показана на фиг.5.2., матрицата на съседство е както следва: