Задачи, решаемые с помощью графов.

Задачи, решаемые с помощью графов.

Задача 1.

Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

Решение:

Итак, имеется 5 человек. Выберем пять произвольных точек плоскости, которые назовём по первой букве имени мужчины. Эти точки будут являться вершинами графа, а отрезки, соединяющие данные вершины, будут представлять собой рукопожатия, которые произвели между собой мужчины.

Если подсчитать число ребер графа, изображенного на рисунке, то это число будет равно количеству совершенных рукопожатий. Как видно, их 10.

Ответ: 10

Задача 2.

В одном дворе живут четыре друга. Вадим и шофер старше Сергея, Николай и слесарь занимаются боксом, электрик-младший из друзей. По вечерам Андрей и токарь играют в домино против Сергея и электрика.

Определите профессию каждого из друзей.

Решение:

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

Будем выделять два вида рёбер: красного и чёрного цвета. Красные рёбра будут обозначать, что данный человек не может иметь выбранную профессию, а чёрные рёбра будут означать, что это профессия данного человека. Если от одной вершины уже выходить три красных ребра, то четвёртое обязательно должно быть чёрным.

Итого, из графа получается, что Андрей-шофёр, Сергей-слесарь, Николай-электрик, Вадим-токарь.

Ответ: Андрей-шофёр, Сергей-слесарь, Николай-электрик, Вадим-токарь.

12 3 4 Следующая ⇒