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

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

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

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

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

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

Определение[редактиране | редактиране на кода]

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