ГРАФТЫҢ КӨМЕГІМЕН ШЫҒАРЫЛАТЫН ҮШ ЕСЕП

ГРАФТЫҢ КӨМЕГІМЕН ШЫҒАРЫЛАТЫН ҮШ ЕСЕП

Қазым Бердібек

Аннотация. Бұл мақалада графтың ағаш түрін пайдалану арқылы үш есеп шығарылған.

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

1-ЕСЕП ( ) 1-суретте пунктердің жобасы көрсетілген. Бір пунктен екінші пунктке тек бір бағытта баруға болады. Әрбір пуктте тек бірден артық болуға болмайды. Сонда бірінші пункттен тоғызыншы пунктке неше жолмен баруға болады? Осы жолдардың қайсысы ең қысқа, ал қайсысы ең ұзын?

Шешуі: Бұл есеп кәдімгі күнделікті өмірде өздеріміз кездесіп қалатын «транспорттық есепке» жақын келеді. Жанармайлардың арзан емес бұл заманында осындай есептердің алатын орны өте зор. Осы шешу үшін графтарды «ағаштар» атты түсінігі кеңінен қолданылады.

Бірінші төбеден бастап тізілмелі түрде граф жолдарын ағашқа «жеткіземіз». Берілген графта қанша рет жолдар кірген болса сонша рет осы «жіктеуде» әрбір төбе кездеседі (2-сурет). Ең қысқа жол ағаштың салбыраған төбелерінің ең кіші «биіктігінде», ал ең ұзын жол ең үлкен «биіктігінде» аяқталады. (2-суретте «биктіктер» штрихталған сызықтармен кескінделген) ағаштың салбыраңқы төбелер саны барлық жолдар санын береді, ол бізде 14. Ең қысқа жол (1,5,9) ұзындығы екіге тең. Ең ұзын жол (1,2,3,6,5,7,8,9) ұзындығы жетіге тең.

Ескерту. 1)бұл мысал графтағы «жол ұзындығы» түсінігінің геометрия немесе географиядағы) «жол ұзындығ» түсінігінен айырмашылығы барлығын көрсетеді.

2)ағаш суреті тек қана барлық жолдардың санын, оның ішінде ең қысқа мен ең ұзынын көрсетіп ғана қоймайды, сонымен қатар оның маңызы барлық жолдарды бір мезгілде көруді және оның салыстыруды қамтамасыз етеді.

1-сурет 3-сурет

2-сурет

2- Есеп ( 3 суретте пункттердің төбесі көрсетілген. Бір пункттен екінші пунктке тек бір бағытта баруға болады. Әрбір пунктте тек бірден артық болуға болмайды.Сонда 1 пунктке неше жолмен баруға болады? Осы жолдардың қайсысы ең қысқа, ал қайсысы ең ұзақ?

Шешуі: Алдыңғы есеп сияқты шығарамыз. 1-ші төбеден бастап 8-ші төбеге дейін тізілмелі түрде граф жолдарын ағашқа “жіктейміз”. Сонда ағаштардың салбыраққа төбелер саны барлық жолдар санын береді,ол бізде 12 .Ең қысқа жол ағаштардың салбыраған төбелерінің кіші “биіктігінде”,ал ең ұзын жол ең үлкен “биіктігінде” аяқталады. Ең қысқа жол ұзындығы 2-ге тең ,олар екеу:(1,4,8) және (1,5,8). (4-сурет). Ал ең ұзын жол ұзындығы 7-ге тең :

(1,4,5,2,3,6,9,8) (4-сурет).

4-сурет

3- Есеп 5-ші суреттегі 1-ші пункттен 9-шы пунктке дейінгі мүмкін болатын жолдар санын және олардың ішінен ұзындығы ең қысқасын анықтау керек.

Шешуі: Бұл есепте алдынғы екі есепке ұқсас шығарылады. Осы жағдайда жердің жоспары пункттер арасындағы ұзындықтардың әртүрлілігіне байланысты құрылады 5-суретте пункттер арасындағы ұзындықтар графтардың қабырғаларының үстілерінде көрсетілген. Бұл есепке сәйкес келетін ағаш 6-суретте кескінделген. Осында 1 пункттен 9 пунктке баратын жолдар санының 12 екенін көреміз. Ең қысқа жол екеу,олар (1,2,5,6,9) және (1,2,5,9), олардың ұзындықтары 21,бірақ бірінші жолда 5 пункт ,ал екіншісінде 4 пункт қатысады.Ал ең ұзын жол (1,3,5,7,9) ұзындығы 38- ге тең.Ал (1,3,5,6,8,9) жолында 6 пункт болса да оның ұзындығы 29-ға тең.

5-сурет

6-сурет

ӘДЕБИЕТТЕР ТІЗІМІ

1. Г.Гретцер,Общая теория решеток , М. Мир,1982.

2. С.Д. Шапорев,Дискретная математика Курс лекции и практических занятий,Санкт-Петербург,2006

3. С.В.Судоплатов, Е.В.Овчиннинова, Элементы дискретной математики,учебник, Москва.Новосибирск,НГТУ,2003

4. Л.Ю.Березина,Графы и их применение,Пособие для учителей,Москва,Просвещение,1979.

5. Ж.А.Омаров, Торлар теориясына кіріспе.Оқу құралы,Талдықорған ,2013.