Өндірістік үрдістерде графтар теориясын қолдану

 графы – байланысқан деп  аталады, егер оның кез-келген  екі  және - төбелері үшін қарапайым - дан - ға болған тізбек болса. Кез-келген графты компоненттері деп аталатын қиылыспайтын байланыстырушы графтарға бөлуге болады. Осылайша, байланыстырушы емес граф кем дегенде екі компонентке ие. Екі төбе эквивалентті, егер біреуінен екіншісіне қарпайым тізбек бар болса. Байланыстырушы граф бір компоненттен тұрады. Граф байланыстырушы емес граф деп аталады, егер оның компоненттер саны бірден көп бола.

Байланыстырушы граф өзінен қарапайым циклды көрініске  ие, егер оның әрбір төбесі екінші дәрежесіне ие болса. Егер - байланыстырушы граф және оның әрбір төбесінің дәрежесі екі болса, онда - қарапайым цикл. Берілген графтың әрбір төбесінен басқа кез-келгеніне жол бар. Жолды кейбір төбесінен бастайық және осы төбе тиісті екі қабырғаның біреуімен жүріп өтей»ік. Екінші төбеге жетіп, одан екінші қабырға арқылы шығайық т.с.с. Керектігінше графтың барлық қабырғалары жүріп өтіледі, біз бастапқы төбеге ораламыз.

Егер  - графы қарапайым цикл болса, онда әрбір төбенің дәрежесі екіге тең.

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

Қарапайым циклде дәрежесі екіге тең болмаған төбе болуы мүмкін емес екендігін көрсетейік.

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

Егер қандайда бір төбе екіден үлкен дәрежеге ие болса, онда ешқандай қарапайым цикл, осы төбе жататын, барлық қабырғаларды қамтуы мүмкін емес.

Графтарға әкелетін есептер.

          1. Есеп. Бір парақты Плюшкин үш бөлікке кеседі. Алынған парақтардың кейбірін ол тағы да үш бөлікке қырқады. Бірінші жаңа парақтарды ол тағыда үш кішкентай бөлікке кеседі және т.с.с Плюшкин қанша парақтар санын алады, егер - парақ кессе?

Шешімі. Парақтарды граф төбелері деп есептейік. Бір парақты кескенде парақтар саны екіге екіге көбейеді. Егер де - парақ кесілген болса, онда парақ пайда болады.

2. Есеп. Бір компанияда бес адамның әрқайсысы басқа екі адаммен таныс деп есептейді. Мұндай компанияның болуы мүмкін бе?

Шешімі. Бұл компанияның  әр бір адамын граф төбесі деп есептейік. Екі танысты қабырғамен біріктірейік. Қарастырылып жатқан компанияда «төртбұрышты» немесе «ұшбұрышты» ерекшелеуге болмайды, өйткені , шартты қанағаттандыратын компанияны құруға болмайды. Яғни танысу схемасы  жалғыз. Көпбұрышқа ұқсайтын  әрбір схеманы цикл деп атайды. Ежелгі гректер «цикл»ді «дөңгелек» деп атаған.

3.Есеп. Есептің қойылымын графтар тіліне аударайық. Шахматистердің әрбіріне сәйкес граф төбесін қояйық, бір- бірімен партияны ойнап қойған шахматтистерге сәйкес келетін төбелерді жұптай қабырғалармен біріктіреміз. Тоғыз төбелі  графты аламыз. Оның төбелер дәрежесі сәйкес ойыншылармен ойнаған партиялар санына тең. Кез – келген тоғыз төбесі бар графта әрдайым кем дегенде екі бірдей дәрежелі төбелер табылатынын көрсетейік.

       Тоғыз төбелі графтың әрбір төбесі - ге теңдәрежеге ие болуы мүмкін. - графы бар делік, оның барлық төбелері әртүрлі дәрежеге ие, яғни - тізбегінің әрбір саны оның тек қана бір төбесінің дәрежесі болып табылады. Бірақ бұл мүмкін емес. Шынында да, егер графта ноль дәрежелі – төбесі болса, онда графта сегіз дәрежелі - төбесі табылмайды, өйткені - төбесі графтың қалған барлық төбелерімен, соның ішінде  – мен де, қабырғалар арқылы қосылуы керек. Басқаша айтқанда, тоғыз төбесі бар графта  бір мезгілде 0 және 8 дәрежелі төбесі болуы мүмкін емес. Осыдан шығатыны, дәрежелері өзара тең, кем дегенде екі төбе табылады. Осылайша, кез- келген уақытта кем дегенде екі  бірдей партия санын ойнаған екі адам тобы .

       Қорытынды. n – төбесі бар кез- келген графта,  , әрдайым кем – дегенде екі бірдей дәрежелі төбе табылады.

