1. Тал және орман

Анықтама. Циклсіз байламды граф тал деп аталады. Циклсіз байламды емес граф – орман деп аталады.

Талдың тамыры ретінде оның кез келген төбесін алуға болады. Талдың жапырағы деп дәрежесі 1-ге тең x төбесін айтамыз: . Талдың сабағы – тамырды жапырақпен қосатын кез келген шынжыр.

3.18 суретте тамыр ретінде 1 төбесі, жапырақтары 3,5,6,7,8,9 төбелері болады; сабағы –1-2-5 немесе 1-4-8 және т.с.с. шынжырлар болып табылады.

2. Талдардың қасиеттері

Айталық графында - төбелердің сангы, - қабырғаларының саны, k – байламдылық компонентінің саны болсын.

1 қасиет. G графы тал болады сонда тек сонда ғана, қашан оның цикломатикалық саны және байламдылық компонентінің саны .

Бұл қасиет анықтаманың басқаша тұжырымдалуы болып табылады: тал – байламды граф, ендеше ; тал – циклсіз граф , ендеше .

2 қасиет. Егер де G графы – тал болса,онда оның қабырғаларының саны төбелерінің санынан бір бірлікке кем.

1 қасиет бойынша и , бұдан , т.е. .

3 қасиет. Талдың кез келген төбелер жұбы жалғыз ғана қарапайым шынжырмен қосылуы мүмкін.

Кері жориық. Айталық онда бұндай шынжыр болмайтын төбелері бар болсын. Ендеше G графы байламды емес, ал бұл шартқа қайшы (G – тал).

Айталық енді қандай да бір төбелер жұбы үшін x және y қосатын екі қарапайым шынжыр бар болсын. Онда цикл құрылады, алайда шартқа қайшы келеді (G­ – тал).

Бұдан, кез келген төбелер жұбы үшін бұндай шынжыр бар және ол жалғыз болады.

4 қасиет. Төбелер санымен берілген байламды графтардың арасында тал максималды циклсіз граф болып табылады.

Расында да, талдың кез келген екі сыбайлас төбесін қабырғамен қосу арқылы цикл аламыз, себебі 3 қасиет бойынша осы төбелерді қосатын шынжыр бар болады.

5 қасиет. Тал минималды байламды граф болып табылады.

Цикломатикалық сандар қасиетіне ие, талда . Қабырғаны жою арқылы ішкі графын аламыз,бұл үшін , алайда 2 қасиет бойынша , бұдан және , яғни графы байламды емес.

3. Графтың каркасы

Есеп. Алты қала автожолдар желісімен қосылған (3.19 сур). Қалалар арасында қарым қатынас сақталынатындай ең көп жолдарды жабу керек.

Б ұл есепте байламды графын аламыз және оның остовты қабырғаларының саны ең аз байламды ішкі графын құру керек. 5 қасиет бойынша ( 3.5.2 қараңыз) – тал.

Анықтама. G графының каркасы деп G графының сондай байламдылық саны бар, бірақ циклсіз остовты ішкі графын айтады.

Б айламды графтың каркасы – тал болатындығы, ал байламды еместікі – орман болатындығы айқын. Каркас жалғыз ғана тәсілмен құрылмайды. 3.20 суретте автожолдардың сұлбасы үшін екі әр түрлі каркас келтірілген (3.19 сур).

Теорема. Графтың каркасын құру үшін қабырғасын жою керек.

Теореманы байламды граф үшін дәлелдейік , . Айталық – G графының каркасы болсын. айырымын қарастырайық. – тал болғандықтан, онда . Ендеше, каркасты құру кезінде қабырға жойылған.

Байламды емес граф үшін теорема дәл осылайша дәлелденеді (каркас әрбір байламдылық компоненті үшін құрылады).

3.19 суреттегі граф үшін – 4 қабырғаны жою керек. Сондықтан да оның каркасы (3.20 сурет) қабырғадан тұрады.

₂

Ұсынылған әдебиеттер:

1. Нұрсұлтанов Қ.Н., Дискретті математика және математикалық логика. – Семей 2002.

2. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. –М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.

3. Смыслова З.А.. Дискретная математика (Учебное пособие), Томск, 2000.

4. Қ.Жетпісов., Математикалық логика және дискретті математика. Алматы, 2011.

5. Шапорев С.Д. Математическая логика. Курс лекций и практических заниятий.- СПБ.: БХВ-Петербург 2005. - 416стр.

6. Тишин В.В. Дискретная математика в задачах и примерах. БХВ-Петербург 2008.