Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Графтағы маршрут – және , төбелері үшін, қабырғалармен байланысқан төбелерінің тізбегі. Мұндағы қабырғалар маршрут қабырғалары деп аталады. Маршрутты солардан өтетін деп айтамыз да, сол саны маршрут ұзындығы болады. Және де маршрут және төбелерін қосады дейміз де, олар сәйкесінше маршруттың басы және аяғы болады, ал олардың арасындағы төбелері аралық төбелер болады. Егер де болса, маршрут тұйық болады.
Жол – барлық қабырғалары әр түрлі маршрут. Егер де жолдың барлық төбелері де әр түрлі болса, ол жол қарапайым деп аталады.
Цикл – бұл тұйықталған жол. Егер де төбелері қос-қостап әр түрлі болса, циклы қарапайым болады.
Төмендегі 2.1 суреттегі графтағы төбелер тізбектері:
2.1 сурет.
Ендігі маршруттардың кейбір қасиеттерін анықтайық.
1 теорема. Әр түрлі төбелерді қосатын кез-келген маршруттың құрамында сол төбелерді қосатын қарапайым жол болады. Кей қабырғадан өтетін кез-келген циклде сол қабырғадан өтетін қарапайым цикл болады.
Орамдылық және компоненттер.
Егер де графтың кез-келген екі төбесін қосатын маршруты бар болса, ол граф орамды деп аталады. Мұндағы «маршрут» сөзін 1 теорема бойынша «қарапайым жол» сөзімен ауыстыруға болатынын айта кету керек.
Ендігі кез-келген графқа төбелер жиынында байланысу қатынасын анықтайық: егер де арасын қосатын маршрут бар болса төбесі төбесімен байланыса алады. Бұл қатынас рефлексивті, транзитивті және симметриялы болғандықтан оны эквивалентті қатынас деп айтамыз. Эквиваленттік кластары орамдылық аймақтары деп аталады, ал солардан туатын субграфтар – графтың орамдылық компоненттері деп аталады. Орамды графта тек бір ғана орамдылық компоненті болады – ол бүкіл граф.
2.2 суреттегі графтың төрт орамдылық аймақтары бар - , , , .
2.2 сурет.
Егер де графтың төбесін алып тастаса сол графтың орамдылық компоненттерінің саны өсіп кетсе – ол төбе шарнир деп аталады. 2.2 суреттегі графта 4 шарнир бар - ол , , , , төбелері.
Егер де графтың қабырғасын алып тастаса сол графтың орамдылық компоненттерінің саны өсіп кетсе – ол қабырға қылта деп аталады. 2.2 суреттегі графтағы қылталар - ол , , , , .қабырғалары.
3 теорема. Егер де графта төбесінен бөлек және төбелерін қосатын жолдардың бәрі де тек қана -дан өтетін болса төбесі шарнир болады.
4 теорема. Егер де графта белгілі бір қабырғаны құрамына қосатын қарапайым цикл болмаса, ол қабырға қылта болып табылады.