Элементы теории графов

 

Рис.16

 

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

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

 

Рис.17

 

Проведем доказательство индукцией по числу ребер в G. В силу связности G, степень каждой вершины не меньше двух, а отсюда, по предыдущей лемме, заключаем, что граф G содержит цикл С. Если С проходит через каждое ребро графа G, то доказательство завершено; если нет, то, удаляя из G ребра, принадлежащие циклу С, получим новый (быть может, и несвязный) граф Н. Число ребер в Н меньше, чем в G, и любая вершина в Н по-прежнему имеет четную степень. Согласно индуктивному предположению, в каждой компоненте графа Н существует эйлерова цепь. В силу связности графа G, каждая компонента в Н имеет по крайней мере одну общую вершину с циклом С, поэтому искомую эйлерову цепь графа G можно получить так: идем по ребрам цикла С до тех пор, пока не встретим неизолированную вершину графа Н, затем следуем по эйлеровой цепи той компоненты в Н, которая содержит указанную вершину; далее продолжаем путь по ребрам цикла С, пока не встретим вершину, принадлежащую другой компоненте графа Н, и т.д.; заканчивается процесс тогда, когда мы попадаем обратно в начальную вершину (рис. 17).

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Примеры приложения теории графов в школьном курсе математики

2.1 Логические задачи

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

Условно их можно классифицировать, подразделив на несколько групп:

1. Задачи о мостах
2. Логические задачи
3. Задачи о «правильном» раскрашивании карт
4. Задачи на построение уникурсальных графов

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

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

Задача 1.  Из трех человек, стоящих рядом, один всегда говорит правду

(правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?

Решение: Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности (рис. 1).

Рис. 1

Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним, судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец".

Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция "дипломат", "лжец", "правдолюб" удовлетворяет задаче. Действительно, если "правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены.

 

Задача 2. В обеденный перерыв члены строительной бригады разговорились о том, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читает пять человек, и любая комбинация читается одним человеком. Сколько различных газет выписывают члены бригады? Сколько человек в бригаде?

Решение: Решение этой задачи достигается построением следующего графа (рис. 2), где каждая вершина обозначает соответствующую газету и

соответственно 5 подписчиков, а каждое ребро будет соответствовать одному

подписчику.

Рис. 2

Иными словами, суть метода решения этой и подобных ей задач состоит в

установлении связей между множеством вершин и множеством ребер графа.

Любая географическая карта является многоугольным графом, в котором страны  будут гранями, границы – ребрами, а окружающий страны Мировой океан – бесконечной гранью. Для лучшего зрительного восприятия необходимо, чтобы страны с общей границей были раскрашены в разные цвета. Такую карту называют "правильно" раскрашенной. Широко известное предположение состоит в том, что каждая карта может быть раскрашена с соблюдением требуемых условий при помощи четырех красок. Этому вопросу уделяется большое внимание в популярной литературе, и здесь мы не будем останавливаться на его рассмотрении. Задачи на проведение эйлеровых линий без повторений и без отрыва карандаша от бумаги являются одним из математических развлечений. При решении подобных

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

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

 

В учебнике Математика 6 класс [6,стр. 207,215,223,229]  представлен ряд задач решаемых с помощью графов.

№1220(1204) Решение некоторые математические задачи помогают специальные схемы, состоящие из точек и соединяющих их дуг или стрелок (рис. 3). Такие схемы называют графами, точки называют вершинами графа, а дуги – рёбрами графа.

Решить с помощью графов задачу:

а) В спортивном зале собрались Витя, Коля, Петя, Серёжа и Максим (рис. 3,а).

Оказалось, что каждый из мальчиков знаком только с двумя другими. Кто с кем знаком? (Ребро графа означает «мы знакомы».)

Б) Во дворе гуляют братья и сёстры одной семьи. Кто из этих детей мальчики, а кто девочки (рис. 3, б)? (Пунктирные рёбра означают «я - сестра», а сплошные «я брат».)

 

Рис. 3             а)                                                                 б)

Решение: а) Витя знаком с Колей и Серёжей, Серёжа знаком с Витей и Петей, Петя знаком с Серёжей и Максимом, Максим знаком с Колей и Петей, Коля знаком с Витей и Максимом.

