вулиць частині міста зображеної на малюнку. Чи може він закінчити свою роботу на тому перехресті, де знаходиться гараж, якщо по кожній вулиці своєї ділянки міста водій буде проїжджати тільки один раз?
3.22. У марсіанському метро 100 станцій. Від будь-якій станції до будь Інший можна проїхати. Страйковий комітет хоче закрити проїзд через одну зі станцій так, щоб між усіма іншими станціями був можливий проїзд. Доведіть, що така станція знайдеться. p> 3.23. У тридев'ятому царстві кожні два міста з'єднані дорогий з одностороннім рухом. Доведіть, що існує місто, з якого в будь-який інший можна проїхати не більш ніж по двох дорогах.
3.24. У місті на кожному перехресті сходиться парне число вулиць. Відомо, що з будь-якої вулиці міста можна проїхати на будь-яку іншу. Доведіть, що всі вулиці міста можна об'їхати, побувавши на кожній по одному разу.
Різні завдання на графи.
3.25. У кутах шахівниці 3х3 коштують 4 коня: 2 білих (у сусідніх кутах) і два чорних. Чи можна за кілька ходів (по шаховими правилами) поставити коней так, щоб у всіх сусідніх кутах стояли коні різного кольору?
Рішення.
Зазначимо центри клітин дошки і з'єднаємо відрізками пари відмічених точок, якщо з однієї в іншу можна пройти ходом коня. Ми отримаємо граф, що містить В«циклВ» з восьми точок і одну ізольовану точку (рис. 24). Переміщення коней по дошці відповідає руху по ребрах цього циклу. Ясно, що при русі по циклу не можна змінити порядок проходження коней.
3.26. Випишіть в ряд цифри від 1 до 9 так, щоб число, складене з двох сусідніх цифр, поділялося або на 7, або на 13.
Рішення.
Напишемо цифри на аркуші. З'єднаємо стрілками ті цифри, які можуть слідувати один за одним (Рис. 25). Тепер ясно, що першою йде 7, потім 8 і 4. Оскільки 8 вже використана, то стрілки, що йдуть до неї, треба прибрати. Після 4 йде 9, оскільки до дев'ятці іншого шляху немає. Далі йде 1 і так далі. p> Відповідь: 784913526.
3.27. У шкільному турнірі в одне коло грають шість шахістів: Олександр, Боря, Вітя, Гриша, Діма і Костя. Щодня гралися три партії, і весь турнір закінчився в п'ять днів. У перший день Боря грав з Альошею, а в другій - з Костею. Вітя в четвертий день грав з Костею, а в п'ятий з Дімою. Хто з ким грав в кожен день турніру? p> Рішення.
Позначимо шахістів відповідно точками А, Б, В, Г, Д і К, а зіграні ними партії - відрізками, що з'єднують ці точки. p> Точки краще розташовувати так, щоб при послідовному їх з'єднанні вони стали вершинами правильного шестикутника.
1) Перший день турніру. За умові у цей день Боря грав з Альошею. З ким грав Вітя? Тільки з Гришею, так як з Дімою та Костею він грав в інші дні. Отже, третю партію в перший день грали Діма з Костею. Побудуємо відповідний граф (рис. 26). p> 2) Другий день турніру. У Цього дня Бо...
