|
'''Графът''' се разглежда като съвкупност от върхове (възли) и дъги (ребра). Използва се представяне на съвкупност от обекти и техните връзки. Обикновено върховете съответстват на обектите, дъгите – на връзките между тях.
Графът е структура от данни, която се използва за решаването на редица интересни задачи от практиката. През последните десетилетия графите са обект на особен интерес както от страна на математиците, така и от страна на информатиците. [[Теория на графите|Теорията]] на графите се обособи като обширен клон от дискретната математика с много интересни теореми и полезни приложения.
Много задачи, от различни области на науката и практиката, могат да бъдат моделирани с граф и решени, като се изпълни съответният алгоритъм върху него – намиране на пътища между две точки, за оцветяване на географска карта с минимален брой цветове, движение по шахматната дъска и др. Графите са модели на реални обекти и служат за представяне на сложна система от връзки – авиолинии, транспортните и комуникационни мрежи, компютърни мрежи, web страници, схеми в електротехниката и други.
=== Обхождането в дълбочина ===
<nowiki>[url=https://bg.wikipedia.org/wiki/%D0%9E%D0%B1%D1%85%D0%BE%D0%B6%D0%B4%D0%B0%D0%BD%D0%B5_%D0%B2_%D0%B4%D1%8A%D0%BB%D0%B1%D0%BE%D1%87%D0%B8%D0%BD%D0%B0]Обхождане в [[Обхождане в дълбочина [/url|дълбочина]] - За разлика от обхождането в ширина, което е неудобно поради това, че е необходимо да се помнят всички обходени върхове (или поне върховете от последното обходено ниво), за да може да се построи следващото ниво. За обхождането в дълбочина са достатъчни само върховете, разположени на пътя от началния до текущия връх. Затова при ограничена компютърна памет за предпочитане са алгоритмите, построени по схемата в дълбочина. От друга страна, ако обхождането се прави с цел да се намери връх със зададени свойства и той се окаже на ниво с по-малък номер, тогава алгоритъмът в ширина ще го намери много по-бързо. Търсенето в дълбочина ще работи непредсказуемо дълго, защото може да се окаже, че върхът е измежду последните обходени (дори и да е на сравнително ниско ниво)</nowiki>
=== Обхождането в ширина ===
<nowiki>[url=https://bg.wikipedia.org/wiki/%D0%9E%D0%B1%D1%85%D0%BE%D0%B6%D0%B4%D0%B0%D0%BD%D0%B5_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D0%B0]Обхождане в [[Обхождане в ширина [/url|ширина]] - съществено за тази алгоритмична схема е понятието ниво на обхождане, което представлява подмножество на множеството от върховете на графа, което в резултат на обхождането в ширина, се разбива на нива. Дърво се нарича краен свързан ацикличен граф имащ поне два върха. Ако даден граф е дърво, то той има един скелет (покриващо дърво), който съвпада с него. Само свързаните графи притежават скелет. В общия случай скелетът на графа не е определен еднозначно. Под обхождане на връх разбираме присъединяването му към дървото, съставено от по-рано обходени върхове. И така, даден е свързан граф, без всякакви ограничения определен връх се избира за корен на бъдещото покриващо дърво на графа, построяването на което е крайния резултат от алгоритмичната схема обхождане в ширина.</nowiki>
== Източници ==
|
