Введение. Применение теории графов при решении логических задач

Применение теории графов при решении логических задач

Введение

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

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

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

Предметом исследования в данной работе является решение логических задач при помощи графов.

Цель исследования: применить графовый аппарат для решения логических задач.

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

Задачи исследования:

1. рассмотреть решение задач при помощи графов;

2. научиться переводить задачи на язык графов;

3. сравнить традиционные методы решения задач с методами теории графов.

В 1736 году великий математик Леонард Эйлер нашел решение головоломки, носящей название «Проблема кёнигсбергских мостов». Река Прегель, протекающая через Калининград (прежде город назывался Кенигсбергом) омывает два острова (рис. 1). Берега реки с островами были во времена Эйлера связаны мостами так, как это показано на рисунке. В головоломке требовалось найти маршрут, проходящий по всем четырем участкам суши по одному разу, а конец и начало пути должны совпадать.

Рисунок 1

Л. Эйлер доказал, что маршрута, который бы отвечал условиям головоломки, не существует, и разработал теорию решения такого рода головоломок. Владея материалом вводной части курса «Знакомство с графами», нетрудно воспроизвести идею рассуждения Л. Эйлера. Для этого нужно предварительно заменить рисунок 1 схемой, приведенной на рисунке 2, где острова и берега изображаются точками.

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

Спустя сто с лишним лет, в 1874 году немецкий ученый Г. Кирхгоф разработал эффективную методику определения значения силы тока в электрической цепи, используя методы и понятия, получившие позднее права гражданства в теории графов. Еще 10 лет спустя английский математик А. Кели (мать его была русской, он владел русским языком и следил за русской математической литературой; он оказался среди тех немногих математиков, которые с самого начала поняли и поддержали идеи Н.И. Лобачевского) разработал теорию деревьев для подсчета числа изомеров насыщенных углеводородов с данным числом n атомов углерода.

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

Графом называется множество точек, изображенных на плоскости (листе бумаги, доске), некоторые пары из которых соединены линиями. Точки называются вершинами графа, линии – ребрами. Степенью вершины называется число ребер, выходящих из вершины.

При взгляде на географическую карту сразу бросается в глаза сеть железных дорог. Это типичный граф: кружочки обозначают станции-вершины графа, а соединяющие их пути-ребра.

Граф на рис.3 изображает схему дорог между селами М, А, Б, В и Г. Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развести письма в остальные четыре села. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф, на котором легко увидеть возможные маршруты. Вершина М вверху- начало маршрутов. Из нее можно начать путь четырьмя различными способами: в А, в Б, в В или в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4×3×2×1 = 24 способа.

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

Рассмотрим одну из простейших задач: «Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?»

Обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, а пунктирная, что не лежит. Тогда с учетом задачи имеем G₁ (рис.4).

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

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

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

Рассмотрим примеры использования графов при решении некоторых известных задач. При этом объекты будем изображать точками, а отношения между ними – отрезками (положения точек и длины отрезков произвольны).

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

Задача 1. Беседуют трое друзей: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас белокурый, другой брюнет, третий рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос имеет каждый из друзей?

Приведем подробное решение. Построим граф отношения, заданного в условии задачи. Для этого, прежде всего, выделим множество фамилий М и множество цветов волос К, элементы которых будем обозначать точками. Точки множества М назовем буквами Б, Ч, Р (Белокуров, Чернов и Рыжов); точки второго множества – б, бр, р (белокурый, брюнет, рыжий). Если точке из одного множества соответствует точка из другого, мы их соединим сплошной линией, а если не соответствует – штриховой. Условие задачи указывает лишь на несоответствия, поэтому вначале должен возникнуть граф, изображенный на рисунке 5.

Рисунок 5

Из условия задачи следует, что для каждой точки из множества М существует одна и только одна тонка из множеств К, которая соответствует первой и, наобо­рот, каждой точке из множества К соответствует одна и только одна точка из множества М. Задача сводится к тому, чтобы найти это единственно возможное соответствие междуэлементами множеств М и К, т. е. к нахождению трех сплошных линий, соединяющих со­ответствующие точки множеств.

Принцип решения задачи прост. Если какая-то точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с его третьей точкой ее необходимо соединить сплошной линией. Поэтому граф на рисунке 5 дополняется сплошными линиями, соединяющими точки Б и р, Р и бр (рис. 6).

Рисунок 6

Далее остается соединить сплошной линией точку Ч и точку б, так как точка Ч соединена с точкой бр штриховой ли­нией, а точка р уже «занята» (рис. 7).

Рисунок 7

Таким образом, на графе этого рисунка автоматически прочитываем ответ: Белокуров — рыжий, Чернов — белокурый, Ры­жов – брюнет. Таким же приемом решаются, например, задачи 2 и 3.

Задача 2. Для Вани, Коли и Миши испечены пи­роги: один с капустой, другой с рисом, третий – с яблоками. Миша не любит пирог с яблоками и не ест с капустой. Ваня не любит пирог с капустой. Кто какой пирог ест?

