Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану

Егер шекті жұп граф байланысты болса, онда (оның элементарлық циклдерінің саны бойынша және өзіне қиылысатын қыры бойынша) графтың барлық қырларын ұстайтын жай цикл болады. Бұл циклді Эйлер циклі деп атайды, ал оған иелі графты Эйлердің графы деп атайды. Жай циклдің әрбір төбесінде жұп дәреже болады. Онда төмендегі теорема дәлелденеді.

Теорема. Егер шекті байланысты граф Эйлердің графы болу үшін оның жұп болуы қажетті және жеткілікті.

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

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

Эйлердің бағытсыз графының Эйлердің циклі бойынша айналып шығуы графтың әрбір қырын айналып шығуына бағыттайды. Мұндай бағытауда Эйлердің графы тең дәрежелі болады. Енді тең дәрежелі граф берілсін. Бұрынғы пікірді қайталасақ (циклдердің орнына контурлар жөнінде айтсақ) онда әрбір тең дәрежелі графты қырлары бойынша қосарланып қилыспайтын элементарлық нұсқалардың қосындысы ретінде көрінуі мүмкін (онымен қоса шекті тең дәрежелі графта графтың барлық қырларын ұстайтын жай нұсқа болады). Басқа сөзбен айтқанда Эйлер теоремасы мынаны танытады: граф төбелерінің барлығының жұп болуы әрбір қыры бір рет жүретін графты айналып шыққанға қажетті және жеткілікті шарт болып табылады.

Эйлер теоремасынан қызықты салдар шығады.

Кез келген байланысты G графтағы әрбір қырды l=(V₁, V₂) екі еселейміз, сол төбелермен оның l’, l’’ еселік қырлар етеміз. Әрбір төбенің дәрежесі екіге өседі де, жұп болады. Алынған жұп G графта Эйлерлік цикл болады (егер l’, l’’ қырлары қарсы бағытталса, онда әрбір төбе тең дәрежелі Эйлерлік цикл болады).

Егер оны G₁ графтың жолы ретінде қарасақ, l’, l қырларын бір қыр етіп желімдесек, онда бірінші G графта бұл траектория (жай емес) әрбір қыры арқылы екі рет жүретін цикл болады (қарама-қарсы бағыт арқылы).

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