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

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

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

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

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

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

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

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