Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Поиск в глубину - вероятно, наиболее важная ввиду многочисленности приложений стратегия обхода графа. Идея этого метода - идти вперед в неисследованную область, пока это возможно, если же вокруг все исследовано, отступить на шаг назад и искать новые возможности для продвижения вперед. Метод поиска в глубину известен под разными названиями, например, "бэктрекинг", "поиск с возвращением".Понятия новой, открытой, закрытой и активной вершин для поиска в глубину имеют такой же смысл, как и для поиска в ширину. Отметим, что всегда имеется не более чем одна активная вершина.Обход начинается с посещения заданной стартовой вершины , которая становится активной и единственной открытой вершиной. Затем выбирается инцидентное вершине ребро и посещаетсявершина . Она становится открытой и активной. Заметим, что при поиске в ширину вершина оставалась активной до тех пор, пока не были исследованы все инцидентные ей ребра. В дальнейшем, как и припоиске в ширину, каждый очередной шаг начинается с выбора активной вершины из множества открытых вершин. Если все ребра, инцидентные активной вершине , уже исследованы, она превращается в закрытую. В противном случае выбирается одно из неисследованных ребер , это ребро исследуется. Если вершина новая, то она посещается и превращается в открытую.Главное отличие от поиска в ширину состоит в том, что при поиске в глубину в качестве активной выбирается та из открытых вершин, которая была посещена последней. Для реализации такого правила выбора наиболее удобной структурой хранения множества открытых вершин является стек: открываемые вершины складываются в стек в том порядке, в каком они открываются, а в качестве активной выбирается последняя вершина. Схематически это показано на рис. 5.1.
Рис. 5.1.Обозначим стек для открытых вершин через , остальные обозначения сохраняют тот же смысл, что и в предыдущем разделе. Через обозначается верхний элемент стека (т.е. последний элемент, добавленный к стеку). Тогда процедура обхода одной компоненты связности методом поиска в глубину со стартовой вершиной может быть записана следующим образом (DFS Depth First Search).
Procedure DFS(a)
Еще раз обратим внимание на основное отличие этой процедуры от аналогичной процедуры поиска в ширину. При поиске в ширину вершина, став активной, остается ею, пока не будет полностью исследована ее окрестность, после чего она становится закрытой. При поиске в глубину, если в окрестности активной вершины обнаруживается новая вершина , то помещается в стек и при следующем повторениицикла while станет активной. При этом остается в стеке и через какое-то время снова станет активной. Иначе говоря, ребра, инцидентные вершине , будут исследованы не подряд, а с перерывами.
Алгоритм обхода всего графа - тот же, что и в случае поиска в ширину (алгоритм 1 предыдущей лекции), только нужно очередь заменить стеком, а процедуру BFS - процедурой DFS.Свойства 1 и 2 поиска в ширину, отмеченные в предыдущем разделе, сохраняются и для поиска в глубину. Остается верной и оценка трудоемкости , но ее доказательство требует несколько иных рассуждений, так как каждая вершина теперь может становиться активной несколько раз. Однако каждое ребро рассматривается только два раза (один раз для каждой инцидентной ему вершины), поэтому в операторе if в строке 5 ветвь then (строки 6-9) повторяется раз. В этом же операторе ветвь else (строка 10) повторяется раз, так как каждая вершина может быть удалена из стека только один раз. В целом получается , причем остаются справедливыми сделанные в предыдущей лекции замечания об условиях, при которых имеет место эта оценка.
Граф түрлері
Графтар тәжірибе мен ғылымның әр түрлі салаларындағы математикалық модельдердің елеулі элементі болып табылады. Олар қиын күрделі жүйелердегі оқиғалар мен обьектілердің арасындағы өзара әрекеттестігін көрнекі көрсетуге көместеседі. Дискретті математиканың көптеген алгоритмдік есептері қалай болғанда да графтармен байланысты есептер ретінде ұйымдастырыла алады, мысалы, граф құрылымының қандай да бір ерекшелігін анықтау қажет, немесе графтың кейбір талаптарды қанағаттандыратын бөлігін табу, немесе берілген қасиеттер бойынша граф құру есептері. Оларда графтармен қандай да бір құнарлы жұмысты бастау үшін немесе графтар теориясын терең зерттеуге кірісу үшін қажетті минимум түсініктер келтірілген. Дәлелдеулер тек олардың күрделілігі кей бір интуитивті сезілетін шегінен аспаған жағдайларда ғана келтіріледі. Сондықтан, мысалы, Кирхгоф теоремасы немесе Понтрягин-Куратовский теоремасы сияқты маңызды факттер дәлелдеусіз хабарланады.
Өзара байланысқан элементтерден тұратын әр түрлі жүйелердің құрылымын сипаттау үшін графикалық сұлбалар көп қолданылады, элементтерді нүктелермен (шеңберлермен, тіктөртбұрыштармен және т.б.), ал олардың арасындағы байланыстарды – элементтерді қосатын сызықтармен немесе бағытталған сызықтар арөылы бейнелейді. Бұл ретте 1.1.суретте көрсетілген диаграммалар секілді диагррамалар шығады.
1.1.суретт
Әдетте осындай диаграммаларда элементтерді бейнелеу әдісі де, сызықтардың ұзындығы не формасы да маңызды емес, тек қандай элемент жұптары сызықтармен қосылғаны маңызды. Егер зейін салып қарасақ, 1.1а және 1.1 б суреттері , , , , , элементтері арасындағы бірдей байланыс құрылымын бейнелейтінін байқауға болады. Бұл құрылымды графикалық бейнелеуге сүйенбей, өзара байланысқан элемент жұптарын атап өту арқылы сипаттаса болады: , , , , , , . Сонымен, барлық мардымсыз нәрселерден ауытқысақ бізде екі тізім қалады: элементтер тізімі және элемент жұптарының тізімі. Ол екеуі математикада граф деп аталатынды құрайды. Бұл мысалдан граф түсінігі өздігінен геометрия немесе графикамен тікелей байланыспағындығы көрініп тұр. Дегенмен, графты сызу мүмкіндігі –бұл математикалық объекттің тартымды ерекшеліктерінің бірі.
"Граф" термині бір қырлы емес,оны әр түрлі кітаптарда келтірілген анықтамаларды салыстыру арқылы оңай байқауға болады. Бірақ осы анықтамалардың барлығында ортақтық бар. Кез келген жағдайда граф екі жиыннан тұрады – төбелер жиыны және доғалар (қырлар) жиыны, әр бір қыр үшін оны қосатын төбелер жұбы көрсетілген. Төбелер мен қырлар граф элементтері деп аталады. Мұнда тек ақырлы графтар, яғни екі жиыны да ақырлы болатын графтар қарастырылады. Графтың белгілі бір типінің толық анықтамасын алу үшін тағы үш кезеңді анықтап алу қажет.
Алдымен, біз және жұптарын әр түрлі деп есептейтін-есептемейтінімізді келісіп алу керек. Егер әр түрлі деп есептесек,онда реттелген жұптар (жұптағы элементтер реті маңызды), кері жағдайда – реттелмеген жұптар болады. Егер қыры төбесімен төбесін қосатын және жұбы реттелген болса, онда бұл қыр бағытталған деп аталады да, төбесі оның басы, төбесі –соңы болады. Егер бқл жұп реттелмеген болса, онда қыр бағытталмаған деп аталады да, екі төбесі-оның ұштары .
Келесі нақтылауды қажет ететін пункт – әр түрлі қырларда бірдей басы мен соңы бола алады ма? Егер болса, онда графта еселі қырлар рұқсат етіледі. Еселі қырлары бар графты мультиграф деп те атайды. 1.2 суретте екі граф бейнеленген, сол жақтағы бағытталған мультиграф, ал оң жақтағы-бағытталған еселі қырлары жоқ граф болып табылады.
жұбы сәйкес қойылған қыр, яғни төбесін -ның өзімен қосатын қыр ілгек деп аталады. Егер ондай қырлар рұқсат етілмесе, онда ілгексіз графтар қарастырылып жатыр делінеді.
1.2. сурет
Осы үш қасиетті қиыстыру арқылы граф түсінігі анықтамасының әр түрлі нұсқаларын алуға болады. Ең көп кездесетіні бағытталмаған еселі қырлары жоқ және ілгексіз графтар. Мұндай графтарды қарапайым графтар деп атайды. Егер графта еселі қырлары жоқ болса, онда сәйкес төбелер жұбы бар қыларды бірдей деп санауға болады – қырдың өзін төбелер жұбы деп есептеу. Ілгектерді болдырмау үшін, қырды жасаушы төбелер әртүрлі болу керектігін ескерту жеткілікті. Бұл қарапайым графтың келесідей анықтамасына алып келеді.
Анықтама. Қарапайым граф деп жұбы аталады, мұндағы - ақырғы жиын, - әртүрлі -дан алынған элементтердің реттелмеген жұптарының жиыны. жиынының элементтері графтың төбелері деп аталады, - жиынының элементтері графтың қырлары деп аталады.
Бұл анықтаманы аздап түрлендіру арқылы еселі қырлары жоқ графтың басқа түрлерінің анықтамасын алуға болады: егер «реттелмеген» сөзін «реттелген» сөзімен ауыстырсақ, онда ілгексіз бағытталған графтың анықтамасы шығады, егер «әртүрлі » сөзін алып тастасақ, ілгегі бар графтың анықтамасын алуға болады. Бағытталған графты көбінесе орграфом деп атайды.
Ары қарай біз "граф" терминін "қарапайым граф" мағынасында қолданамыз, ал графтың басқа түрлерін қарастыру барысында мұны әдейі талқылаймыз.
графының төбелер жиынын арқылы белгілейміз, қырлар жиынын - , төбелер санын - , қырлар санын - .
Анықтамадан көрініп тұрғандай қарапайым графтың берілуі үшін оның төбелері мен қырларын атап өту жеткілікті,сонымен қатар әр қыр төбелер жұбы болуы қажет. Айталық, мысалы, , . Сонымен с , графы берілген. Егер граф тым үлкен болмаса, онда оны төбелері шеңбер не басқа белгілермен бейнеленген,ал қырлары- төбелерді қосатын сызықтармен бейнеленген сурет арқылы көрнекі көрсетуге болады. Жоғарыда берілген графы 1.3. суретте көрсетілген. Біз графты бейнелеудің дәл осы тәсілін көп қолданамыз, сонымен қатар төбелердің белгіленуі кейде төбелерді бейнелейтін шеңбердің ішіне , кейде жанында орналастырылады, ал төбелердің аттары маңызды емес болған кезде олар қалдырып кетіледі.
1.3. сурет
элементтен тұратын қандай да бір жиынын алайық және төбелер жиыны бар әр түрлі (қарапайым!) графтарды қарастырамыз. Осындай графтар санын арқылы белгілейміз. Бұл графтар тек қырлар жиынымен ғана ажыратылады,ал әр бір қыр - жиынының әр түрлі элементтерінің реттелмеген жұбы. Комбинаторикада мұндай жұптар - нен 2-ден үйлестіру деп аталады, олардың саны мынаған тең:
Әр бір жұп графтың қырлар жиынына кіруі немесе кірмеуі мүмкін. Туындылау ережесін қолдана отырып келесі нәтижеге келеміз:
Теорема 1. .
Егер графта қыры болса ,онда және төбелері осы графта іргелес деп айтады, қыры , , төбелерінің әрқайсысына инцидентті , ал олардың әрқайсысы осы қырға инцидентті.
Берілген төбесімен іргелес графтың барлық төбелерінің жиыны осы төбенің аймағы (окрестность) деп аталады да, арқылы бейнеленеді.
Тәжірибе жүзінде көп есептерді шешу барысында ыңғайлы әрі қолайлы графты беру әдісі іргелестік тізімі деп аталады. Бұл тізімдер нақты мәліметтер құрылымы түрінде әр түрлі тәсілдермен жүзеге асырыла алады, бірақ кез келген жағдайда әр бір төбесі үшін онымен іргелес барлық төбелер көрсетіліп шығады, яғни жиынының элементтері. Графтардың осындай берілу әдісі төбенің аймағын тез көру мүмкіндігін береді.
төбесімен іргелес төбелер саны төбесінің дәрежесі деп аталады және арқылы белгіленеді.
Егер кейбір графтың барлық төбелерінің дәрежелерін қоссақ, онда әр бір қыры осы қосындыға өзінің 2-ге тең үлсін қосады, сондықтан келесі тұжырым әділ :
Теорема 2. .
Бұл теңдік «қол алысулар туралы лемма» ("лемма о рукопожатиях") ретінде танымал. Бұдан шығатыны тақ дәрежелі төбелер саны кез келген графта жұп болады.
дәрежелі төбені оқшауланған деп атайды.
Егер графтың әр бір төбесінің дәрежесі -ға тең болса, онда графты дәрежсіне тұрақты деп атайды.
Графтың дәрежелер жиынтығы - бұл кемімейтін ретпен жазылған граф төбелерінің дәрежелерінің реттілігі.
2. Қосжарнақтағы қосүйлесімділік
Графтағы қосүйлесімділік деп ортақ қосарлы төбелері жоқ қабырғалар жиынтығы аталады. Қосүйлесімділік туралы тапсырма, берілген графтағы неғұрлым көп қабырғамен қосүйлесімділікті табудан құралады. графының бұл санын арқылы белгілейміз. Графтың жабылған қабырғалары деп графтың кез-келген төбесі осы қабырғалардың біреуіне болса да инцидентті болатын қабырғалар жиынтығы аталады. графының жабылған қабырғаларындағы ең төменгі санды қабырғаларды арқылы белгілейміз. Жабылған қабырғалар тек жеке төбесі жоқ графтар үшін екеніне назар аударайық.
Қосүйлесімділік анықтамасы тәуелсіз төбе жиынтығының анықтамасына ұқсас, қосүйлесімділік деп кейде осы қабырғалардың тәуелсіз жиынтығын атайды. Бұл ұқсастық жабылған қабырғалар мен қосүйлесімділіктің арасындағы тығыз байланыспен күшейе түседі, дәл жабылған төбелер мен тәуелсіз жиынтықтардың өзара байланысы сияқты ұқсас болады. Тіптен, осы байланыстың сандық сипатын айқындайтын теңдік те, дәл осындай түрде болады (еске салсақ, тәуелсіздік саны және жабылған төбелер теңдеуімен байланысқан).
Қосжарнақты графтардағы қосүйлесіміділік
графы - және жарнақтары бар қосжарнақты граф, қосүйлесімділігі графында дейік. Кез-келген ұлғайтпалы жол, егер ол бар болса, жиынтығының төбесін жиынтығының төбесімен қосады.Кейбір ерікті төбесін айқындап алайық.Біз -дан басталатын ұлғайтпалы жолды тапқымыз келеді, немесе оның жоқтығын растауымыз керек. Алайда, төбесінен қандай кезектесе алмасатын жолдарға қолжетімді екенін айқындау үшін, төбесінен басталатын барлық кезектесе алмасатын жолдарды қарастырудың керегі жоқ. төбесін төбесі арасындағы арақашықтықтың жұп немесе тақ болуына қарай жұп немесе тақ деп атаймыз. Граф қосжарнақты болғандықтан, төбесін жұп (тақ) төбемен қосатын кез- келген жол жұп (тақ) ұзындықты болып келеді. Сондықтан, төбесінен жұп (тақ) төбеге апаратын кезектесе алмасатын жолдарда шеткі қабырға міндетті түрде күшті (әлсіз) болып табылады. Қолжетімділік дарақты түбірлі ең максималды дарақ ретінде анықтайық, онда түбірден басталатын әр жол кезектесе алмасатын болып табылады. Қолжетімділік дарақ бір мағыналы емесі анық, бірақ қосжарнақты графтағы әрбір осындай дарақ келесі қасиетке ие:
Лемма 1. төбесі тек қана және төбелерін қосатын кезектесе алмасатын жол болғанда ғана қолжетімділік дарағына жатады.
Дәлел. қолжетімділік дарағын қарастырайық, сондай-ақ, төбесінен кезектесе алмасатын жолдар арқылы қол жетерлік төбесінің кез-келгені осы дараққа жататынын дәлелдейік. төбесінен төбесіне қысқа кезектесе алмасатын жол бойымен индукция жүргіземіз. осындай жолдың соңғының алдындағы (яғни алдындағы ) төбесі дейік. Индукция бойынша, төбесі дарағына жатады. Егер ол жұп болса, онда төбесінен төбесіне кезектесе алмасатын жолдың кез-келгені күшті қабырғамен аяқталады. Сәйкесінше, дарағында төбесін оның әкесімен күшті қабырға байланыстырады, ал қабырғасы әлсіз болады.
Сондықтан дараққа төбесін және қабырғасын қоссақ, мен -ті қосатын дараққа апаратын жол кезектесе алмасушы болады.Демек, дарағында төбесі жоқ деп есептесек, онда ол максималды емес болып шығады, ал бұл енықтамаға қарама-қайшы. төбесі тақ болған жағдай да осылайша қарастырылады. Сонымен тапсырманы орындау үшін қолжетімділік дарағын құра білу керек. Бұл үшін төбесінен аздап түрлендірілген ендік іздеуді қолдану қажет. Стандартты ендің іздеуден айырмашылығы мұнда ашылатын төбелер жұп немесе тақ болып бөлінеді. Жұп төбелер үшін оларға инцидентті әлсіз қабырғалар, ал тақтарға күштілері зерттеледі. арқылы әдетте төбесімен шектесетін төбелер жиынтығы белгіленеді, - ендік іздеуде қолданылатын кезек. Егер төбесі ерікті болмаса, яғни күшті қабырғаға инцидентті болса, онда осы қабырғаның төбесі арқылы белгіленеді.