Конкурс «Новое в образовании» Номинация icon

Конкурс «Новое в образовании» Номинация



Смотрите также:
Врамках Форума проводится конкурс «Новое поколение»...
Конкурс «Учитель года-2012» (заочный тур) Номинация «Лидер в образовании»...
Конкурс «Учитель года -2011» Номинация «Лидер в образовании»...
Открытый конкурс общественных инициатив в области здоровьеформирующих и здоровьесберегающих...
Конкурса, конференций, состязаний, номинация, дата участия...
На всероссийский конкурс «Организация учебно-воспитательного процесса, научно-исследовательской...
Положение о ежегодном областном конкурсе «Информационные технологии в образовании»  Общие...
Районный конкурс «Лучший учитель 2009 года» -лауреат конкурса 2 Районный конкурс «Инновации в...
Детский творческий онлайн-конкурс «Интернешка» Январь 2011г....
Конкурс проходил по трем номинациям и двум возрастным категориям: а) номинация «Художественное...
Всероссийский конкурс на лучший молодёжный проект по экологической проблематике Номинация...
Окружной конкурс социальных и культурных проектов в рамках Года семьи в Российской Федерации...



скачать
2008 учебный год.


Конкурс «Новое в образовании»


Номинация: использования новых технологий.




Работа на тему:


«Метод проектов на уроках математики.

Проект «Графы»»


Автор- составитель: учитель математики

Леткинской средней школы

Сарайкина Антонина Николаевна


Содержание:

Предисловие.

Проект «Графы»

I. Введение.

II. Теория граф.

III. Графы Эйлера.

IV. Деревья.

V. Плоские графы

VI. Ориентированные графы.

VII. Биография Л.Эйлера.

VIII. Тестовые задания.

IX. Задачи для самостоятельной работы.

X. Заключение.


Литература:


1. В.А.Гусев, А.И. Орлов, А.Л.Розенталь. Внеклассная работа по математике. –Москва «Просвещение» 1984г.

2.Научно – методическая газета «Математика» - Приложение к газете 1 сентября –

№6, 2007г.

3. Физико-математический журнал «Квант», А. Савин, №6,1994г.

4.Проектная деятельность учащихся по математике. Автор – составитель М.В.Величко. – Волгоград: Учитель,2007г.


Предисловие.

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

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

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

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

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

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

- новых личностных качеств.

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

Организация и проведение макропроектов (долгосрочных) требует обоснованного и разумного подхода с учетом всех ранее выявленных замечании.

Проект требует тщательной подготовки, проведение его занимает 5-6 уроков, если это проект, рассчитанный на урочную деятельность. Причем защита проектов предусматривает, как правило, сдвоенный урок.

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


^ Проект: «Графы»

Тип проекта: долгосрочный, практико – ориентированный

Форма: внеурочная (групповые занятия)

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

^ Этапы проекта.


Учитель

Учащиеся

1

2

1-й этап - погружение

Формирует:

- проблемы проекта;

- цели;

- задачи:



Осуществляют:

личностное присвоение проблем;

вживание в ситуацию;

принятие, конкретизацию цели и задач




2-ой этап – организация деятельности

Организует деятельность-

предлагает:

организовать группы;

распределить амплуа в группах;

спланировать деятельность по решению задач проекта;

возможные формы презентации.

Осуществляют:

разбивку на группы;

распределение ролей в группе;

планирование работ;

выбор формы и способа презентации результатов.


3-й этап – осуществление деятельности.

Не участвует:

но консультирует;

ненавязчиво контролирует;

дает новые знания;

репетирует презентацию


Работают активно и самостоятельно:

каждый в соответствии со своей ролью и сообща;

консультируются по необходимости

подготавливают проекты результатов



4-й этап – презентация результатов

Принимает отчет:

обобщает и резюмирует полученные результаты;

подводит итоги проектов;

оценивает умение общаться, слушать, обосновывать мнение;

акцентирует внимание на воспитательном моменте,

умение работать в группах на общий


результат.

Демонстрируют:

понимание проблем, цели и задач;

умение планировать и осуществлять работу;

найденный способ решения проблем;

рефлексию деятельности и результата;

дают взаимооценку деятельности и ее результативности.




^ I. Введение.

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

в физике - при построении электрических схем, в химии и биологии – при изучении молекул их цепочек;

в географии – при составлении карт;

в истории – при составлении генеалогических древ (родословной);

в геометрии – чертежи многоугольников, многогранников, пространственных фигур;

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

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

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

