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

[1], [2], [3], [5], [16], [18].

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

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

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

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

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

0. 
   Ағаштар
   

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

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

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

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

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

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

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

1-сурет
Тамырды D ағашында бөлу оның төбелерінің жиынында жартылай реттелгенін анықтайдыда, егер және элементарлық тізбек тамырдан төбесінде -ні ұстайды.

Әрбір 0

төбе D2

ағаштың тамырын анықтайды, осы төбелерге іліну болып

табылады, мұнда

осы әрбір

D

ағаштың бөлігінде

D 0 D

.

Тамырды

D ағашында бөлу

оның

төбелерінің

жиынында жартылай

реттелгеніне

анықтайды да,

егер

және

элементарлық

тізбек

тамырдан төбесінде - ні ұстайды. Әрбір 0 төбеде

D ағаштың тамырын

анықтайды, осы төбелерге іліну болып табылады, мұнда

. Осы

әрбір

D ағаштың

бөлігіндеD 0D.

Барлық D0 ағаштың

бөліктері

өзінің

бұтақтарынан тамырына желімдеу арқылы пайда болады.

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

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

(^Vi0 - ден шығып ^Vin - ге жеткізуге тиісті ) не бағытсыздығы.

[^Vi0 ,^Vin ] жолы 1 , 2 , ..., n қырлары бойынша біртіндеп
^Vi0,^Vi1,…,^Vinтөбелері арқылы жүріле алады.Жолды табиғи қарастырғанда графтөбелері мен қырлары арқылы өтіп, қозғалған дененің үздіксіз (траекториясы) жолы деген мағынаны береді.
Графтың еселіксіз қырлары үшін жолды төбелердің тізбегі арқылы беруге болады.
Бағытсыз графтың жолдарынан тұратын тізбектелген төбелер мен қырлар тізбек деп аталады.
Бұдан кез – келген жол тізбек болады да, керісінше бағытсыз графтар үшін жол және тізбек ұғымдары бір мағынасын бере алады.
Егер (*) тізбегін керісінше қарастырсақ ^Vinn^Vn1n1^Vn2 …^V11^V0 - керісінше жазылған тізбек кейінгі жағдайда бұл тізбектерде айырмашылық жоқ,

сондықтан бұл тізбектер ^Vi0 мен ^Vin төбелерінен тұрады.

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

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

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

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

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

Арақашықтың ^{d V}1^,V2 үшін барлық қасиеттер орындалады:

А) ^{d V}1^,V2 ^{0,d V}1^,V2^0;V1^V2болғанда;

Б) ^{d V}1^,V2 = ^{d V}2^,V1 ;

Сондықтан ^V метрикалық кеңістікте тұрады.