Уикипедия

Граф (математика): Разлика между версии

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
мРедакция без резюме
м Редакция
Ред 8:
 
== Определение ==
ГрафГрафът G=(V, E) сепредставлява наредена състоидвойка от крайно, непразно множество на върховете V, и множество на ребрата Е. n е броя на върховете V, а е – броя на ребрата Е. акоАко ребрата са представени във вид на подредени двойки (v, w), то графа се нарича ориентиран, v е начало, а w – край на дъгатареброто (v, w). Ако ребрата не са наредени двойки, а множества от два елемента, то графграфът се нарича неориентиран. (заб. В ориентирания граф може да има ребро (а, а), а в неориентирания – не).
неориентиран. (заб. В ориентирания граф може да има ребро (а, а), а в неориентирания – не).
 
         Ако в ориентирания граф G=(V, E), подредената двойка (v, w) принадлежи на Е, то казваме, че има ребро тоот v към w. Ако в множеството на ребрата Е на неориентирания граф G=(V, E) има множество [v, w], то считаме, че има ребро между v и w и казваме, че възела (върха) v е свързан с върха w.<!-- === Ойлерови графи ===
граф G=(V, E) има множество [v, w], то считаме, че има ребро между v и w и казваме, че възела (върха) v е свързан с върха w.<!-- === Ойлерови графи ===
Граф, в който е възможно да има път обхождаш всички ребра точно по веднъж са нарича Ойлеров граф.
В такъв граф броя на нечетните степени на върховете е 2 или 0.
Line 23 ⟶ 21:
 
=== Съседни върхове ===
СъществуваДва върха се наричат съседни, когато съществува ребро между тях.
 
=== Инцидентност ===
Line 29 ⟶ 27:
 
=== Степен на връх ===
БроятСтепента на даден връх се дефинира като броят на ребрата, с които даден връхтой е свързан с другите върхове.
 
=== Изолиран връх ===
Връх от степен 0, /или още такъв, който не е инцидентенсвързан с ребро/други върхове се нарича изолиран връх.  
 
=== Примка ===
Ребро, свързващо един и същ връх, т.е. ребро, на което началото и края му съвпадат, се нарича примка.
 
=== Паралелни ребра ===
ДвеПаралелни исе наричат две или повече ребра, които свързват два върха.
 
=== Тегло на ребро ===
Стойност, присвоена на всяко ребро, с която му придава тегловен коефициент. Тегла най-често изразявамеизползваме, за да изразим количествено отличаване на отделните ребра като например разстоянието между върховете.  
 
=== Тегло на връх ===
ВсекиНа всеки връх имасъщо иможе да се припише стойност – например площ на населено място .
 
=== Път в граф ===
Път между два върха енаричаме последователностпоследователността от съседни върхове или ребра, през които преминаваме, за да достигнем от единия до другия връх, т.е. път между два върха съществува, ако е възможно да се премине по ребрата от първия до втория връх. Първият връх е начало, а вторият – край на пътя. Ако в пътя няма повтарящи се дъги, то пътят се нарича прост.
 
== Видове графи ==
Line 55 ⟶ 53:
 
=== Ориентиран ===
Ориентиран - графътграф е ориентирантози, когатона който всичките му ребра са ориентирани (има значение кое е първото ребро).
 
=== Пълен граф ===
Line 61 ⟶ 59:
 
=== Празен граф ===
Граф на който всички възли са висящиизолирани (няма нито един клон). В такива графи G(V,E), E –е празно множество.Брой а броя ребра =е равен на 0.
 
=== Допълнителен граф ===
Line 67 ⟶ 65:
 
=== Регулярен граф ===
ВсичкиГраф, в който всички възли са от еднаква степен, се нарича регулярен. (ПълниятНапример пълният граф е регулярен със степен =равна на броя върхове без n-1едно.)
 
=== ТегловиТегловен граф ===
НаГраф, в който на възлите и/или на клонитеребрата са присвоени тегла, се нарича тегловен граф.
 
