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

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

Егер k=1…n үшін e_k   V_{ik 1},V_ik ^G графтың тізбектелген төбелері мен қырлары V_i0 e₁ V_i1 e₂ … V_in-1 e_n V_in (*) V_i0төбесінен шығып V_in төбесіне беттесе, онда ол V_i0 төбесі - төбесі жолдың басы, V_in төбесі - жолдың соңы деп аталады (ұзындығы нольге тең болса, онда төбе біреуге ғана болады). Жалпы алғанда (*) тізбегіндегі төбелер мен қырлардың ішінде қайталандыратын болуы мүмкін. Әрбір қыр үшін жолдың бағыты болуы тиісті. (V_i0 -ден шығып V_in –ге жеткізуге тиісті) не бағытсыздығы.

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

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

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

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

Қарапайым жол екі рет бір қыр арқылы өтпейді. (*) тізбегіндегі қырға тек санда ғана қайталануы мүмкін, онда қайталанатын кейбір төбе, не (*) тізбектің мынадай түрі болуы мүмкін V_i0 l₁ V_i1 l₂ … V_in-1 l_n V_in (*)

Элементарлық жол, тізбек, нұсқа(контур), цикл G графтарының астындағы кейбір графты қарастырайық. 1–ші суреттегі бейнеленген V₁ l₁ V₂ l₃ V₄ l₅ V₃ l₄ V₅l₅V₆ қарапайым тізбекті көрсетеді де, бірақ элементарлық бола алмайды, себебі l₁ және l₂ қырлары қарама–қарсы бағытталған):

V₄ l₃ V₂ l₂ V₃l₅V₄ - элементарлық нұсқа (контур).

Егер V_i0 e₁ V_i1 e₂ … V_in-1 e_n V_in тізбегі (**) тізбегінен бөлек, элементарлық тізбек емес болса, онда ^V төбесі (*) тізбегіне кем дегенде екі рет кіруі мүмкін. ^Vik төбесіне екі рет кіретін (*) тізбегінің бөлігі цикл болады да, оларды сызған сан (*) тізбегінен қалғандарын ^Vi0 және ^Vin бар тізбекті құрайды. Осылай элементарлық тізбекті, не (**) тізбегінен алуға болады. Оны бір ^Vi0 төбесіне ауыстыруға болады. Қарапайым циклге де осыны қолдануға болады:

1) [V₁, V₂] кез – келген тізбек элементарлық тізбектің төменгі бөлігін сол соңғыларымен ішінде сақтайды.

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

3) l қыры (V төбесі) қарапайым цикл элементарлық төменгі циклді өзінің бө-лігі етеді, ол l(V) арқылы өтеді.

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

2. Кез – келген графта төбелердің бір – бірімен қатынасы байланысқан

тізбектің болуы бұл тұйықталған транзитивтілік қатынастағы көршілестер (сыбайластар). Олар рефлексивтік қасиетті қанағаттандыратын (төбенің өзі ұзындығы нольге тең екенін көрсетеді), симетриялық қатынаста тізбектің бағытының шамасы болмайды және транзитивтік қатынаста (желімдеп жапсыру т. б.) біртіндеп өтетін тізбектер [a,b], [b,c],[ c, a] тізбегін береді. Графтық төбелер эквиваленттік сыныптарға бөлінеді. Төменгі графтың керілген кластағы төбелерін байланысқан компоненттер деп атаймыз. Кезкелген екі төбені кем дегенде цепь арқылы бір қоспадағы компонентті қосады. Ол әртүрлі компонентті төбелер тізбегі арқылы байланыспайды.

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

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

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

Байланысқан графтан көптеген төбелеріне V ара қашықтықты тізбектегі аз қырлардың саны d(V₁, V₂) ретінде V₁ және V₂ байланыстырады. Арақашықтың D(V₁, V₂) үшін барлық қасиеттер орындалады:

1. 
   d(V₁, V₂)=0, d(V₁, V₂)>0; (V₁ ≠ V₂)болғанда
   

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