9 класс. Каждый из четырех гномов – Вася, Миша, Саша и Слава – или всегда говорит правду, или всегда врет. Мы услышали такой их разговор: Вася (Мише): Ты лжец. Слава (Васе): Сам ты лжец. Саша (Славе): Так они же оба лжецы. (Подумав.) Впрочем, и ты тоже. Кто из гномов правдивый, а кто говорит неправду? Ответ обоснуйте.

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

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

^ II.Теория граф.

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

В математике определение графа дается так: графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.




Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)

Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)

Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)



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

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно

n(n-1)/2

Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2:
Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа .

Степени вершин и подсчет числа ребер.

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

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

рис.5

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.
На рисунке : Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1.

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

Доказательство:

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

Закономерность 2.

Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа. Доказательство:

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

ТЕОРЕМА

Число нечетных вершин любого графа четно. Доказательство:

Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как
K1 + 2К2 + ЗК3 + ...+ nКn.
С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство
K1 + 2К2 + ЗК3 + ... + nКn = 2R. (1)
Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 + ...):
K1 + 2К2 + ЗК3 + 4К4 + 5К5 + ... + nК = 2R,
(К1 + К3 + К5 +...) + (2K2 + 2Х3 +4K4 + 4К5 + ...)=2R
Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число.

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

Задача. Первенство класса. В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина с Андреем и Борисом; Дмитрий – с Виктором и Елена – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Обсуждение. Изобразим данные задачи в виде схемы. Участников будем изображать точками: Андрея – точкой А, Бориса – точкой Б и т.д. Если двое участников уже сыграли между собой, то будем соединять изображающие их точки отрезками. Получается схема, показанная на рисунке 1.




Точки А, Б, В, Г, Д, Е - вершины графа, соединяющие их отрезки – ребра графа.

Заметим, что точки пересечение ребер графа не являются его вершинами.

Число игр, проведенных к настоящему моменту, равно числу ребер, т.е. 7.

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

Чтобы найти число игр, которые надо провести, построим еще один граф с теми же вершинами, но ребрами будем соединять тех участников, которые еще не играли друг с другом (рис.2) Ребер у этого графа оказалось 8, значит, осталось провести 8 игр: Андрей – с Виктором и Дмитрием; Борис – С Виктором, Дмитрием и Еленой и т.д.

Попробуем построить граф для ситуации, описанной в следующей задаче:

Задача. Кто играет Ляпкина – Тяпкина? В школьном драмкружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина – Тяпкина.

- Ляпкиным – Тяпкиным буду я! – решительно заявил Гена.

- Нет, я буду Ляпкиным – Тяпкиным, возразил Дима.- С раннего детства мечтал воплотить этот образ на сцене.

- Ну, хорошо, уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.

- …А мне – Осипа, - не уступил ему в великодушии Дима.

- Хочу быть Земляникой или Городничим,- сказал Вова.

- Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, -

добавили они одновременно.

Удастся ли распределить роли так, чтобы исполнители были довольны?

Обсуждение. Изобразим юных актеров кружками верхнего ряда: А – Алик, Б – Борис, В – Вова, Г – Гена, Д – Дима, а роли, которые они собираются играть, - кружками второго ряда (1 – Ляпкин – Тяпкин, 2 – Хлестаков, 3 – Осип, 4 – Земляника, 5 – Городничий). Затем от каждого участника проведем отрезки, т.е. ребра, к ролям, которые он хотел бы сыграть. У нас получиться граф с десятью вершинами и десятью ребрами (рис.3)





Чтобы решить задачу, нужно из десяти выбрать пять ребер, не имеющих общих вершин. Сделать это легко. Достаточно заметить, что в вершины 3 и 4 ведут по одному ребру, из вершин Д и В соответственно. Это означает, что Осипа (вершина 3) должен играть Дима (кто же еще?), а Земляничку – Вова. Вершина1 – Ляпкин – Тяпкин – соединена ребрами с Г и Д. Ребро 1 – Д отдает, так как Дима уже занят, остается 1 – Г, Ляпкина – Тяпкина должен играть Гена. Остается соединить вершины А и Б с вершинами 2 и 5, соответствующими ролям Хлестакова и Городничего. Это можно сделать двумя способами: либо выбрать ребро А -5 и Б – 2, либо ребро А -2 и Б -5. В первом случае Алик будет играть Городничего, а Боря – Хлестакова, во втором случае наоборот. Как показывает граф, других решений задача не имеет.

Тот же граф получится при решении следующей задачи:

Задача. Сварливые соседи. Жители пяти домов поссорились друг с другом и, чтобы не встречаться у колодцев, решили поделить их (колодцы) так, чтобы хозяин каждого дома ходил к «своему» колодцу по «своей» тропинке. Удастся ли им это сделать?

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

