Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану
Теорема2. Графтың әр түрлі төбелерінің әр жұбы бір және тек қана бір тізбекпен байланысатын кезде ғана, граф ағаш бола алады. Теорема 3
жүктеу/скачать 0,66 Mb.
|
| Теорема2. Графтың әр түрлі төбелерінің әр жұбы бір және тек қана бір тізбекпен байланысатын кезде ғана, граф ағаш бола алады.
Теорема 3. Әр ағаштың аспалы төбесі табылады. Теорема4 . Ағаштың кез келген бір қабырғасын өшірген кезде, ол не ағашпен, не төбелермен оқшауланған өзара байланысқан компоненттерге бөлінеді. Ағашқа кез келген жаңа қабырға қосылған кезде, ағашта қарапайым цикл түзіледі де, ол енді ағаш болуын тоқтатады. 3-суреттегі мысалдағы графтың и қабырғасын өшірген кезде, ол T1жәнеT2 екі ағаштан тұратын орман болып бөлінеді, ал е қабырғасын қосқаннан кейін, ол G циклдік графына айналады. 3-сурет
Сонымен қоса бағытталған қабырғалары бар, яғни доғалары бар ағаштар да қарастырылады. Егер ағаштың бір төбесі мен оның кез келген басқа төбесі арасында оңай жол бар болса, онда сол бағытталған ағаш тамыры бар праағаш деп аталады (4-сурет). Праағаштың тек бір ғана тамыры бола алады. 4-сурет
Ағаштың төбелерінің типтері және оның орталары. n төбелері барТ ағашын қарастырайық. Оның соңғы төбелерін 1- ші типті төбелер деп атайық. Енді 1ші түрдегі барлық төбелерді және соңғы қабырғаларды өшіріп тастайық. Нәтижесінде циклсіз орамдалынған T1графын аламыз, яғни тағы бір ағаш, бірақ ендігі жолы ең аз көлемді төбелері бар ағашты аламыз. T1 ағашының соңғы төбелерін Т ағашындағы 2-ші типті төбелер деп атайық. Сол сияқты 3-ші, 4-ші және т.б. типтегі төбелер анықталады. Ағаш максималды типтегі не бір, не екі төбеге ие бола алады. 5-суреттегі Т ағашының төбелерінің деңгейі сәйкес төбелердің жанында жазылып тұр. Мұнда оларды анықтауға мүмкіндік беретін процедуранының кезеңдері де көрсетілген. Егер Т ағашының екінші типтегі төбелерінің біреуін және оған инцидентті қабырғаларды өшіріп тастасақ, онда пайда болға ағаш тек бір ғана максималды типтегі төбеге ие болады. 5-сурет
k типті төбе максималды типтегі төбе болсын. Ағаш төбелерінің типтері анықтамасынан миксималды типтегі жалғыз төбенің эксцентриситеті оның типіне, яғни k-ға тең болатыны шығады. Ал максималды типтегі екі төбенінің әр қайсысының эксцентристеті k-1-ге тең. Демек, максималды емес типтегі төбелерінің кез келгенінің эксцентриситеті көбірек болады. Сондықтан кез келген ағаштың дәл ортасы (центр) максималды типтегі төбелері болып табылады. Ағаштың не бір, не екі дәл орта-сы болады. Қисынды G графының барлық төбелерінен құралған және ағаш болып табылатын Gграфының ішкі графы қылшық ағаш (қылшығы немесе қаңқасы) деп аталады. Графтың қылшық ағашы жалғыз емес. G графы қисынды болсын. Онда G графының қылшық ағашының (егер ол бар болса) n(G)-1 қабырғасы болуы керек. G графының кез келген қылшық ағашы G графынан m(G)-(n(G)-1)=m(G)-n(G)+1–ге тең қабырғасын өшірудің нәтижесі. 6-суретте G графы және оның G1және G2қылшық ағаштары берілген. 6-сурет
Тұжырымдама. Қылшық алу үшін өшіруге қажетті кез келген бағытталмаған G графының доғалар саны оларды қшіру тізбегіне байланысты болмайды және m-n+k–ға тең болады, мұндағы m-доғалар саны, n – төбелер саны, k – Gграфының қисынының компонентінің саны. 7-суреттегі G графы үшін m=8, n=7, k=2. Қылшық алу үшін, графтың үш қабырғасын өшіру керек. Осы әдісті екі ағаштан тұратын орман алу үшін де қолдануға болады. 7-суретте тамыры бар ағаш кескінделген. Ағаштың төбелері 4қабатқа бөлінген. v ағашының тамыры бірінші қабатта орналасқан. 7-сурет
Ағаштағы әрбір төбе белгілі бір қабатқа жатады. Қабаттың номері ағаштағы төбелердің ара қашықтығы мен тамырына тура келеді. 3-ші қасиет бойыншы әрбір байланыс i-ші қабаттағы қыр арқылы (i-1)-ші қабаттағы номермен төбемен байланыста болады да, ешқандай i -ші қабаттағы төбемен байланысты болмайды. Ағаштың осындай көрінісі өте қолайлы. Мұндай көрініс, аяқталған ағашта үнемі соңғы төбе болады. (мысалы ақырғы қабаттағы төбе, бірақ басқалары болуы мүмкін). жүктеу/скачать 0,66 Mb. Достарыңызбен бөлісу:
|