Ойлерови пътища и обхождания



Дата15.01.2018
Размер27.48 Kb.
#47684

Ойлерови пътища и обхождания


Определение. Път, който минава по всеки ръб (насочен или ненасочен) на граф еднократно, се нарича ойлеров. Затвореният ойлеров път се нарича ойлеров цикъл.

Теорема 1. а) Нека за граф съществува незатворен ойлеров път. Тогава степените на двата края на този път са нечетни, а степените на всички остали върхове са четни.

б) Нека за граф съществува ойлеров цикъл. Тогава степените на всички върхове са четни.

2. В равнина са начертани няколко окръжности така, че от всяка от тези окръжности може да се премине към произволна от останалите окръжности, без прекъсване на линията. Докажете, че съществува затворен път, който минава по всяка от дъгите на всички окръжности точно по един път.

Лема 3. Ако степените на всички върхове на граф са четни, то той може да се представи като обединение на цикли така, че всеки ръб участва точно в един цикъл.

Теорема 4. Даден е свързан граф.
а) Ако степените на всички върхове са четни, то в него съществува ойлеров цикъл;
б) Ако степените на точно два върха са нечетни, то в него съществува ойлеров път с краища в нечетните върхове.

5. Докажете, че съществува ред от 37 цифри, различни от 0, такъв, че всеки две различни цифри, някъде в този ред, са една до друга.

Теорема 6. Ако за насочен свързан граф от всеки връх излизат толкова стрелки, колкото и влизат в съответния връх, то за този граф съществува ойлеров цикъл.

7. Докажете, че съществува редица от 82 цифри, в която може да се открият всички двуцифрени числа, които не са кратни на 10.

8*. Ключалката на една врата се кодира с 10 бутона на които са означени цифрите от 0 до 9. За да се отключи ключалката, трябва да се натиснат 4 бутона в точно определен ред (като всеки опит е независим от предходните). Докажете, че за да сме сигурни, че ключалката е отключена, е необходимо да натиснем не повече от 10003 бутона.

Други задачи


ОП1. Квадрат 44 е разделен на единични квадратчета (квадратчета със страна 1). Може ли получената мрежа, образувана от страните на единичните квадратчета да се представи като обединение на:

а) осем начупени линии с дължина 5;
б) пет начупени линии с дължина 8?

ОП2. В свързан граф всеки ръб е син или червен. От всеки връх излизат равен брой сини и червени ръбове. Докажете, че между всеки два върха съществува път, за който цветовете на ръбовете задължително се редуват.

ОП3. От парче тел с дължина 12дм трябва да се изработи модел на куб с ръб 1дм. На колко части най-малко трябва да се раздели парчето тел?

ОП4. Картата на един град изглежда като квадрат 33, като всеки от деветте по-малки квадрати на които е разделена картата изобразява квартал на града. Страната на всеки от малките квадрати изябразява улица с дължина 100м (включително и страните на квадраите по външния контур, контура на големия квадрат). Какъв най-малък път трябва да измине валяк, за да асфалтира всички улици на града?

ОП5. а) Върху разграфена на квадратчетаповърхност, по всеки хоризонтал и по всеки вертикал, са разположени по 4 или по 6 фигури. Винаги ли е възможно да вземем няколко фигури така, че по всеки хоризонтал и по всеки вертикал, да са разположени точно по две фигури.

б*) Същият въпрос, ако по всеки хоризонтал и по всеки вертикал, са разположени не по-малко от две фигури.

ОП6. В страната Центумия някои двойки градове са съединени с пътища така, че от всеки град излизат точно по 100 пътя. Сноп наричаме комплект от 10 пътя, излизащи от един град. Докажете, че всички пътища може да се разделят на няколко снопа.

Бургас, 9-10 класс, 25 июля 2016 г, www.ashap.info/Uroki/Bolgar/Burgas16/index.html






Сподели с приятели:




©obuch.info 2024
отнасят до администрацията

    Начална страница