2. Планарлылық критерийі

және (3.7 сур) графтары планарлы емес графтардың эталоны болып табылады. Ал қалған басқа планарлы емес графтардың немесе “ұқсас” ішкі графы болады. “Ұқсас” дегеннің мағынасы қандай?

графының элементар стягивание негізі мынада: а) U-дан қабырғасын алып тастаймыз; б) U –ғы x және y символдарын z символымен алмастырамыз; в) X-тан x, y төбелерін алып тастаймыз; г) z –ті X-ке қосамыз. G графының элементар стягивание екі сыбайлас x және y төбелерінің олардың арасындағы қабырға жойылғаннан кейін бір z төбесіне бірігуін айтады. графы графына стягиваемым деп аталады егер де графы -ден тізбектелген элементар стягиваний жолымен алынатын болса (3.8 сур).

Планарлылықтың бірінші критерийін бір – бірінен тәуелсіз орыс математигі Л.С. Понтрягин және польшалық математик К. Куратовский дәлелдеді.

Понтрягин - Куратовский теоремасы. Граф сонда тек сонда ғана планарлы болады, қашан оның құрамында немесе стягиваемых ішкі графы болмаса.

М ысал. графы (3.9, а) планарлы емес, себебі ішкі графы (3.9, б) графына изоморфты (3.9, в). Вершины графа графының изоморфизмін айыру үшін екі түспен боялған.

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

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

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

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

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

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

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

Дәріс 14

Дәріс сабақтың құрылымы:

Графтардың байламдылығы

1. Маршруттар. Байламдылық компоненттері.

2. Эйлер шынжыры мен циклдары. Цикломатикалық сан

1. Маршруттар

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

М ысал. G графында (3.12 сурет) тізбегі ұзындығы 5-ке тең маршрутты анықтайды, ол 5 төбені 4 төбемен қосады; – ұзындығы 5-ке тең шынжыр; – қарапайым шынжыр; – қарапайым цикл.

Байламдылық компоненттері

графы байламды деп аталады, егер кез келген төбелер жұбы үшін осы төбелерді қосатын шынжыр табылса. Мысалы, графы (3.13 сур) байламды болып табылады, ал – байламды емес ( және төбелері шынжырмен біріге алмайды).

G графының байламдылық компоненті деп G графының максималды байламды ішкі графын айтады. графында екі байламдылық компоненті бар (3.13 сур): G –x₅,x₂ төбелері бар және олардың қабырғаларын қосатын ішкі граф; G – вершины төбелері мен олардың қабырғаларын қосатын ішкі граф. G және G ішкі графтарының ортақ төбелері мен қабырғалары жоқ, сонымен қатар ,яғни {G,G} байламдылық компонентінің жиыны графының бөліктеуін құрады.