Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану

1. 
   Графтың цикломатикалық саны деген не?
   
2. 
   Гамильтондық жол деген не?
   

0. 
   Графтағы циклдылық
   
1. 
   Ағаштар
   

0. 
   Графтағы циклдылық
   

Егер кезкелген ^G графтың қыры кем дегенде бір элементарлық циклге жататын болса, онда ол графтың қырын циклділік қыр деп атайды, ал қарсы жағдайда ациклділік деп атайды: Ациклділікке мысал ретінде ілінген қырды келтіруге болады. Төмендегі екі пікір орындалады:

1)Байланысты графтан циклдік қырды шығарғанда, оның байланыстылығы сақталады.

2)Ациклдік қырды шығарғанда байланыспайтын граф болып өзгереді.

Біріншіден кезкелген тізбек үшін циклдік қырды циклдегі қалған қырлардың тізбегімен өзгертуге болады.

Екіншісі қарсы жолмен дәлелденеді, егер байланысты қалпында қалатын болса, онда алынған қырдың соңы элементарлық тізбекпен байланыста болар еді; алынған қырды орнына қойсақ, онда элементарлық цикл шығар еді, бұл мүмкін емес, себебі бұл қыр ациклді.

0. 
   Ағаштар
   

Циклсіз байланысқан графты ағаш дейміз. Басқаша айтқанда барлық қырлары ациклділік болатын графты ағаш дейміз.

Төмендегі төрт шартты қанағаттандыратын графты ағаш дейміз:

0. 
   Кезкелген қырды алып тастағанда байланысты граф байланыспайтын болады.
   

0. 
   Қырлар саны төбелер санынан біреуі аз болатын байланысты граф.
   
1. 
   Бір элементарлық тізбекте байланыста болатын граф.
   

0. 
   Екі төбені байланыстыратын қырларды қосқаннан кейін пайда болған циклсіз граф.
   

Ағаштан кезкелген 0 төбені аламыз және оны тамыр , не ноль қабаттағы төбе дейміз. Көрші төбелерді 1-ші қабаттағы төбе, көрші ⁱ¹ қабаттағы төбені

0. 
   -ші қабаттағы төбе дейміз, тағы сол сияқты.
   

Ағаштағы әрбір төбе белгілі бір қабатқа жатады. Қабаттың номері ағаштағы төбелердің ара қашықтығы мен тамырына тура келеді. 3-ші қасиет

бойыншы әрбір байланыс ⁱ -ші қабаттағы қыр арқылы ⁱ¹ -ші қабаттағы номермен төбемен байланыста болады да, ешқандай ⁱ -ші қабаттағы төбемен байланысты болмайды. Ағаштың осындай көрінісі өте қолайлы. Мұндай көрініс, аяқталған ағашта үнемі соңғы төбе болады. (мысалы ақырғы қабаттағы төбе, бірақ басқалары болуы мүмкін).

1-сурет

0. 
   ^G байланысты графта біртіндеп барлық циклді қырларды алып тастаймыз. Сонда ^G графтың байланысты бөлігі сол төбелердің жиынынан тұратын элементарлық циклсіз ағашқа ^G графтың тұлғасын аламыз. Тұлға бір мағыналы емес таңдалады да, бірақ ациклді қырлары кезкелген тұлғаға кіреді.
   

1. 
   Ағаштар дегеніміз не?
   
2. 
   Циклдылық деген не?
   
3. 
   Ациклдылық дегеніміз не?
   
4. 
   Префиксті код деген қандай код?
   
5. 
   Макмиллан теңсіздігі.
   

^Vinжолдың соңы деп аталады (ұзындығы нольге тең болса, онда төбе біреугеғана болады). Жалпы алғанда (*) тізбегіндегі төбелер мен қырлардың ішінде қайталандыратын болуы мүмкін. Әрбір қыр үшін жолдың бағыты болуы тиісті.

Графтың еселіксіз қырлары үшін жолды төбелердің тізбегі арқылы беруге болады.

Бағытсыз графтың жолдарынан тұратын тізбектелген төбелер мен қырлар тізбек деп аталады.

Бұдан кез – келген жол тізбек болады да, керісінше бағытсыз графтар үшін жол және тізбек ұғымдары бір мағынасын бере алады.

