Задачи, решаемые с помощью графов. 1. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только двумя другими. Возможна ли такая компания? Ответ: Возможна.

Задачи, решаемые с помощью графов. 2. В школьной столовой на первое можно заказать щи, гороховый суп или борщ, на второе – котлету или рыбу, а на третье – чай или морс. Сколько вариантов обеда можно получить из указанных блюд? Ответ: 12 вариантов. 1-е блюдо 2-е блюдо 3-е блюдо борщ щи суп к к к р р р м м м м м м ч ч ч ч ч ч

Задачи, решаемые с помощью графов. 3. Володя решил навестить своих друзей: Петра, Константина и Игоря. Ему обязательно нужно побывать у каждого из своих друзей и вернуться домой. Если он к кому-то не зайдет, то его друг обидится. Помогите ему выбрать кратчайший путь, если известно, как расположены дома друзей и на каком расстоянии они находятся друг от друга. Петр Володя Игорь Константин В – И =30 В – П = 40 И – К = 45 К – П = 50 В – К = 60 И – П = 55

Задачи, решаемые с помощью графов. 3. П В И К В В В В И В В В И И И И П П П П П К КК К К В – К – П – И – В = = 195 В – К – И – П – В = = 200 В – И – К – П – В = = 165 Ответ: Самый короткий путь Володи: В – И – К – П – В =165

4. Как вы помните, охотник за мёртвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетищева, Петуха, Констанжогло, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни по одной из дорог Чичиков не проезжал более одного раза. Задачи для самостоятельной работы O A B C DK E F H M

Проверь себя O A B C DK E F H M По схеме видно, что путешествие Чичиков начал из имения E, а кончил в имении О. Замечаем, что в имения В и С ведут только по две дороги, поэтому по этим дорогам Чичиков должен был проехать. Через А проходят дороги АВ и АС. По дорогам АЕ, АМ и АК Чичиков не ездил. Отметим ED и перечеркнем DK. Анализируем схему. 8.

Проверь себя B O A C DK E F H M 4. Задача решена в ходе преобразования картинки. Остается только считать ответ: имение Е принадлежит Манилову, D – Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F – Бетрищеву, H – Петуху, К – Констанжогло, О – Кошкареву.

1) Изобразите с помощью графа договорные отношения между предприятиями А, Б, В, Г, Д, Е, если к рассматриваемому моменту: предприятие А установило договорные отношения со всеми другими предприятиями; Б установило с Г и Д; В установило со всеми предприятиями, кроме предприятия Е. Сколько вершин и сколько ребер имеет полученный граф?

2) Среди шести стран установлены экономические отношения, причем каждая страна имеет экономические договоры с каждой другой страной. Изобразите в виде графа результат установленных экономических отношений. Сколько ребер имеет полученный граф? 3) Сколько ребер нужно провести чтобы достроить граф, изображенный на рисунке до полного?