Графтар әдісі

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ М. Әуезов атындағы Оңтүстік Қазақстан университеті ЕТ ж\е БҚЕ кафедрасы Презентация

Тақырыбы: Графтар саны: цикломатикалық, хроматикалық, сыртқы және ішкі бірліктер.

Орындаған: Лесхан Ж.

Тобы: ИП-19-6к1

Қабылдаған: Ахметова С.

Шымкент 2021 ж

Жоспар:

Леонард Эйлер

Леонард Эйлер - швейцариялық математик, механик және физик. Базель университетін бітірген. Графтің әр бір қабырғасы бір рет кіретін циклді эйлер циклі деп аталады, ал осындай циклі бар графті эйлер граф деп аталады. Мұндай графтар түрін анықтау проблемасы Л. Эйлермен 1736 жылы шешілді. Эйлер теоремасы. Бұл ұғымдар 1736 жылы Эйлердің Кенигсберг көпірлері туралы жұмысында енгізілген.

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

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

Шекті байланысты ориентирленбеген мультиграф Эйлер графы болуы үшін бұл графта тақ дәрежелі төбенің болмауы қажетті және жеткілікті.

Дәлелдеу

Егер шекті ориентирленбеген граф G(X) әр түрлі бас нүкте және ақырғы нүкте -ге ие болса, онда ол Эйлер шынжыры деп аталады. Графта Эйлер шынжыры бар болуы үшін оның байланысты және x(i) және x(j) төбесінен басқа барлық төбелері жұп дәрежеге ие болуы керек. x(i) және x(j) төбесі тақ дәрежелі болуы керек, себебі x(i) төбеден бір рет артықша шығады, ал x(j) төбеге бір рет артықша кіреді. Жоғарыдағы шарттар Эйлер шынжырының бар болуының жеткілікті шарты.

x(i)

x(j)

Шекті байланысты ориентирленбеген G(X) графтың төбелері саны k-ға тең болып, әрбір төбе тақ дәрежелі болса, онда G(X) -ты қаптайтын қабырғалары бойынша қиылыспайтын шынжырлар саны k/2-ге тең.

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