^ III. Графы Эйлера.

Теория графов – наука сравнительно молодая: во времена Ньютона такой науки еще не существовало, хотя и были в ходу «генеалогические деревья», представ-ляющие собой разновидности графов. Первая работа по теории графов принадлежит Леонарду Эйлеру, и появилась она в 1736 году в публикациях петербургской Академии наук. Начиналась эта работа с рассмотрения следующей задачи:

а)Задача о кенигсбергских мостах. Город Кенигсберг (ныне Калининград) расположен на берегах и двух островах реки Прегель (Преголи).Различные части города были соединены семью мостами, как показано на рисунке. В воскресные дни горожане совершают прогулки по городу. Можно ли выбрать такой маршрут, чтобы пройти один и только один раз по каждому мосту и потом вернуться в начальную точку пути?


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

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

Фигура эта, такая простая на вид, оказывается, имеет интересную особенность. Если мы начнем движение из вершины В, то у нас это обязательно получится. А что будет, если мы начнем движение из вершины А? Легко убедиться, что обвести линию в этом случае нам не удается: у нас всегда будет оставаться не пройденные ребра, добраться до которых уже невозможно.




.

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

Графы, начерченные на рис.6 также можно начертить одним росчерком пера.



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

Вам это сделать не удалось! Почему? Вы не можете найти нужную вершину? Нет! Дело не в этом. Этот граф вообще нельзя вычертить одним росчерком пера.



Проведем рассуждения, которые убедят нас в этом. Рассмотрим узел А. Из него выходят три вершины. Начнем вычерчивать граф с этой вершины. Чтобы пройти по каждому из этих ребер, мы должны выйти из вершины А по одному из них, в какой – то момент обязательно вернуться в него по второму и выйти по третьему. А вот снова войти уже не сможем! Значит, если мы начнем вычерчивание с вершины А, то закончить в нем не сможем.

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

Итак, вершина А должен быть или началом, или конечным узлом вычерчивания.

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

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым (рис.6).

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность1. (вытекает из рассмотренной нами теоремы).
^ Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 2.

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

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

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

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

Граф называется несвязным, если это условие не выполняется.

рис.7рис.8

На рисунке 7, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным. (рис.8)
Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.

Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа.(рис.8)


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


ТЕОРЕМА.

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

Доказательство:

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

^ Вернемся теперь к задаче о кенигсбергских мостах.




Обсуждение задачи. Обозначим различные части города буквами А, В, С, Д, а мосты – буквами а, b, c, d, e, f, g – мосты, соединяющие соответствующие части города. В этой задаче существуют лишь переходы через мосты: переходя через любой мост, мы всегда из одной части города попадаем в другую, И, наоборот, переходя из одной части города в другую, мы непременно пройдем по мосту. Поэтому, изобразим план города в виде графа, вершины которого А, В, С, Д (рис.8) изображают отдельные части города, а ребра a, b, c, d, e, f, g – мосты, соединяющие соответствующие части города. Ребра зачастую оказываются удобнее изображать удобнее не прямолинейными отрезками, а криволинейными – «дугами».

Если бы существовал маршрут, удовлетворяющий условию задачи, то существовал бы замкнутый непрерывный обход этого графа, проходящий один раз по каждому ребру. Иными словами этот граф должен вычерчиваться одним росчерком. Но это невозможно – какую бы вершину мы ни выбрали за исходную, нам придется проходить через остальные вершины, и при этом каждому «входящему» ребру (мосту, по которому мы вошли в эту часть города) будет соответствовать «выходящее» ребро мост, которым мы и воспользуемся затем, чтобы покинуть эту часть города): число ребер, входящих в каждую вершину, будет равно числу ребер, выходящих из нее, т. е. общее число ребер, сходящихся в каждой вершине, должен быть четным. Наш граф этому условию не удовлетворяет, и поэтому требуемого маршрута не существует.

^ IV. Деревья.

Деревом называется любой связный граф, не имеющий циклов.
Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

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

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а). В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.

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

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

Висячей вершиной называется вершина, из которой выходит ребро.(рис.10)

рис.9а;б

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

Свойство 2.

Всякое ребро в дереве является мостом.
Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

рис.10 (кружком обведены висячие вершины)

Теорема.

Граф, в котором две любые вершины соединены ровно одним простым путём, является деревом.

Доказательство:

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


*Дерево – это граф, в котором две любые вершины соединены ровно одним простым путём.


ЛЕММА (о висячей вершине)