Задача 3. На одном заводе работают три друга: слесарь, токарь и сварщик. Их фамилии Борисов, Ива­нов и Семенов. У слесаря нет ни братьев, ни сестер, он самый младший из друзей. Семенов, женатый на сестре Борисова, старше токаря. Назовите фамилии сле­саря, токаря и сварщика.

Приведенные задачи можно успешно решать и с ис­пользованием таблиц. Такой способ или его модифика­ции рекомендуется и разбирается во многих научно-по­пулярных книгах и педагогических пособиях. Можно, однако, указать классы задач, в которых применение графов, изображенных точками и отрезками, оказывает­ся более удобным и оправданным. Использование же в решениях метода таблиц типа турнирных таблиц или их обобщений вынуждает важную часть рассуждений проводить «устно». При этом неоднократно приходится возвращаться к условию задачи, к промежуточным ре­зультатам, многое помнить и в нужный момент поль­зоваться полученной информацией. К такому типу задач относятся задачи с тремя или большим числом множеств рассматриваемых объектов.

Задача 4. Три товарища – Иван, Дмитрий и Степан – преподают различные предметы (химию, биологию, физику) в школах Москвы, Ленинграда и Киева. Известно:

1. Иван работает не в Москве, а Дмитрий не в Ленинграде;

2. Москвич преподает не физику;

3. Тот, кто работает в Ленинграде, преподает химию;

4. Дмитрий преподает не биологию.

Какой предмет и в каком городе преподает каждый из товарищей?

Решение. Выделим три множества: множество имен, множество предметов и множество городов. Эле­мент каждого из множеств на рисунке 4 задан своей точкой (буквы на этом рисунке — первые буквы соот­ветствующих слов). Если две точки из разных множеств характеризуют признаки разных людей, то будем сое­динять такие точки штриховой линией. Если же две точки из разных множеств соответствуют признакам одного человека, то такие точки будем соединять попар­но сплошными линиями. Существенно, что по условию задачи для каждой точки любого множества в каждом из остальных множеств найдется одна и только одна точка, ей соответствующая.

Рисунок 8

Таким образом, граф на рисунке 8 содержит все заданные в условии элементы множеств и отношения между ними. Задача на языке графов сводится к нахождению трех «сплошных» тре­угольников с вершинами в разных множествах.

Рассмотрим граф на рисунке 8. Напрашивается штри­ховой отрезок ХД, Действительно, Л соответствует X и, одновременно, Л не соответствует Д, т. е. X не может соответствовать Д. Итак, используется типичная для такого рода задач операция на графе: если у тре­угольника с вершинами в трех разных множествах одна сторона сплошная, вторая — штриховая, то третья должна быть штриховой. Из условия задачи следует равномерность еще одной операции на графе: если какая-то точка соединена штриховыми отрезками с двумя точками во втором множестве, то ее следует со­единить с третьей точкой этого множества сплош­ным отрезком. Так проводится сплошной отрезок ДФ. Далее проводится штриховой отрезок ДМ (в тре­угольнике ДФМ сторона ДФ сплошная, а ФМ — штри­ховая), ДК сплошным (ДМ и ДЛ штриховые), Теперь соединим точки Ф и К сплошным отрезком. Если в треугольнике с вершинами в разных множествах две стороны сплошные, то третья тоже будет сплошной. Найден первый «сплошной» треугольник ДФК. Так, не возвращаясь к тексту задачи, руководствуясь лишь естественными операциями на графе, описанными выше, мы находим решение (рис. 9).

Рисунок 9

Отметим последователь­ность, в которой проводились отрезки: ХД, ДФ, ДМ, ДК, ФК, МС, ИЛ, ХИ, БМ, БС. Вершины каждого из трех полученных «сплошных» треугольников определяют ответ задачи: Иван преподает химию в Ленинграде, Дмитрий — физику в Киеве и Степан — биологию в Москве.

В следующей задаче применение графов помогает обнаружить наличие двух решений.

Задача 5. Маша, Лида, Женя и Катя умеют играть на разных инструментах (виолончели, рояле, гитаре и скрипке], но каждая только на одном. Они же владеют разными иностранными языками (английским, француз­ским, немецким и испанским), но каждая только одним. Известно:

1. девушка, которая играет на гитаре, говорит по-испански;

2. Лида не играет ни на скрипке, ни на виолончели и не знает английского языка;

3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка;

4. девушка, которая говорит по-немецки, не играет на виолончели;

5. Женя знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Условию задачи соответствует граф, изображенный на рисунке 10.

Рисунок 10

Обозначения и принцип решения здесь такие же, как и в задаче 4. Проведем последовательно следующие сплошные отрезки: КС, ВЖ, ВФ, АК (рис.11).

Рисунок 11

Тем самым образуются два «сплошных» треугольника ЖВФ и КСА. Проводим еще сплошной отрезок РН. Теперь убеждаемся, что условия задачи не обеспечи­вают однозначности выбора третьей точки для каждой из пар РН и ГИ. Возможны следующие варианты «сплошных» треугольников: МГИ и ЛРН или ЛГИ и МРН. Таким образом, задача имеет два решения.

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

