Geum.ru

Задачи на делимость чисел в егэ 17 Разностные уравнения 18

Вид материалаРеферат

Содержание


Теория графов
Графы и их применение к решению задач
А и 7 городов, в которые можно добраться из А.
Подобный материал:
1   2   3   4   5   6   7   8   9   ...   15
^

Теория графов


Е.О. Басмаджян
Руководитель: Г.А. Борисова
учитель математики первой категории
МОУ лицей № 12

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

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

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

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

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

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

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

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

Задача 2. В магазине "Все для чая'' есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?

Чтобы задача была понятнее и доступнее в решении я применила теорию графов.

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

Литература

  1. Берж, К. Теория графов и ее приложения [Текст] / К. Берж . – М. : ИЛ, 1962. – 320 c.
  2. Зыков, А. А. Основы теории графов [Текст] / А. А. Зыков – М. : «Вузовская книга», 2004. – 664 С.
  3. Оре, О. Теория графов [Текст] / О. Оре. – М. : Наука, 1980. – 336 с.
  4. Уилсон, Р. Введение в теорию графов [Текст] / Р. Уилсон ; пер с англ. – М. : Мир, 1977. – 208 с.
  5. Харари, Ф. Теория графов [Текст] / Ф. Харари. – М. : Мир, 1973.
^

Графы и их применение к решению задач


О.И. Бородина
Руководитель: А.Р Нусратуллина.,
Учитель математики первой категории
МОУ Гимназия № 35

В школьной программе по математике термин «граф» отсутствует. При этом в различных областях математики, а также в компьютерных науках, в электронике, в экономике и других дисциплинах графы используются повсеместно. Теория графов – относительно молодая область математики (первая работа Леонарда Эйлера о Кёнигсбергских мостах, с которой началось развитие теории графов, была опубликована в 1736 году, а сам термин граф появился лишь спустя 200 лет). Его впервые использовал в 1936 году венгерский математик Денеш Кёниг. Но, несмотря на это, изложить все результаты, полученные математиками в этой области, невозможно даже в очень толстой книге.

Мы рассмотрели основные понятия и теоремы теории графов и применили их к решению задач.

Задача 1. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими? [1]

Представим этот граф с 15 вершинами. Подсчитаем количество ребер в этом графе (для этого надо 15 умножить на 5, разделить на 2, т.к. при подсчете каждое ребро учтено дважды). Если это число целое, данный граф построить можно. Таким образом, указанным способом телефоны соединить нельзя.

Задача 2. В государстве 15 городов, каждый из которых соединен дорогами не менее чем с семью другими. Докажите, что из любого города можно добраться в любой другой (возможно, проезжая через другие города). [1]

Рассмотрим произвольный город ^ А и 7 городов, в которые можно добраться из А. Всего мы рассмотрели 8 городов. Пусть какой-нибудь из оставшихся городов не соединен ни с каким из этих восьми городов. Тогда он соединен только с шестью городами, что противоречит условию.

Задача 3. В шахматном турнире по круговой системе, в которой каждый игрок должен встретиться с каждым, участвуют 6 школьников. Известно, что Ваня сыграл 5 партий, Толя – 4, Леша и Дима – по 3, Семен – 2, Женя – 1. С кем сыграл каждый из участников? [2]

Поставим в соответствие каждому игроку точку плоскости – вершину графа. Если два игрока встречались между собой, то будем соединять соответствующие вершины линией – ребром графа. Пусть вершина Ж соответствует Жене, вершина В – Ване, вершина Т – Толе, вершина С – Семену, вершина Л – Леше. Поскольку степень вершины В равна 5, то соединим эту вершину со всеми остальными вершинами графа. Из вершины Т должны выходить 4 ребра, а выходит пока одно. Соединим эту вершину ребрами с вершинами Л, Д и С, поскольку степень вершины Ж уже равна 1. Из вершин Л, Д и С выходит по два ребра, степень вершин Л и Д должна быть равной 3. Поэтому соединим эти вершины ребром. Построенный граф будет описывать встречи, проведенные детьми.

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

Литература

  1. Генкин, С.А. Ленинградские математические кружки [Текст] : пособие для внеклассной работы / С.А. Генкин, И.В. Итенберг, Д.В. Фомин. – Киров : Изд-во «АСА», 1994. – 272 с.
  2. Мельников, О. И. Обучение элементам теории графов в 4-6 классах [Текст] / О.И. Мельников, В.В. Куприянович. – Математика в школе. – 2004. – №4.– С.63-68