В каждом дереве есть висячая вершина.

Доказательство:

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

ТЕОРЕМА.

В дереве число вершин на одну больше числа ребер.

Доказательство:

Из условия теоремы граф – дерево. У него есть висячая вершина. Удалим её и выходящее из нее ребро. Оставшийся граф также дерево. У него есть висячая вершина, которую также удалим. Проделав эту операцию n-1 раз, получим граф, состоящий из одной вершины. Т. к. удалялось по одному ребру, то вначале их было n-1.


Использует графы и дворянство. На рисунке 11 приведена часть генеалогического дерева знаменитого дворянского рода- писателя Льва Николаевича Толстого. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.

^ V. Плоские графы.

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

Рассмотрим граф с пятью вершинами, попарно соединенными друг с другом (рис. 12). Здесь ребра графа пересекаются. Невозможно его изобразить так, чтобы пересечений не было, как невозможно выполнить намерения трех человек, описанных Льюсом Кэрроллом:

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

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

         

ТЕОРЕМА Понтрягина – Куратовского:

Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами (рис.12).(В основном используется старинных задач о домах и колодцах, суть которой сводится к выяснению вопроса — является ли рассматриваемый граф плоским или нет ( рис.13).

рис.13

^ VI. Ориентированные графы.

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





Тогда могут помочь сориентироваться в этой ситуации стрелки, расположенные, например, прямо на ребрах-улицах рассматриваемой схемы (графа) города.

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

Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих» из вершины).
^ Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих» в вершину).

рис.13


Так, на рисунке 13 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:
Ст.вх.А=2, Ст.вых.А=1
Ст.вх.В=2, Ст.вых.В=0
Ст.вх.Д=1, Ст.вых.Д=3

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

A1A2, A2A3, ..., Аn-1А в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.
На ниже приведенном рисунке показаны примеры путей в ориентированном графе. Причем, первые два пути— простые — ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым, т. к. через вершину Г путь «проходил» дважды. (рис.14)
рис.14
^ Ориентированным циклом называется замкнутый путь в ориентированном графе.
На предыдущем рисунке приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.

рис.15

Так, на рисунке 15 пути от А к Д могут быть различны и иметь различную длину.
Первый путь имеет длину 2, второй - 3, а третий — 4.

Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними.
Так расстояние между вершинами А и Д на графе рисунка 15 равно 2; записывают так: S(АД)=2.

рис.16


Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным (обозначают значком бесконечности).
Так, расстояние между вершинами Б и Д графа, представленного на рисунке 16 бесконечно:



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

VII. Биография Л. Эйлера.

Леонард Эйлер (1707-1783) родился в Базеле, в Швейцарии. Его отец, Пауль Эйлер, был сельским пастором. Первые уроки Леонард получил от отца, а учась в последних классах гимназии, он посещал лекции по математике в Базельском университете, которые читал Иоганн Бернулли. Вскоре Эйлер самостоятельно изучает первоисточники, а по субботам Бернулли беседует с талантливым студентом - обсуждает неясные места. Леонард дружит с его сыновьями, особенно с Даниилом.

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

Именно в Петербурге Эйлер сложился как великий ученый. Критически переосмыслив работы Ферма по теории чисел и труды Лейбница и Ньютона по математическому анализу и механике, он нашел свой собственный путь в науке. Почти все его книги и статьи были опубликованы позднее, но главное в научной судьбе Эйлера решилось в его первое петербургское десятилетие.

К 35 годам, из-за постоянных перегрузок, Эйлер успел основательно подорвать свое здоровье. Достаточно сказать, что он во время долгих вычислении перенапряг зрение и ослеп на один глаз. Правда, сам Эйлер отнесся к этому событию философски: «Теперь я меньше буду отвлекаться от занятий математикой». В 1740г. он оказался в тяжелой депрессии, что было связано не только со здоровьем, но и с постоянным напряжением из–за неустойчивости политической жизни в России. К тому времени появляется возможность переехать в Берлин, куда его приглашает король Фридрих II, и Эйлер подает заявление об отставке.

В берлинский период Эйлер написал множество работ. Это были не просто трубы по математике, но и по физике и астрономии: «Введение в анализ бесконечных» (1748), «Морская наука» (1749), «Теория движения Луны» (1753)и др. Эйлер также подготовил к изданию трехтомное «Интегральное исчисление». Ученый проявил себя и как популяризатор науки: им были написаны знаменитые «Письма к немецкой принцессе», в которых в популярной форме Эйлер изложил всю современную физику.

