Граф (математика)

Вижте пояснителната страница за други значения на Граф.

Диаграма на неориентиран граф с шест върха и седем ребра

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

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

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

Определение

Графът G = (V, E) представлява наредена двойка от крайно непразно множество на върховете V и множество на ребрата Е. Ако ребрата са представени във вид на наредени двойки (v, w), то графът се нарича ориентиран, v е начало, а w — край на реброто (v, w). Ако ребрата са ненаредени двойки, то графът се нарича неориентиран. Ако двата края на ребро съвпадат, реброто се нарича примка.

Понятия, свързани с графи

Съседни върхове

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

Инцидентност

На всяко ребро r съответства двойка върхове (v1, v2). Реброто r се нарича инцидентно с върховете v1 и v2.

Степен на връх

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

Изолиран връх

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

Примка

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

Паралелни ребра

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

Тегло на ребро

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

Тегло на връх

На всеки връх също може да се припише числова стойност — например площ на населено място, цена на стока и др.

Път в граф

Път наричаме редица от съседни върхове (и ребрата, които ги свързват). Първият връх в редицата се нарича начало на пътя, а последният — край на пътя. Ако в пътя не се повтарят ребра, то пътят се нарича прост.

Видове графи

Неориентиран

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

Ориентиран

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

Пълен граф

Граф, за който има ребра между всеки два върха, където n е броя на възлите.

Празен граф

Граф на който всички възли са изолирани (няма нито един клон). В такива графи G(V,E), E е празно множество. а броя ребра е равен на 0.

Допълнителен граф

Възлите на основния и допълнителния граф съвпадат. Ако в основния граф има път между два възела, то в допълнителния няма и обратно. е допълнителен за G(V,E) ако V₁ºV и Е₁ Ç Е = празно множество.

Регулярен граф

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

Тегловен граф

Граф, в който на възлите и/или на ребрата са присвоени тегла, се нарича тегловен граф.

Равнинен граф

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

Двуделен граф

Възлите в двудяловия граф са разделени на две подмножества – и V₁ и V₂ и всеки възел има свързващи ребра само към възли от другото подмножество.

Свързан граф

Граф, за който между произволна двойка от върхове има път.

Несвързан граф

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

Компонента

Максималния породен свързан граф, съдържащ даден възел.

Представяния на графи

Матрицата на съседство

Един възможен начин за представяне на граф е чрез матрицата на съседство. Тя се състои от n реда и n стълба, където n е броят на върховете в графа. Всеки ред и стълб съответстват на конкретен връх. Ако има ребро между връх 1 и връх 2 то елементът на позиция [1][2] е 1, а ако няма ребро – 0.

Матрицата на инцидентност

Друг възможен начин за представяне на граф е чрез матрицата на инцидентност. Матрицата на инцидентност се различава за неориентирани и ориентирани графи. В нея редовете представляват върховете, а стълбовете – ребрата. Елементът на позиция [ i ][ j ] е -1, ако реброто j излиза от върха i, 1 ако реброто j влиза във върха i и 0 в противен случай.

Обхождане на графи

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

Обхождането в дълбочина

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

Обхождането в ширина

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

Вижте също

Източници

Иржи Седлачек, „Теория на графите“, „Наука и изкуство“, София, 1967
Красимир Манев, „Увод в дискретната математика“, издателство КЛМН, София, 2003, ISBN 954-535-136-5