2.4. Эйлерлік графтар Эйлерлік граф есептеріне жазықтықта тұйық қисықтың әр бөлігін тек бір рет қана сызып өту қажет болатын бас қатыру есептері мысал бола алады.

Тарихы жағынан топология және графтар теориясы Л.Эйлердің Кенигсберг көпірлері туралы есепті шығаруынан бастап пайда болды. Бұл есеп 1736 жылы Петербург ҒА-ның журналында жарияланған. Кенигсберг (қазір Калининград) қаласы Прегал өзенінің екі жағасында және өзен ішіндегі екі аралда орналасқан. Қала халқы оның бір бөлігінен екінші бөлігіне көпір арқылы өтеді. Аралдар және жағалар 7 көпірлермен қосылған (8-сурет). «Кенигсбергтің бір ауданындағы (құрылықтағы) үйінен шыққан адам әр көпірден бір-ақ рет өтіп, қаланы түгел аралап, шыққан үйіне қайта орала ма?» Кенигберг есебі – осы. Жағадағы аудандарды А және В әріптерімен белгілесек, аралдарды С және D әріптерімен белгілесек, жол схемасы А, В, С, D төбелерден және АС, ВС, АС, ..., СD қырлардан құралған граф болып шығады. АС және ВС қырлары екі еселі болады. Эйлер бұл жағдайға сәйкес келетін мультиграф тұрғызды. Бұл мультиграфта құрылық бөліктері граф төбелерімен, көпірлер арқылы өтетін жолдар граф қабырғаларымен кескінделді, ол 9-суретте келтірілген. Эйлер мұндай серуеннің болуы мүмкін еместігін көрсетті. Геометрия тілінде айтқанда, қай төбеден шықса да, граф бойынша жүріп отырып, ешбір қырдан екі рет өтпей, шыққан төбеге қайтып келуге болмайды. Келтірілген сұрақты графтар теориясында былайша тұжырымдайды. Берілген мультиграфта оның барлық қабырғаларын қамтитын цикл бар ма?

А

С - Кнайпхоф аралы - құрылық бөлігі

Прегал өзені

В

8-сурет

	А
С				D
	В

9-сурет, 8- суреттің граф түрінде кескінделуі

Байланысқан бағытталған мультиграфтың оның барлық қабырғаларын қамтитын циклдің бар болуын белгілеп, тұжырымдап дәлелдеген атақты механик, математик Л.Эйлер болды.

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

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

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

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

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

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

10-суреттерде эйлерлік емес және эйлерлік графтар көрсетілген.

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

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

10-сурет

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

11-сурет

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

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