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

Жалпы жағдайда - арқылы - төбелермен, - қабырғалармен және

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

Теорема. - төбелі ағаш қабырғаға ие.

Дәлелдеу: Оқшауланбаған  төбе болып табылмайтын бір  - ағашынан дәл сол төбелерімен екі ағашты алу үшін - дан бір қабырғасын жою қажет. Үш ағаш алу үшін - қандайда  бір екі қабырғаны жоюкерек. Ең көбі - төбелі - ағаштан барлығы оқшауланған болатын -ағаш алуға болады. Ол үшін - ағашынан қабырғаны жою керек. Сонымен,  - төбелі ағашта шынында да қабырға.

 

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

Графтарды санау теориясы кейбір қасиетке ие, изморфтық емес графтар санын есептеу методтарын құрумен айналысады. Бұл теория шамамен  ХІХ – ғасырдың 70 – жылдары пайда болды және  Кэли атымен байланысты. Оның байқауы бойынша бұл есеп әрбір төбенің дәрежесі 4 және 1ге тең ағаштар санын санауға әкелетінін тапты. Қазір графтарды санау бойынша көптеген есептер шешілген.

Бірнеше анықтамаларды  қарастырайық

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

Мысал. 4 төбелі ағашта белгілердің әртүрлі орналасуы:

 

 

Суретті мұқият қарайтын болсақ екінші белгіленген ағаш біріншісі  төңкерілген екеніне көзіміз  жетеді, ал бұдан шығатыны, бұл екі белгіленген ағаш изоморфты. Басқа жағынан еш біреуі үшінші белгіленген ағашқа изоморфты емес  - төбенің дәрежесіне қарасақ болғаны. Бұдан шығатыны, берілген ағаштағы әртүрлі белгілердің орналасуларының жалпы саны 4!/2=12, тең болу керек, өйткені кез – келген белгілердің орналасуының төңкерілуі жаңа обьектіге әкелмейді. Осылайша суретте көрсетілген ағаштағы белгілердің әртүрлі орналасуының жалпы саны төртке тең болуы керек, өйткені оның  орталық төбесі төрт әртүрлі әдістермен белгіленуі мүмкін, олардың әрқайсысы белгілердің орналасуын анықтайды. Бұдан шығатыны, төрт төбелі барлық белгіленген ағаштардың саны он алтыға тең. Осы нәтижені -төбелі белгіленген ағаштармен біріктіретін Кэли теоремасын қарастырайық.

 

6. Жазық граф

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

 

Мысал. Жазық емес графқа мысал ретінде бес төбелі толық  граф болуы мүмкін. Оның жазық көрсетілуін  көрсетудің кез – келген әрекеті сәтсіз аяқталады.

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

Мысал.

 

 

Суретте -  графының үш граніменжазық көрсетілуі көрсетілген: (1,5,4,1),(1,3,2,4,1),(1,2,3,1). Қарапайым (1,2,4,1)- циклмен шектелген жазықтық бөлігі грань болып табылмайды, өйткені (1,2,3,1)- циклын қамтиды. Граньды шектейтін қарапай цикл граньдің шекарасы деп аталады. Екі граньды көрші граньдар деп  атаймыз, егер олардың шекаралары кем дегенде бір ортақ қабырғаға ие болады.

Мысал.

 

 

Осы графтағы қарапайым (1,2,3,4,1)- циклмен шектелген жазықтық  бөлігі грань болып табылады, өйткені (4,5) граньдің ішінде орналасқан қабырғасы циклды құрамайды.

Берілген мысалдағы  жазықтықтың штрихтелген бөлігі грань болып табылмайды, өйткені ол циклді қамтиды және де жазықтықтың бұл бөлігі циклмен шектелмеген. (1,2) қабырғасы циклдерді біріктіретін көпір болып табылады. Мұндай көпірлертосауыштар деп аталады.

 

        Грань ретінде графтық жазық көрінісіден тыс жерде орналасқан жазықтық бөлігін қарастырсақ та болады. Ол «ішінен» қарапайым циклмен шектелген және басқа циклдерді қамтымайды. Жазықтықтың бұл бөлігін шексіз грань

деп атайды.

Мысал. 

 

 

Суретте шексіз граньның бөлігі штрихтелген. Графтың кез – келген жазық көрсетілуі шексіз граньға ие емес, немесе дәл бір шексіз граньға ие. Ерекше жағдай ретінде ағаштың және ормандың жазық көрсетілімінде шексіз грань ендіріледі. Ағашпен орманның жазық көрсетілуінде грань ретінде суреттің барлық жазықтығын қабылдайды.

Екі граф гомеоморфты, егер олардың екеуіде оның қабырғаларына  жаңа екі дәрежелі төбелер «қосу» арқылы бір графтан алынуы мүмкін болса.

Мысал.

