Лабораторная работа 6. Задачи на графы
Цель работы: рассмотреть решение задач с использованием «Граф», проверить выполнение «Графов» на родословных.
Задача 1.
Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?
Решение.
Каждого из этой компании изобразим на рисунке кружком. Если двое знакомы, соединим соответствующие кружки отрезком. Оказывается, что такие ситуации не только возможны, но все их можно описать аналогичными схемами (рис. 2.1). Из рассматриваемой компании нельзя выделить ни «четырехугольник», ни «треугольник», поскольку тогда из оставшихся нельзя будет составить компанию, удовлетворяющую условию, т. е. схема знакомства единственная.
Всякую схему, напоминающую многоугольник, принято называть циклом. (Древние греки «цикл» называли «колесом»; и действительно, на рисунке 2.2 изображено нечто, напоминающее колесо и с успехом заменяющее в рассматриваемой ситуации многоугольник.)
Что общего у схем, которые помогли нам решить задачи? Все они состоят из точек (кружков) и отрезков, соединяющих пары точек. Рассмотрение таких схем и приводит к понятию графа.
Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек.
Дата добавления: 2016-01-06; просмотров: 28; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!