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

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

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

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

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

Определение редактиране

Графът 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