4. Есеп. Тоғыз адам бір айналымды шахматтық турнир өткізуде. Кейбір кезде, дәл екеуі бірдей партия санын ойнады. Дәл бір ойыншы әлі бір партия ойнамағанын немесе дәл бір ойыншы барлық партияның ойнағанын дәлелдеу керек.

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

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

       Дәл екеуі бірдей дәрежеге ие тоғыз төбелі графта 0 немесе 8 дәрежелі екі төбе болуы мүмкін емес екендігін дәлелдейік.

       Дәл екі төбелі оқшауланған, ал қалғандары әртүрлі дәрежеге ие тоғыз төбелі граф табылды делік. Онда, егер осы оқшауланған екі төбені қарастырмасақ, дәрежелері сәйкес келмейтін жеті төбелі граф қалады. Бірақ бұл жағдайда графтың болуы мүмкін емес. Демек бұл болжам дұрыс емес.

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

      Есепке оралайық. Дәлелдеу керек болғандай, қарастырылған тоғыз ойыншының тек қана біреуі әлі бірде – бір партия ойнаған жоқ немесе тек қана біреуі барлық партияларды ойнады. Бұл есепті шешу барысында тоғыз санын кез- келген басқа натурал санмен ауыстыруға болады.  .

Қорытынды. Егер  n – төбелі графта ( ) дәл екі төбесі бірдей дәрежеге ие болса, онда бұл графта әрдайым дәл бір 0- дәрежелі төбе немесе дәл бір (n-1)  дәрежелі төбе табылады.

 

Анықтамалар мен  мысалдар

       - төбелер жиынымен графының біріктіру матрицасы деп -өлшемді - матрицасын айтады, онда - элементі графындағы және - біріктіретін қабырғалар санына тең. Берілген граф төбелерінің белгілерін өзгерте отырып бірнеше біріктіру матрицаларын алуға болады. Бұл - матрицасының қатарлармен бағандар реттігінің өзгеруіне алып келеді. Бірақ нәтижеде әрдайым теріс емес бүтін сандардан тұратын симметриялық матрица пайда болады, ол кез – келген қатардағы немесе бағандағы сандар қосындысы сәйкес төбенің дәрежесіне тең болатын қасиетке ие. Әрбір түйін төбе дәрежесінде бір рет ескеріледі. Керісінше, кез-келген берілген симметриялық матрицадан графты теріс емес сандардан құралған болып табылатын бірегей изоморфизмге дейінгі дәлдікпен. Бұдан шығатыны, графтар теориясын ерекше типтегі матрицаларды үйренуге алып келуге болатындығында. 

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

Қабырғалар жиыны бос  граф, толық байланысқан емес немесе бос граф деп аталады. n – төбелі толық байлыныспаған графты - арқылы белгілейміз. Кез- келген екі төбелі біріктірілген қарапайым графты толық граф деп атаймыз. n – төбелі толық граф әдетте - арқылы белгіленеді. Барлық төбелері бірдей дәрежеге ие графты регулярлы граф деп атайды. Егер әрбір төбенің дәрежесі - ге тең болса, онда граф регулярлы дәреже деп аталады. 3-дәрежелі регулярлы граф кубтық немесе үш валентті граф деп аталады. Әрбір толық байланысқан емес граф 0-дәрежесіне жүйелі болып табылады, ал әрбір - толық графы - дәрежесі жүйелі емес. Үнемі графтардың ішіндегі ерекше қызық тудыратыны- платондық графтар – бес дұрыс көпқабырғағыштың – платондық денелердің: тетраэдра, куба, октаэдра, доденаэдра және икосаэдра.

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

