Уикипедия

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

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
Редакция без резюме
Редакция без резюме
Ред 7:
Много задачи, от различни области на науката и практиката, могат да бъдат моделирани с граф и решени, като се изпълни съответният алгоритъм върху него – намиране на пътища между две точки, за оцветяване на географска карта с минимален брой цветове, движение по шахматната дъска и др. Графите са модели на реални обекти и служат за представяне на сложна система от връзки – авиолинии, транспортните и комуникационни мрежи, компютърни мрежи, 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.<!-- === Ойлерови графи ===
Граф, в който е възможно да има път обхождаш всички ребра точно по веднъж са нарича Ойлеров граф.
 
В такъв граф броя на нечетните степени на върховете е 2 или 0.
 
== Формули ==
 
Ако от степента на всеки връх е n, то броя на ребрата в този граф е �1�. -->
 
== Понятия, свързани с графи<br> ==
=== Съседни върхове ===▼
 
▲=== Съседни върхове ===
Два върха се наричат съседни, когато съществува ребро между тях.
 
=== Инцидентност ===
На всяко ребро r съответства двойка върхове (v1, v2), казва се, че реброто r е инцидентно с v1 и v2.
 
Line 29 ⟶ 28:
Степента на даден връх се дефинира като броят на ребрата, с които той е свързан с другите върхове.
 
=== Изолиран връх ===
Връх от степен 0, или още такъв, който не е свързан с други върхове се нарича изолиран връх.  
 
Line 50 ⟶ 49:
[[Файл:Undirected.svg|thumb|90x90px|Неориентиран граф.]]
 
=== Неориентиран ===
=== Неориентиран ===
Графът е неориентиран, когато всичките му ребра са неориентирани. Всяко неориентирано ребро може да се представи като две ориентирани ребра.
 
=== Ориентиран ===
[[Файл:Directed.svg|thumb|84x84px|Ориентиран граф.]]
Ориентиран граф е този, на който всичките му ребра са ориентирани (има значение кой е първият връх на реброто).
 
=== Пълен граф ===
Граф, за който има ребра между всеки два върха, където n е броя на възлите.
 
Line 88 ⟶ 87:
 
== Представяния на графи ==
 
=== Матрицата на съседство ===
Един възможен начин за представяне на граф е чрез матрицата на съседство. Тя се състои от n реда и n стълба, където n е броят на върховете в графа. Всеки ред и стълб съответстват на конкретен връх. Ако има ребро между връх 1 и връх 2 то елементът на позиция [1][2] е 1, а ако няма ребро - – 0.
 
=== Матрицата на инцидентност ===
Друг възможен начин за представяне на граф е чрез матрицата на инцидентност. Матрицата на инцидентност се различава за неориентирани и ориентирани графи. В нея редовете представляват върховете, а стълбовете - – ребрата. Елементът на позиция [ i ][ j ] е -1, ако реброто j излиза от върха i, 1 ако реброто j влиза във върха i и 0 в противен случай.
 
== Обхождане на графи ==
Този метод решава задачата за намиране на всички пътища между два възела чрез алгоритмичната схема за обхождане на граф. Това е процедура, при която систематично, по определени правила "се„се посещават"посещават“ всички върхове на графа. Съществуват два вида обхождане, които могат да се използват като алгоритмични схеми. И двата подхода строят коренови дървета но имат принципни различия.
 
=== Обхождането в дълбочина ===
Обхождане в [[Обхождане в дълбочина|дълбочина]] -  – За разлика от обхождането в ширина, което е неудобно поради това, че е необходимо да се помнят всички обходени върхове (или поне върховете от последното обходено ниво), за да може да се построи следващото ниво. За обхождането в дълбочина са достатъчни само върховете, разположени на пътя от началния до текущия връх. Затова при ограничена компютърна памет за предпочитане са алгоритмите, построени по схемата в дълбочина. От друга страна, ако обхождането се прави с цел да се намери връх със зададени свойства и той се окаже на ниво с по-малък номер, тогава алгоритъмът в ширина ще го намери много по-бързо. Търсенето в дълбочина ще работи непредсказуемо дълго, защото може да се окаже, че върхът е измежду последните обходени (дори и да е на сравнително ниско ниво)
 
=== Обхождането в ширина ===
Обхождане в [[Обхождане в ширина|ширина]] - – съществено за тази алгоритмична схема е понятието ниво на обхождане, което представлява подмножество на множеството от върховете на графа, което в резултат на обхождането в ширина, се разбива на нива. Дърво се нарича краен свързан ацикличен граф имащ поне два върха. Ако даден граф е дърво, то той има един скелет (покриващо дърво), който съвпада с него. Само свързаните графи притежават скелет. В общия случай скелетът на графа не е определен еднозначно. Под обхождане на връх разбираме присъединяването му към дървото, съставено от по-рано обходени върхове. И така, даден е свързан граф, без всякакви ограничения определен връх се избира за корен на бъдещото покриващо дърво на графа, построяването на което е крайния резултат от алгоритмичната схема обхождане в ширина.
 
== Източници ==
Взето от „https://bg.wikipedia.org/wiki/Граф_(математика)“.