Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану
жүктеу/скачать 1,12 Mb.
|
Лекция дискретка каз
- Бұл бет үшін навигация:
- Дәріс №11. Эйлер циклдары және шынжырлар
- 1.Жұп графтар
- 2.Эйлер графы
| Бақылау сұрақтары:
Байланысқан компоненттер дегеніміз не? Графта жолды іздеу қалай жүзеге асырылады? Қоспалы граф дегеніміз не? Дәріс №11. Эйлер циклдары және шынжырлар Дәріс мақсаты:Графтар теориясындағы классикалық Эйлер есебіментаныстыру. Кілттік сөздер:Эйлер графы,жұп графтар,Гамильтон графы,. Жоспары: 1.Жұп графтар 2.Эйлер графы 1.Жұп графтар Граф төбелерін ұстайтын байланыссыз граф бөлігін қарастырамыз.
0,1 коэффициенттер жиынының үстіне графтың барлық бөліктерінің жиыны сызықтық кеңістікті құрайды: кезкелген граф бөлігін H -ты бірге көбейткенде H -ты береді, ал H -ты нольге көбейткенде құр граф бөлігін қырларды ұстамайтын бөлігін береді және G графының бөлектенген төбелерінен тұрады. G графының бөліктерінің кеңістігі және оның граф бөліктерінің мінездемелік векторлардың кеңістігі изоморфты және оның өлшемі P болады. Граф бөліктерінің бір қырлық жиыны базис бола алады. Егер оның барлық төбелерінің дәрежесі жұп болса, ондай графты жұпграф дейміз.Кез келген элементарлық тізбек(циклден басқа)жұп графтытізбекке жатпайтын қырын ұзартсақ, онда тізбектің соңғы дәрежесі бір және гафта оның дәрежесі екіден кем еместігі шығады. Егер граф шекті ', '' болса, онда тізбекті ұзартсақ шекті реті арқылы біз екінші өтілген төбеге келеміз, алынған бөліктегі тізбек элементарлық циклді құрайды, шығарғаннан кейін жұп граф қалады, себебі барлық дәрежелер жұп санға өзгереді (екі циклдің төбелері үшін және 0 циклге жатпайтын төбелер үшін). 2.Эйлер графы Графта ешбір қыр қалғанша бұл графтың кейбір элементарлық циклге қайта бөлінуі мүмкін. Сонымен, әрбір шекті жұп циклды екені шығады. Егер шекті жұп граф байланысты болса, онда (оның элементарлық циклдерінің саны бойынша және өзіне қиылысатын қыры бойынша) графтың барлық қырларын ұстайтын жай цикл болады. Бұл циклді Эйлерциклі деп атайды,ал оған иелі графты Эйлердің графы деп атайды. Жай циклдің әрбір төбесінде жұп дәреже болады. Онда төмендегі теорема дәлелденеді. Теорема.Егер шекті байланысты граф Эйлердің графы болу үшіноның жұп болуы қажетті және жеткілікті. Эйлер графының байланысты барлық компоненті шектелген байланыспайтын жұп графында болады. Егер төбеге кіретін доғалардың саны шығатын доғалардың санына тең болса , онда бағытты графтың төбесін тең дәрежелі деп аталады. Егер графтың барлық төбелері тең дәрежелі болса, онда оны теңдәрежелі граф деп атайды. Эйлердің бағытсыз графының Эйлердің циклі бойынша айналып шығуы графтың әрбір қырын айналып шығуына бағыттайды. Мұндай бағытауда Эйлердің графы тең дәрежелі болады. Енді тең дәрежелі граф берілсін. Бұрынғы пікірді қайталасақ (циклдердің орнына контурлар жөнінде айтсақ) онда әрбір тең дәрежелі графты қырлары бойынша қосарланып қилыспайтын элементарлық нұсқалардың қосындысы ретінде көрінуі мүмкін (онымен қоса шекті тең дәрежелі графта графтың барлық қырларын ұстайтын жай нұсқа болады). Басқа сөзбен айтқанда Эйлер теоремасы мынаны танытады: граф төбелерінің барлығының жұп болуы әрбір қыры бір рет жүретін графты айналып шыққанға қажетті және жеткілікті шарт болып табылады. Эйлер теоремасынан қызықты салдар шығады. Кезкелген байланысты G графтағы әрбір қырды (V1,V2)екі еселейміз, сол төбелермен оның ','' еселік қырлар етеміз. Әрбір төбенің дәрежесі екіге өседі де, жұп болады. Алынған жұп G графта Эйлерлік цикл болады (егер ','' қыралары қарсы бағытталса, онда әрбір төбе тең дәрежелі Эйлерлік цикл болады). Егер оны G1 графтың жолы ретінде қарасақ, қырларын бір қыр етіп желімдесек, онда бірінші G графта бұл траектория (жай емес) әрбір қыры арқылы екі рет жүретін цикл болады (қарама-қарсы бағыт арқылы). Сонымен, әрбір байланысты графтың әрбір қыры екі рет ұстайтын цикл болады, шытырмадағы айналып шығуды бастапқы айналуға қайта келумен түсіндіруге болады. жүктеу/скачать 1,12 Mb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||