Біріктіру матрицасына мысал, граф берілді делік.

 

 
Біріктіру матрицасы 

 

 

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

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

 Осылайша, , онда - және - арасындағы арақашықтық.

 

4. Қабырғаларды жою, көпірлер

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

 Көпірлер қасиеттерін қарастырайық.

1. - қабырғасы көпір болып табылады, егер және төбелерін біріктіретін - жалғыз жол болса.

2. - қабырғалы көпір болып табылады, егер екі және төбелерін біріктіретін әрбір жол мен - ны қамтыса.

3. - қабырғасы көпір болып табылады, егер ол ешбір циклге тиісті болмаса

 Үшінші қасиеттің әділдігін дәлелдейік.

Тура теорема. Егер - қабырғасы ешбір циклге тиісті болмаса, онда - көпір.

- қабырғасы ешбір циклге тиісті  болмағандықтан оны жойған кезде  мен - біріктіретін жол қалмайды, яғни  - көпір болып табылады.

Кері теорема. Егер - қабырғасы көпір болса, онда - ешбір циклге тиісті емес.

Егерде  - қабырғасы циклге тиісті болса, онда - қабырғасын жойған кезде мен - байланыстыратын екінші жол қалатын еді, яғни - қабырғасы көпір болмайтын еді. Бұдан, - циклге тиісті емес.

 

5. Ағаштар.  Ағаштардың саналуы.

Әрбір төбелер жұбын  біріктіретін тек қана бір тізбегі  бар байланыстырушы графтар ағаштар деп аталады. Ағашты цикл қамтымайтын байланыстырушы граф деп те анықтасақ болады.

Мысал. Үстел теннисі бойынша кубок олимпиадалық принцип бойынша ойнатылуда. Кездесулер де тең есеп кездеспеу керек. Келесі турға тек алдынғы турда жеңген команда жіберіледі. Жеңілген командалар ойыннан шығады. Кубокты жеңу үшін команда барлық ойындарда жеңіске жету қажет. Кубок ойындарына 16 команда арыз берді.

 

Ойындардың өткізілуі граф түрінде көрсетілген.

 

 

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

Осы ағаштың көмегімен  қандай ақпаратты алуға болады.

1. Кубок ойындарының барлық қатысушылар санын (төменгі ярус төбелерінің саны).
2. Ойындардың өткізу этаптарының санын (ағаштағы төбелерден «ярустар» саны, төменгі есептелмегенде.!
3. 1/8,  ¼,  ½ - финалда қатысатын командалар санын ( сәйкесінше 4-ші, 3- ші, 2-ші ярустардағы төбелер саны).
4.   Кубок жеңімпазын табу үшін ойналатын кездесулер санын ( төменгі «яруссыз» графтағы төбелер саны.) бірақ оқшауланған төбеден тұратын ағашты да граф деп есептеу ыңғайлы. Ағаштың әрбір төбелерін біріктіретін тек бір жол бар. Орман деп ағаштардың бірігуін көрсететін байланысқан емес графты атайды. Ағаштағы және ормандағы әрбір қабырға көпір болып табылады. (3-қасиет).

Мысал.

Әрбір компонентті ағаш болып табылатын 4 компоненттен құралған орман көрсетілген.

 

Анықтама бойынша ағаштар  мен ормандар қарапайым граф болып  табылады. Көптеген көрсеткіштері бойынша  ағаш өзінен граф нетривиалдық типін көрсетеді. Байланыстырушы - графында, кейбір таңдалған циклге тиісті, бір қабырғаның жойылуы қалған графтың байланыстығын бұзбайтыны белгілі. Осы процедураны қалған циклдердің біреуіне қолданайық, осылайша ешбір цикл қалмағанша қайталаймыз. Нәтижеде - графының барлық төбелерін байланыстыратын ағашты аламыз, ол остовтық ағаш немесе остов немесе - графынд каркасы деп аталады.