Задачи, приводящие к графам

ГРАФЫ И ИХ ПРИМЕНЕНИЕ ПРИ РЕШЕНИИ ЗАДАЧ

Работу выполнили

ученицы 6 Б класса МОУ «Гимназия № 4»

Машурова Александра, Сазанова Анна

Учитель Еремеева Марина Леонидовна

Задачи, приводящие к графам

1. Женя, Дима, Максим и Але­ша сыграли между собой по одной партии в шахматы. Сколько всего партий было сыграно?

Решение:

Женя сыграл партию с Димой, партию с Максимом и партию с Алешей - всего три партии. Дима также сыграл три партии - с Женей, Максимом и Алешей. Но партию Димы с Женей мы уже посчитали. Остается добавить одну партию, которую сыграли Максим с Алешей. Поэтому искомое число партий равно значению выражения 3+2+1.

Проще решить эту задачу с помощью рисунка.

 

Каждая линия обозначает сыгранную партию. Всего на схеме 6 линий, значит всего сыграно 6 партий.

 

2. Вася, Коля, Петя, Аня и Наташа - луч­шие лыжники в пятом классе. Для уча­стия в соревнованиях нужно выбрать из них одного мальчика и одну девоч­ку. Сколькими способами это можно сделать?

Решение:

Эту задачу можно решить с помощью следующей схемы.

Ответ: 6 способов.

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

На прощание эти ученые обменялись визитными карточками. Сколько карточек было передано из рук в руки?

Решение:

Ответ: 10 рукопожатий, 20 визитных карточек.

4. Как вы помните, охотник за мертвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке: Ма­нилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаим­ное расположение имений и проселочных дорог, соединяющих их (рис. 1.1). Установите, какое имение кому принадлежит, если ни по одной из дорог Чичиков не проезжал более одного раза.

Решение. По схеме видно, что путешествие Чичиков начал с имения Е, а кончил имением О. Замечаем, что в имения В и С ведут только по две дороги, поэтому по этим дорогам Чичиков дол­жен был проехать. Отметим их жирной линией. Опреде­лены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и AM Чичиков не ездил. Перечеркнем их (рис. 1.2К Отметим жирной линией ED; перечеркнем DK. Перечеркнем МО И МН отметим жирной линией МF; перечеркнем FO; отметим жирной линией FH, НК и КО. Найдем единственно возможный при данном условии маршрут.

Подведем первый итог: задача решена в ходе преобразования картинки. С рисунка остается только считать ответ: имение Е принадлежит Манилову, D — Коробочке, С — Ноздреву, А — Собакевичу, В — Плюшкину, М — Тентетникову, F — Бетрищеву, Н — Петуху, К — Констанжогло, О — Кошкареву.

 

 

Основные понятия теории графов

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

Точки иначе называют вершинами, отрезки — ребрами графа.

Вершины, которые не принадлежат ни одному ребру, называются изолированными.

На следующем рисунке одна изолированная вершина.

 

 

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

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

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

Вершина называется нечетной, если ее степень — число нечетное. Вершина называется четной, если ее степень — число четное.

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

Циклом называется путь, в котором совпадают его начальная и конечная вершины.

Длиной пути называется число ребер этого пути.

Длиной цикла называется число ребер в этом цикле.

Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.

Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.

 

 

В графе вершины А и В — связные, а вершины А и Н — несвязные.

Граф называется связным, если каждые две вершины его связные.

Граф называется несвязным, если хотя бы две вершины его не­связные.

Деревом называется всякий связный граф, не имеющий циклов.

 

Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке висячие вершины выдел закрашенными кружками).

Лесом называется несвязный граф, представляющий объединение деревьев.