БөЖ тақырыбы: Графтағы байланыстар Орындаған
жүктеу/скачать 67,12 Kb.
|
Графтардағы байланыстар
|
Ақтөбе өңірлік мемлекеттік университеті БӨЖ тақырыбы: Графтағы байланыстар Орындаған: МПКО ДОТ 2 жылдық студенті Омарова Іңкәр Бекежанқызы Тексерген: Бекбауова Алтыншаш Упуовна Графтардағы байланыстар Егер G граф төбелерінің кез келген жұбы үшін байланыстырушы тізбек бар болатын болса, онда мұндай графты байланысқан граф деп атайды. Графтардың қасиеттері: • Графтың əр төбесі тек бір ғана байланысу компонентіне кіреді. • Кез келген аяқталған графта байланы су компоненттерінің шектелген саны болады; • Тек жалғыз байланысу компонентінен тұратын граф байланысқан граф болып табылады; • Графтың əр байланысу компоненті, оның ішкі графы болып табылады; • Кез келген граф үшін не өзі, не оның қосымшасы байланысқан болып табылады. Қасиеттерді дəлелдеу. 4° жəне 5° қасиеттерді дəлелдейік G1 (V1 ,E1 ) – G (V,E) графының байланысу компоненті болсын. G графының G1 (V1 ,E1 ) компонентіне кірмейтін V2 =V\V1 тө белер жиынын қарастырайық. Егер V2 -ден барлық инцидентті қа бырғаларымен бірге əрбір төбесін өшірсек, G (V,E) графының G1 (V1 ,E1 ) байланысу компонентімен сəйкес келетін ішкі графын аламыз. G (V,E) n-ретті кез келген граф болсын, ал G=(V,E) – оның Kn графына дейінгі қосымшасы. Граф байланысқан болғанда, пайымдау айқын. G графы байланыспаған болсын, G1 (V1 ,E1 ) – оның байланысу компоненттерінің бірі жəне V2 =V\V1 . Онда кез келген v∈V1 , w∈V2 төбелері үшін – G қосымшасында vw ∈E қабырғасы бар. Сонда, V2 -дегі кез келген төбе Е-ге жататын V1 қабырғаның кез келген төбесімен байланыстырылған, ал V1 -дегі кез келген екі төбе, екі түйіні де E-де жатқан ұзындығы 2 болатын тізбекпен байланыстырылған. Сондықтан G графы байланысқан граф. Графтың байланысуы графтың топологиялық сипаттама ларының бірі. G графының төбелер байланысының саны (белгіленуіX(G)) төбелердің ең аз саны деп аталады, оларды өшіру (оған инцидентті қабырғалармен бірге) байланыспаған графқа немесе бір шеттетілген төбеден тұратын графқа алып келеді. Қабырғалық байланыс саны (белгіленуі λ(G)),G графының ең аз қабырғалар саны болып табылады, оны өшіру байланыспаған графқа алып келеді. Егер χ(G)≥k жəне λ(G)≥k орындалса, онда графы k-байланысқан деп аталады. G графының қосылуы бойынша, максималды k-байланысқан ішкі граф k-байланыс компоненті деп аталады. Сəйкес графтардың байланыс санының коммуникациялық жəне логикалық желілерін зерттеуде сол желілердің сенімділік дəрежесі деп түсіндіруге болады. Графтар теориясында байланысқан графтарды орнату тəсілдері зерттеледі. Олардың барысында k-байланысу немесе k-қабырғалы байланысу шарттары, əртүрлі байланыстар арасындағы қатынас, байланыс сандарының графтың өзге параметрлеріне тəуелділігі жəне т.с.с. зерттеледі. Сонда, егер δ(G) – G графының төбелерінің минималды дəрежесі болса, онда келесі теңсіздіктер дұрыс: χ(G)≤ λ(G)≤ δ(G). Сонымен, келесі пайымдаулар дұрыс деп есептейміз. Көршілес емес u жəне v төбелерін бөлетін ең аз төбелер саны, u жəне v-ны байланыстыратын ортақ төбелері жоқ қарапайым тізбектердің ең көп санына тең. G графы, оның кез келген төбелерінің жұбы ең болмағанда k-төбесі қиылыспайтын тізбектермен байланысқан жағдайда ғана k-байланысқан болады. Ұқсас теоремалар қабырғалар арасындағы байланыс үшін де дұрыс келеді. Кез келген төбелерінің жұбы ең болмағанда k-қабырғалы қиылыспайтын тізбектермен байланысқан жағдайда ғана граф k-қабырғаларымен байланысады. Өшіру (жою) барысында байланыспаған графқа əкелетін қабырғалар жиынын қиынды деп атаймыз. Əрбір графтағы u жəне v төбелерін бөлетін қабырғалары арқылы қиылыспайтын қиындылар саны көп бола- 29 ды, олар u мен v-ны байланыстыратын, яғни u жəне v-ның d(u,v) арақашықтығын байланыстыратын ең аз қабырғалар санынан тұратын қарапайым тізбекке тең. Анықтама 2. Егер G графының бір-бірімен тізбектеп (қарапайым тізбек) байланыспаған бірнеше төбелер жұбы бар болса, онда ол граф байланыспаған граф деп аталады. Байланыспаған графтың қарапайым мысалы ретінде оқшауланған төбелері бар графты айтуымызға болады. Теорема. Графтың V төбелер жиынын, графтың кез келген қабырғасы ішкі жиынның біреуінің төбелерін байланыстыратындай екі бос емес V1 жəне V2 ішкі жиындарына бөлгенде ғана граф байланыспаған болып табылады. Дəлелдеу. G(V,E) – байланыспаған граф болсын. Графтың кейбір v төбелерін нақтылап алып, оны v төбелерінен жəне онымен тізбектеп байланыстырған V төбелерінен тұратын V1 жиыны арқылы белгілейік. V1 жиыны бос емес (ең болмағанда v төбесінен тұрады) жəне V жиынымен сəйкес келмейді (V1 =V графы G(V,E) – байланысқан, себебі оның кез келген екі төбесі арасындаарқылы өтетін тізбек бар). V2 =V/V1 қосымшасын қарастырайық. V2 жиыны – бос емес жəне G(V,E) графының ешбір қабырғасы V1 -дің бірде-бір төбесін V2 -нің ешбір төбесімен байланыстырмайды. Сондықтан, алынып отырған V1 жəне V2 жиындары ізделініп отырған жиынын бөліктегеннен пайда болады. Керісінше, теорема шартын қанағаттандыратын V жиыны V1 ∪V2 бөліктегенде пайда болсын. G(V,E) графы байланыспаған граф екенін дəлелдейік. Əртүрлі жиындардан v∈V1 жəне w∈V2 ерікті төбелер жұбын алайық жəне осы төбелерді байланыстырушы тізбек бар деп есептейік. Мұндай тізбек, ұштары əр түрлі ішкі жиындарға жататын қабырғалардан тұрады, демек бұл шартқа қарама-қайшы. Теорема дəлелденді. Егер w=v немесе басы v жəне соңы w болатын тізбек бар болатын болса, онда v төбелеріне қарасты графтың w төбесін алуға болады. Теоремадан шығатын салдар. G графы байланысқан болу үшін, ондағы кез келген нақтыланған төбелері арқылы сол графтың қалған барлық төбелерін алуымызға болатындығы жеткілікті. Байланысқан граф, байланыспаған граф, байланысу компоненті, қасиеттері туралы тағы қайталап өтейік. Кез келген төбе- 30 ден кез келген өзге төбеге жол бар болса, онда бағытталмаған граф байланысқан болады (жол қабырғалардың кез келген санынан тұруы мүмкін). Мысалы: төмендегі 2.1-суретте граф байланысқан болып табылады. Алайда, егер 4 жəне 5 төбелер арасындағы қабырғаны өшірсек, онда ол байланысқан болмайды – 5 төбесінен ешбір төбеге бару мүмкін болмайды. Егер байланысу қасиеті орындалмаса, онда граф байланыспаған болады. Ары қарай мультиграфтарды, яғни екі төбесі екі немесе одан да көп қабырғалармен байланысқан графтарды ескермей, тек қана төбелер жұбы бір ғана қабырғамен байланысқан немесе байланыспаған графтарды қарастырумен шектелеміз. n төбелері бар граф байланысқан болу үшін, (n – 1) -ден кем емес қабырғалары болу керек. Егер графта *34 2 nn n − + кем емес қабырғалар болса, ол кепілді түрде байланысқан болады. Егер граф байланысқан жəне циклсыз болса, онда оның кез келген қабырғасын өшіру байланыстың жоғалуына əкеледі. Байланыспаған граф байланысу компонентінен тұрады. Бұл жиынның кез келген төбесі арқылы осы жиынның кез келген төбесіне қатынаса алатын, бірақ бұл жиынның бір де бір төбелері осы жиыннан тыс кейбір төбелеріне қатынаса алмайтын төбелер жиыны – байланысу компоненті болып табылады. Байланысу компонентінің төбелер саны граф төбелерінің санына тең екені айқын. 2.2-суретте екі байланысу компоненттері бар граф келтірілген. Байланыс компоненті тек бір төбеден тұруы мүмкін екендігі айқын көрініп тұр. Егер графта n төбе бар болса, онда граф n-нан аспайтын байланысу компоненттерінен тұрады. Байланысқан графта байланысу компоненті жалғыз. Байланыспаған графта кез келген байланысу компоненті n – 1 -ден аспайтын төбелерден тұрады. Егер графта k байланысу компоненті бар екені анық болса, онда кез келген байланысу компоненті n – k + 1-ден аспайтын төбелерден тұрады. Егер байланыспаған графта k-байланысу компоненті бар болса, онда байланысқан граф алу үшін, графқа кем дегенде k – 1 қабырға қосу қажет. Графтың байланысқан екендігін қалай анықтауға болады? Кейбір А төбесін таңдап алып, оны қатынас болған төбе ретінде белгілейміз (1), ал қалғандарын сəйкесінше қатынас болмаған төбе ретінде қарастырайық (0): А-ны ағымдағы төбе деп алайық. Ары қарай келесідей əрекеттерді орындаймыз. Қатынас болмаған іргелес төбелерді белгілеу: ағымдағы төбе үшін, онымен əлі қатынас болмаған іргелес төбелерді іздейміз жəне содан соң оларды қатынас болған төбе ретінде белгілейміз. Бізде k жаңадан белгіленген төбелер пайда болсын (жоғарыдағы 2.3-суретте олардың саны – 3). Кезек бойынша олардың біреуін ағымдағы төбе деп аламыз жəне онымен қатынаста болмаған іргелес төбелерге рекурсивті түрде белгілеулер жүргізіп, орындаймыз. Егер берілген төбелер арасында қатынас болған төбелер ретінде белгіленбеген іргелес төбелері болмаса, онда ағымдағы төбе үшін рекурсия орындалмайды. Егер осы əрекеттерден кейін барлық төбелер қатынас болған төбе ретінде белгіленсе, граф байланысқан, басқа жағдайда байланыспаған болады. Мысал. Келесі түрдегі граф берілген 2.4-сурет. Мұндағы төбедегі натурал сандар – қаншасыншы қатынастан соң қатынас болған төбе ретінде белгіленгендігін көрсетеді. Кез келген төбені таңдаймыз (1). Ары қарай, онымен үш көршілес емес төбелер белгіленеді (2, 3, 4). Ағымдық төбе (2) болады. Рекурсия: əлі қатынаспаған екі көршілес емес төбелерді белгілейміз (5 жəне 6). (5) үшін рекурсия қажет емес – оның қатынаспаған көршілес төбелері жоқ, ал (6) үшін рекурсия қажет – (7)-ні белгілейміз. 7-ші нөмірде əлі қатынаспаған көрші – 8-ші нөмір бар, ал 8-ші нөмірде қатынаспаған көршілес төбелер жоқ. (2)-ден шыққан рекурсивті шақырулар аяқталды. Ендігі кезекте (3) төбе, бірақ мұнда рекурсия қажет емес, (4) төбе қалды. Оның көршілес төбелерінің бірі (9) əлі де белгіленбеген, оны ретке келтіреміз. Сонда: Нəтижесінде шығатын қорытынды: кейбір төбелердің арасында қатынасу болмағандықтан граф байланыспаған болып табылады. жүктеу/скачать 67,12 Kb. Достарыңызбен бөлісу:
|