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

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

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

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

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

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

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

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

         Ако в ориентирания граф G=(V, E), подредената двойка (v, w) принадлежи на Е, то казваме, че има ребро от v към w. Ако в множеството на ребрата Е на неориентирания граф G=(V, E) има множество [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
  • https://en.wikipedia.org/wiki/Graph_(mathematics)

Външни препратки[редактиране | редактиране на кода]