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

Графът се разглежда като съвкупност от върхове (възли) и дъги (ребра). Използва се за представяне на съвкупност от обекти и техните връзки. Обикновено върховете съответстват на обектите, а дъгите — на отношенията между тях.
Графът е структура от данни, която се използва за решаването на редица интересни задачи от практиката. През последните десетилетия графите са обект на засилен интерес от страна на математиците и информатиците. Теорията на графите се обособи като обширен клон от дискретната математика с много интересни теореми и полезни приложения.
Много задачи от различни области на науката и практиката могат да бъдат моделирани с граф и решени, като се изпълни съответният алгоритъм върху него — намиране на път между две точки, оцветяване на географска карта с най-малко цветове, движение по шахматната дъска и др. Графите са модели на реални обекти и служат за представяне на сложна система от връзки — авиолинии, транспортни и комуникационни мрежи, компютърни мрежи, уебстраници, схеми в електротехниката и др.
Определение[редактиране | редактиране на кода]
Графът 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) ако V1ºV и Е1 Ç Е = празно множество.
Регулярен граф[редактиране | редактиране на кода]
Граф, в който всички възли са от еднаква степен, се нарича регулярен. Например пълният граф е регулярен със степен равна на броя върхове без едно.
Тегловен граф[редактиране | редактиране на кода]
Граф, в който на възлите и/или на ребрата са присвоени тегла, се нарича тегловен граф.
Равнинен граф[редактиране | редактиране на кода]
Равнинният граф може да се изобрази в равнината без да се пресичат ребра.
Двуделен граф[редактиране | редактиране на кода]
Възлите в двудяловия граф са разделени на две подмножества – и V1 и V2 и всеки възел има свързващи ребра само към възли от другото подмножество.
Свързан граф[редактиране | редактиране на кода]
Граф, за който между произволна двойка от върхове има път.
Несвързан граф[редактиране | редактиране на кода]
Граф, за който съществуват възли без път между тях. Всеки несвързан граф може да се представи като съвкупност от краен брой свързани графи, наречени компоненти.
Компонента[редактиране | редактиране на кода]
Максималния породен свързан граф, съдържащ даден възел.
Представяния на графи[редактиране | редактиране на кода]
Матрицата на съседство[редактиране | редактиране на кода]
Един възможен начин за представяне на граф е чрез матрицата на съседство. Тя се състои от 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