б) А и В – сёстры, Б и Г – братья.

 

№1249(1233) Решите с помощью графа задачу: «Вера, Нина, Оля и Люба надели платья разных цветов (красное, синее, белое, голубое). На вопрос, кто из них в каком платье, три девочки ответили: 1) Оля – в синем, Люба – в белом; 2) Оля – в красном, Нина – в синем; 3) Вера – в синем, Люба – в голубом. В каждом ответе только одна часть верна, а остальные нет. Какого цвета платье одела каждая девочка? »

Решение: Все ответы девочек можно изобразить в виде графа (рис 4):

Рис.4

Предположим, что в пункте 1) утверждение «Оля – в синем» верно, тогда в пункте 2) утверждение «Оля – в красном» неверно и должно быть верным утверждение «Нина – в синем», но это будет противоречить нашему предположению из пункта 1) что «Оля – в синем» верно, значит, в пункте 1) верным является утверждение «Люба – в белом». Из пункта 3) следует, что утверждение «Вера – в синем» верно, а из пункта 2) следует, что верно утверждение «Оля – в красном». Для Нины остаётся один вариант: «Нина – в голубом».

 

№1303(1287) Решите помощью графа задачу: «Марина, Лариса, Жанна и Катя умеют играть на разных инструментах (пианино, виолончели, гитаре, скрипке), но каждая только на одном. Они же знают иностранные языки (английский, французский, немецкий, испанский), но каждая только один. Известно: 1) девушка, которая играет на гитаре, говорит по-испански; 2) Лариса не играет ни на скрипке, ни на виолончели и не знает английского языка; 3) Марина не играет ни на скрипке, ни на скрипке, ни на виолончели и не знает ни немецкого, ни английского языка; 4) девушка, которая говорит по-немецки, не играет на виолончели; 5) Жанна знает французский язык, но не играет на скрипке. Кто на каком инструменте играет и какой иностранный язык знает? »

Решение: Из условия 5) и 3) следует, что Марина говорит по-испански. Из условия 1) следует, что Марина играет на гитаре. Из условия 2) следует что Лариса играет на пианино и говорит по-немецки. Из 5) следует, что Жанна говорит по-французски и играет на виолончели. Для Кати остаётся один вариант: она говорит по-английски и играет на скрипке.

 

№1340(1324) Древнегреческая задача.

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

- Вот сколько, - ответил Пифагор, - половина изучает математику, четверть – природу, седьмая часть проводит время в размышлении, и, кроме того, есть ещё три женщины.

Решение: Изучают математику 1/2всех учеников Пифагора; изучают природу  1/4 всех учеников; проводят время в размышлении 1/7 всех учеников; все эти ученики вместе составляют: 1/2+1/4+1/7=14/28+7/28+4/28=25/28. Женщины составляют 1-(25/28)=3/28 всех учеников. Женщин было трое, значит, всего учеников у Пифагора  было:  3:(3/28)=(3*28)/3=28. Ответ: у Пифагора было 28 учеников.

 

 

 

 

 

Заключение

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

Важную роль на начальной стадии ознакомления с теорией графов играют:

- простота: многие её задачи, формулировки  и возможные пути решения понятны  даже школьникам начальных классов;

- большая наглядность многих теоретико-графовых конструкций;

- естественность приёмов доказательства;

- яркий прикладной характер.

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

 

 

 

Список использованных источников:

 

          Список печатных источников:

1. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1975г.
2. Березина Л. Графы и их применение. – М.: Просвещение, 1979г.
3. Берж К. Теория графов и ее применения. – М.: Изд-во иностр. лит., 1962г.
4. Зыков А. Основы теории графов. – М.: Наука, 1984г.
5. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977г.
6. Виленкин Н. Математика 6 класс. – М.: Мнемозина, 2010г.

 

     Список электронных ресурсов:

7. Сайт «Дискретная математика (электронный учебник)» (http://lvf2004.com)
8. В.Н. Бурков, Д.А. Новиков – Элементы   теории   графов (http://www.mtas.ru/start/t_garf.pdf)