Рішення задач за допомогою графа
Теорія графів застосовується при вирішенні задач з багатьох предметних областей: математика, біологія, інформатика
Мені подобається Проект подобається 20 учасникам
1736 рік, г.Кёнігсберг. Через місто протікає річка Прегеля. У місті - сім мостів, розташованих так, як показано на малюнку вище. З давніх часів жителі Кенігсберга билися над загадкою: чи можна пройти по всіх мостах, пройшовши по кожному тільки один раз? Це завдання вирішували і теоретично, на папері, і на практиці, на прогулянках - проходячи по цим самим мостам. Нікому не вдавалося довести, що це нездійсненно, але і зробити таку «загадкову» прогулянку по мостам ніхто не міг.
Розв'язати проблему вдалося знаменитому математику Леонарда Ейлера. Причому, він вирішив не тільки цю конкретну задачу, але придумав загальний метод вирішення подібних завдань. При вирішенні задачі про Кенигсбергских мостах Ейлер поступив таким чином: він "стиснув" сушу в точки, а мости "витягнув" в лінії. Таку фігуру, що складається з точок і ліній, що пов'язують ці точки, називають ГРАФОМ.
Граф - це сукупність непорожньої безлічі вершин і зв'язків між вершинами. Гуртки називаються вершинами графа, лінії зі стрілками - дугами, без стрілок - ребрами.
1.Оріентірованний граф (коротко орграф) - ребрах якого присвоєно напрямок.
2.Неоріентірованний граф - це граф. в якому немає направлення ліній.
3. Зважений граф - дуги або ребра мають вагу (додаткова інформація).
Рішення задач за допомогою графів:
Рішення: Позначимо вчених вершинами графа і проведемо від кожної вершини лінії до чотирьох інших вершин. Отримуємо 10 ліній, які і будуть вважатися рукостисканнями.
На пришкільній ділянці ростуть 8 дерев: яблуня, тополя, береза, горобина, дуб, клен, модрина і сосна. Горобина вище модрини, яблуня вище клена, дуб нижче берези, але вище сосни, сосна вище горобини, береза нижче тополі, а модрина вище яблуні. Розмістіть дерева від найнижчого до найвищого.
Вершини графа - це дерева, позначений першою літерою назви дерева. У даній завдання два відносини: "бути нижче" і "бути вище". Розглянемо відношення "бути нижче" і проведемо стрілки від нижчого дерева до більш високого. Якщо в задачі сказано, що горобина вище модрини, то стрілку ставимо від модрини до горобини і т.д. Отримуємо граф, на якому видно, що найнижче дерево - клен, потім йдуть яблуня, модрина, горобина, сосна, дуб, береза і тополя.
У Наташі є 2 конверта: звичайний і авіа, і 3 марки: прямокутна, квадратна і трикутна. Скількома способами Наташа може вибрати конверт і марку, щоб відправити лист?
Нижче представлений розбір завдань.