Задача 6. В шахматном турнире принимали уча­стие 6 партнеров разных профессий: токарь, слесарь, инженер, учитель, врач и шофер. Известно:

1. в первом туре Андреев играл с врачом, учитель с Борисовым, а Григорьев с Евдокимовым;

2. во втором туре Дмитриев играл с токарем, а врач с Борисовым;

3. в третьем туре Евдокимов играл с инженером;

4. по окончании турнира места распределились так — Борисов I место, Григорьев и инженер поделили II и III места, Дмитриев занял IV Место, а Золотарев и слесарь поделили пятое и шестое места.

Какие профессии имели Григорьев, Дмитриев и Евдо­кимов?

Сохраняя прежние приемы в обозначениях и подхо­дах к решению задачи, для каждого из пунктов усло­вия 1, 2, 3, 4 построим свой граф (рис. 12).

Рисунок 12

Можно построить и общий для всех условий граф (рис. 13).

Рисунок 13

На последнем графе независимо друг от друга можно провести три сплошных отрезка ИА, ВЗ и БШ, что и свидетельствует об избыточности условия задачи. Для того, чтобы получить ответ задачи, проводим сплошные отрезки ГТ, ДУ и ЕС.

Во всех рассмотренных задачах точки и отрезки как бы берут на себя труд думать за нас. Решение задач с помощью графов можно сравнивать с решением за­дач методом уравнений: после составления уравнения мы забываем на время условие задачи и действуем «механически» по правилам решения уравнений. Эта особенность метода сохраняется при рассмотрении и других логических задач, которые предусматривают ана­лиз нескольких возможностей. Приведем пример.

Задача 7. Четыре спортсменки Аня, Валя, Галя и Даша заняли первые четыре места в соревнованиях по гимнастике, причем никакие две из них не делили меж­ду собой эти места. На вопрос, какое место заняла каждая из них, трое болельщиков высказали предполо­жения:

1. Аня — II место, Даша — III место;

2. Аня — I место, Валя — II место;

3. Галя — II место, Даша — IV место.

Оказалось, что каждый болельщик один раз ошибся, а другой раз указал правильно. Какое место заняли каждая из спортсменок?

Решение. На рисунке 14 точки «верхнего» мно­жества соответствуют именам спортсменок, а «нижнего» — занятым местам.

Рисунок 14

Сплошные отрезки соответствуют предположениям первого болельщика, штриховые — вто­рого, штрих пунктирные — третьего.

Предположим, например, что Валя заняла II место, тогда неверными должны быть высказывания; «Аня за­няла I место», «Аня заняла II место», «Галя заняла II место». Отрезки, соответствующие ложному высказы­ванию, будем перечеркивать (рис. 15).

Рисунок 15

В таком случае Даша займет III и IV места, что по условию задачи невозможно. Следовательно, предположение, что Валя заняла II место, неверно; верным будет высказывание

«Аня заняла I место» (рис. 16). Но тогда зачеркиваем отрезки АН и ВП, оставляя ДIII. Далее зачеркнем от­резок ДIV.

Рисунок 16

Итак, Аня заняла I место, Даша — III, Галя —II, Валя —IV.

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

Задача 8. При составлении расписания уроков на понедельник трое преподавателей высказали пожелания, чтобы их уроки были:

по математике = первый или второй; ^:

по истории — первый или третий;

по литературе — второй или третий.

Сколькими способами и как при составлении распи­сания можно удовлетворить пожелания всех препода­вателей?

Задача 9. В велогонках приняли участие пять школьников. После гонок четыре болельщика заявили:

1. Сережа занял II место, а Коля— III;

2. Надя заняла III место, а Толя — V;

3. Толя занял I место, а Надя — II;

4. Сережа занял II место, а Ваня — IV.

Зная, что одно из показаний каждого болельщика верное, а другое — ложное, найти правильное распределение мест.

Наглядная форма графов (метод становится еще нагляднее, если вместо различных линий одного цвета, использовать линии разных цветов) позволяет быстро и без затруднений разобраться в достаточно запутанных ситуациях.

Выводы

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

На помощь приходят графы. Выделяя из словесных рассуждений главное — объекты и отношения между ними, графы представляют изучаемые факты в наглядной форме. Приемы решения логических задач с использованием графов подкупают своей естественностью и простотой, избавляют от.лишних рассуждений, во многих случаях сокращают нагрузку на память. С одной стороны, графы помогают проследить все логические возможности изучаемой ситуации, с другой, благодаря своей обозримости, помогают тут же, в ходе решения задачи, классифицировать логические возможности, отбрасывать неподходящие случаи, не доводя до полного перебора всех случаев. Что подтверждает нашу гипотезу.

Список литературы

1. В.А. Гусев, А.И. Орлов, А.Л. Розенталь. Внеклассная работа по математике в 6-8 классах. М.: Просвещение, 1977

2. Ж. Математика в школе, №4, 2004.

3. Н.С. Новиков. Дискретная математика. СПб.: Питер, 2001.

4. Энциклопедический словарь юного математика. М.: Педагогика, 1989г.