Егер (*) тізбегін керісінше қарастырсақ ^Vinn^Vn1n1^Vn2 …^V11^V0 - керісінше жазылған тізбек кейінгі жағдайда бұл тізбектерде айырмашылық жоқ,

Егер (*) тізбегінде ^Vi0^Vinⁿ⁰ тізбегенің басы шекті төбелері дәл келсе, онда мұндай жолды n ұзындығы бар нұсқа (оған сәйкес цикл) деп аталады. (*) тізбегіне әрбір төбе және әрбір қыр бір рет кіретін болса, онда мұндай жол тізбек, контур, цикл қарапайымдылықтар (элементарлықтар) деп аталады.

Графта тізбекті қозғалған дененің жолы деп қарастыруға болады. Онда жолды - әрбір қыр арқылы бағдарлама бойынша өтетін траектория екендігін көрсетуге болады.

Қарапайым жол екі рет бір қыр арқылы өтпейді. (*) тізбегіндегі қырға тек санда ғана қайталануы мүмкін, онда қайталанатын кейбір төбе, не (*) тізбектің

Егер [^Vi0 ,^Vin ] тізбегі (**) тізбегінен бөлек, элементарлық тізбек емес болса, онда ^V төбесі (*) тізбегіне кем дегенде екі рет кіруі мүмкін.

элементарлық тізбекті, не (**) тізбегінен алуға болады. Оны бір ^Vi0 төбесіне ауыстыруға болады. Қарапайым циклге де осыны қолдануға болады:

0. 
   
   ^a,b,b,c,a,c тізбегін береді. Графтық
   ^V1^,V2 кез – келген тізбек элементарлық тізбектің төменгі бөлігін сол соңғыларымен ішінде сақтайды.
   

0. 
   Қарапайым, бірақ элементарлық емес тізбек элементарлық циклді бөлігі ете алады.
   

0. 
   қыры (^V төбесі) қарапайым цикл элементарлық төменгі циклді өзінің
   

Осындай тәсілмен жол және контур үшін ұқсас пікірлерді айқындайды.

0. 
   Кез – келген графта төбелердің бір – бірімен қатынасы байланысқан тізбектің болуы бұл тұйықталған транзитивтілік қатынастағы көршілестер (сыбайластар). Олар рефлексивтік қасиетті қанағаттандыратын (төбенің өзі ұзындығы нольге тең екенін көрсетеді), симетриялық қатынаста тізбектің бағытының шамасы болмайды және транзитивтік қатынаста (желімдеп
   

жапсыру т. б.) біртіндеп өтетін тізбектер төбелер эквиваленттік сыныптарға бөлінеді.

Төменгі графтың керілген кластағы төбелерін байланысқан компоненттер деп атаймыз. Кезкелген екі төбені кем дегенде цепь арқылы бір қоспадағы компонентті қосады. Ол әртүрлі компонентті төбелер тізбегі арқылы байланыспайды.

Графтың екі төбесі тізбек арқылы байланысса, ондай графты қоспалы граф деп атаймыз. Компонентті қоспасы бар кез – келген граф ^G оған байланыстыратын ^G графикалық компонентке, графқа жатпайтын біраз көп төбелермен қырларды қоссақ, онда пайда болған графтың бөлігі байланыспайтын болады. Көптеген есептер шығарғанда тек қана байланысты графтарды қарастырады, себебі байланыспайтын графқа есепті шешу әрбір қоспа компонентінің қарастыруға қажет етеді.

Графикалық байланыстығын тексеру үшін (берілген қырлардың тізімінен, бір матрицадан) еріксіз алынған оның төбесінен байланысқан компонентті құру жеткілікті.

Ол үшін көптеген қырларды іріктеп, оған басында көршілестерді, одан кейін көршілестерді іргелестермен қоса т. б. осы процессті мүмкіндігінше соза беруге болады. Егер графтың барлық төбелері іргелестен тұрса, онда байланысқан граф, басқаша графтың бөлігі, кіретін құралған төбелері қоспа компонентінен тұрады. Осы процессті қалған төбелеріне қолданып, барлық байланыстық компонентті айқындауға болады.

Байланысқан графтан көптеген төбелеріне ^V ара қашықтықты тізбектегі аз қырлардың саны ^{d V}1^,V2 ретінде ^V1 және ^V2 байланыстырады.