Көрсетілген графтар  гомеоморфты және дәл осыны кез  – келген екі циклдық графтар  туралы айтсақ болады. Графтардың гомеоморфтығы эквивалентіктің қатынасы болып табылады. «гомеоморфты» - терминінің ендірілуі тек қана технологиялық көз – қарас жағынан ғана ыңғайлы. Екі дәрежелі төбенің қосылуы немесе өшірілуі планарлыққа ешқандай қатынасы жоқ. Қандай –да бір қабырғаға, мысалы ,бір төбенің , мысалы , қосылуы келесі тәртіпте іске асырылады: қабырғасы және төбелеріне инцидентті. Онда қабырғасы графтан өшіріледі, бірақ екі жаңа қабырға қосылады: және төбелеріне инцидентті , және  және - төбелеріне инцидентті

Графтардың гомеоморфтылығы  түсінігін ендіру келесі маңызды  нәтижені орнатуға мүмкіндік береді, ол Куратовтың теоремасы атымен белгілі, ол графтың планарлығының керекті және жеткілікті шартты береді.

 

7. Гомеоморфтық графтар

Теорема (Куратовский, 1930). Граф планарлық, егер немесе - гомеоморфты подграфтар қамтымаса.

Куратовский теоремасының дәлелі ұзақ және қиын болғандықтан бұл  жерде ол келтірілген.  Оған қарамастан, Куратовскийдің теоремасын планарлықтың басқа критериясын алу үшін қолданайық. Тағыда екі анықтаманы қарастырайық. Элементарлық тьарту деп келесі процедураны айтады: қабырғасын алып оны «тартамыз», яғни ні жойып және және -ды арттырамыз. Осылайша алынан төбе бастапқыда және ге инцидентті болып қабырғаларға инцидентті болады.

Мысал.

 

- графы  - графына тартылып жатқан деп аталады, егер -ты  - дан кейбір элементарлы тартулар тізбегі көмегімен алуға болады.

Граф планарлық болып  табылады, егер ол немесе - гомеоморфты подграфтар қамтымаса.

 

8.Эйлер графы. Эйлер формуласы

Анықтама. G=(V, Х) графы  берілсін. G графының барлық төбелері мен  қабырғаларын қамтитын цикл Эйлерлік цикл деп аталады.       

    Эйлерлік циклі бар мультиграф Эйлерлік граф деп аталады.

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

Дәлелдеу. Графтың байланысқан болатындығы оның эйлерлік граф екендігінен шығады. Эйлерлік цикл әрбір қабырғаны тек бір рет қана қамтитын болғандықтан, әр төбеге қарындаштың ұшы қанша рет барса сонша рет шығады. Сондықтан әр төбенің дәрежесі екі бірдей қосылғыштан тұрады: біреуі төбеге ену нәтижесі, екіншісі төбеден шығу нәтижесі. Ендеше, төбе дәрежесінің жұп болғаны.     

      Осы теоремаға кері тұжырым да дұрыс болады.

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

3, 4 суреттерде Эйлерлік  емес және Эйлерлік графтар көрсетілген.

3-суреттегі граф Эйлерлік емес, бірақ р₅ және р₃ төбелері шеттері болатын α₁, α₂, α₃, α₄, α₅, α₆  қабырғалар тізбегі құрайтын Эйлерлік жолы бар. 4-суретте көрсетілген графтағы α₁, α₂, α₃, α₄, α₅, α₆, α₇, α₈, α₉, α₁₀ қабырғалар тізбегі Эйлерлік цикл құрайды

Р1		α2	Р2	Р3
			α6
α1		α3	α5
		α4
Р5			Р4

3-сурет.  
 

 

		α2
α1
	α5		α8
α6					α3
α10	α7
		α9		α4

 
 4-сурет.

Эйлер формуласы

 

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

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

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

Суретте біз жойып  жатқан қабырғалар қисықтар арқылы көрсетілген. Алынған ағашта төбелер санын белгілейік - , қабырғалар саны - , граньдар саны .

- теңдігі әділетті.

Ағашта бір грань, яғни . Графтан қабырғаларды жою операциясы оның төбелер мсанын өзгерпейді, яғни , ағашта . Бұдан , яғни , сондықтан немесе .

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

 

 

Мысал.

 

 

 

9. Дирак теоремасы

         Граф гамильтондық болу үшін керекті және жеткілікті шартты іздеу, графтар теориясының негізі шешілмейтін есебі болады. Гамильтондық графтар туралы өте аз белгілі. Белгілі теоремалардың көбісі келесі көрініске ие «егер - графы жеткілікті графтар санына ие болса, онда - графы гамильтондық граф болып табылады. Осы теоремалардың ішіндегі ең белгілісі Г.Э.Диракка тиісті теорема болып табылады, сондықтан Дирак теоремасы атымен белгілі.

        Теорема(Дирак,1952). Егер қарапайым графта - төбелерімен, кез –келген - төбесі үшін болса, онда - графы гамилтондық болып табылады.

         Ескерту. Осы кең танымал теореманың бірнеше дәлелденуі бар, бұл жерде біз Д.Дж.Ньюман дәлелін келтіреміз.

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

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