=== Равнинен граф ===
МожеРавнинният граф може да се изобрази в равнината без да се пресичат ребра.
ребра.
 
=== Двудялов граф ===
ВсичкиВъзлите възлив двудяловия граф са разделени на две подмножества – и  V<sub>1</sub> и V<sub>2</sub> и всеки възел има свързващи ребра само към възли от другото подмножество.
и всеки възел има свързващи ребра само към възли от другото подмножество.
 
=== Свързан граф ===
Граф, за който между всичкипроизволна възлидвойка от върхове има път.
 
=== Несвързан граф ===
Граф, за който съществуват възли без път между тях. Всеки несвързан граф може да се представи като съвкупност от краен брой свързани графи, наречени компоненти.
краен брой свързани графи, наречени компоненти.
 
=== Компонента ===
Максималния породен свързан граф, съдържащ даден възел.
възел.
 
== Представяния на графи ==
 
=== Матрицата на съседство ===
Един възможен начин за представяне на граф е чрез матрицата на съседство. Тя се състои от n реда и n стълба, където n е броят на върховете в графа. Всеки ред и стълб съответстват на конкретен връх. Ако има ребро между връх 1 и връх 2 то елементът на позиция [1][2] е 1, а ако няма ребро - 0.
на позиция [1][2] е 1, а ако няма ребро - 0.
 
=== Матрицата на инцидентност ===
Друг възможен начин за представяне на граф е чрез матрицата на инцидентност. Матрицата на инцидентност се различава за неориентирани и ориентирани графи. В нея редовете представляват върховете, а стълбовете - ребрата. Елементът на позиция [ i ][ j ] е -1, ако реброто j излиза от върха i, 1 ако реброто j влиза във върха i и 0 в противен случай.
 
== Обхождане на графи ==
Този метод решава задачата за намиране на всички пътища между два възела чрез алгоритмичната схема за обхождане на граф. Това е процедура, при която систематично, по определени правила "се посещават" всички върхове на графа. Съществуват два вида обхождане, които могат да се използват като алгоритмични схеми. И двата подхода строят коренови дървета но имат принципни различия.
 
=== Обхождането в дълбочина ===
иматОбхождане принципнив различия.дълбочина Обхождането- За разлика от обхождането в ширина, което е неудобно поради това, че е необходимо да се помнят всички обходени върхове (или поне върховете от последното обходено ниво), за да може да се построи следващото ниво. За обхождането в дълбочина са достатъчни само върховете, разположени на пътя от началния до текущия връх. Затова при ограничена компютърна памет за предпочитане са алгоритмите, построени по схемата в дълбочина. От друга страна, ако обхождането се прави с цел да се намери връх със зададени свойства и той се окаже на ниво с по-малък номер, тогава алгоритъмът в ширина ще го намери много по-бързо. Търсенето в дълбочина ще работи непредсказуемо дълго, защото може да се окаже, че върхът е измежду последните обходени (дори и да е на сравнително ниско ниво)▼
Обхождане в дълбочина - И двата подхода строят коренови дървета но
▲имат принципни различия. Обхождането в ширина е неудобно поради това, че е необходимо да се помнят всички обходени върхове (или поне върховете от последното обходено ниво), за да може да се построи следващото ниво. За обхождането в дълбочина са достатъчни само върховете, разположени на пътя от началния до текущия връх. Затова при ограничена компютърна памет за предпочитане са алгоритмите, построени по схемата в дълбочина. От друга страна, ако обхождането се прави с цел да се намери връх със зададени свойства и той се окаже на ниво с по-малък номер, тогава алгоритъмът в ширина ще го намери много по-бързо. Търсенето в дълбочина ще работи непредсказуемо дълго, защото може да се окаже, че върхът е измежду последните обходени (дори и да е на сравнително ниско ниво)
 
=== Обхождането в широчина ===
Взето от „https://bg.wikipedia.org/wiki/Граф_(математика)“.