Со временем ситуация в России изменилась, на трон взошла Екатерина II, которой очень хотелось вернуть великого ученого. После переговоров Эйлер в 1766г. возвращается в Россию.

Вскоре после приезда ученый полностью лишается зрения, но не прекращает работать. Приглашенный императрицей окулист удалил катаракту на одном глазу, но предупредил, что перегрузка неминуемо приведет к возвращению слепоты. Но разве мог Эйлер «не вычислять»? Уже через несколько дней после операции он снял повязку. И вскоре потерял зрение снова. На этот раз – окончательно. Впрочем, Эйлер мог вполне разборчиво писать на черной доске мелом. Несмотря на потерю зрения, работоспособность Эйлера не снизилось, даже, наоборот: во второй петербургский период им написано половина всех его трудов. Умер Эйлер в 1783 г., оставив огромное научное наследие, которое до сих пор издается в Швейцарии. Похоронен в Петербурге.

У Эйлера было пятеро детей: три сына и две дочери. После смерти Эйлера все его потомки остались в России.

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

VIII. Тестовые задания.

1. Укажите область, в которой не применяются графы:

а) экономика;

б) физика;

в) архитектура;

г) нет вариантов.

2. Укажите полный граф.



3.Если полный граф имеет n вершин, то количество его ребер равно:

а) (n-1)/2 б) n(n-2)/2 в) n(n-1)/2

4. Какой граф является «эйлеровым графом»



5. Начерти линию одним росчерком (укажи направление).



6. Придумай свой способ записи букв Ф и К, при котором их можно начертить одним росчерком.

Ответ:


7. Решению, какой из следующих задач, соответствует граф



а) В пяти корзинах (А, Б, В, Г, Д) лежат яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта – в корзинах А, Б и Г; в корзинах А, Б и В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д – третьего. Требуется дать каждой корзине номер, но так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно), в корзине №2 – второго и т.д.

б) Трое господ при входе в ресторан отдали швейцару свои шляпы, а при выходе получили их обратно. Сколько существует вариантов, при которых каждый из них получил чужую шляпу?

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

8. Начерчен плоский граф, имеющий шесть вершин, степень каждого из которых равна 4. Этот граф под номером:




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

Ответ:


10. Реши задачу, использовав графы.

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


а) 5 б)10 в)9


IX. Задачи для самостоятельной работы.

1. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.

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

2. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

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


3. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2. Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.

4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей ?

Ответ. Нет (теорема о четности числа нечетных вершин).

5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Ответ. Нет, не может.

6.В Цветочном городе каждый коротышка знаком с 6 малышками, а каждая малышка – с 6 коротышками. Докажите, что в этом городе число малышек равно числу коротышек.

Решение:

Если знакомство вида «коротышка – малышка» - это ребро графа, то n – число коротышек, m – число малышек. Тогда всех знакомств (ребер) коротышек 6n, а малышек 6m. Значит 6n= 6m, тогда в этом городе число малышек равно числу коротышек.

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

Решение:

Если вытекают 3 реки, а впадают 4 – это невозможно, т. к. количество «втекающих», должно быть равно количеству «вытекающих». Дима не прав.

8.Волейбольная сетка – прямоугольник 50x600 клеток. Какое наибольшее число веревочек можно перерезать, чтобы сетка не распалась?

Решение:

Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а ребрами – веревочки. В этом графе нужно удалить как можно больше ребер так, чтобы он остался связным. Заметим, что пока в графе есть цикл, возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Изначально в графе было 601·50+600·51=60650 рёбер и 51·601=30651 вершин, т. е. дерево будет иметь 30650 ребер. Таким образом, разрезать можно 60650-30650=30000 веревочек.

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

Решение:

Допустим, что это возможно, тогда пусть на шоссе n городов, значит дорог всего (2n-1). Поскольку дороги одной компании соединяют все города в связное множество, то этих дорог не меньше n. Тогда дорог двух компаний не меньше 2n, что нам противоречит, а значит не смогут выполнить условия.
10.В городе Н от каждой площади отходит ровно 5 улиц, соединяющих площади. Докажите, что число площадей чётно, а число улиц кратно 5.

Решение:

По теореме, что число нечётных вершин любого графа чётно, следует, что число площадей (вершин графа) 2n, а число улиц (рёбер графа) будет (2n·5):2, а значит, число площадей чётно, а число улиц кратно 5.


X. Заключение.

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

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




Скачать 275,21 Kb.
оставить комментарий
Дата16.10.2011
Размер275,21 Kb.
ТипКонкурс, Образовательные материалы
Добавить документ в свой блог или на сайт

отлично
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх