 |
Задачи по теореме Эйлера о нечетных вершинах
|
|
|
|
ДОКЛАД
по информатике на тему:
“Исторические веки. Теория Графов”
Выполнил: Петрунин Владимир, группа 21
Павлово 2017 г
Содержание:
I. Введение
II. Основная часть.
1.История возникновения теории графов.
2.Некоторые задачи теории графов.
2.1 Логические задачи
2.2 Задачи на связность.
2.3 Задачи по теореме Эйлера о нечетных вершинах
3.Применение теории графов в различных сферах деятельности.
3.1.Графы и информация
3.2.Графы и химия.
3.3.Графы и биология
3.4.Графы и физика
I. Введение.
Я выбрал эту тему, потому что она была и остается актуальной в наше время.
Сейчас почти в любой отрасли науки и техники встречается применение графов. В физике - при построении электрических схем, в химии и биологии
- при изучении молекул и их цепочек, в географии – при составлении карт, в истории – при составлении родословной,
в геометрии – в чертежах многоугольников, многогранников, пространственных фигур, в экономике – при решении задач о выборе оптимального пути для потоков грузового транспорта (схем авиалиний, метро, железных дорог).
Графами являются блок-схемы программ для ЭВМ, сетевые графики строительства. С помощью графов решается задача о назначении на должности.
Теория графов в школьной программе не изучается, но широко применяется при решении математических олимпиадных задач.
II. 1. История возникновения теории графов
Изучив информацию Интернет-ресурсов, я для себя открыл следующие интересные факты об истории теории графов.
Родоначальником теории графов принято считать математика Леонарда Эйлера.
Историю возникновения этой теории можно проследить по переписке великого ученого. В ней он сообщал, что ему была предложена задача о семи мостах Кенигсберга. Спрашивалось, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И ему сразу же было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот показался ему достойным внимания тем, что «…Для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство...». После долгих размышлений он нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на рисунке, на котором А обозначает остров, а В, С и D - части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами а, b, с, d, е, f, g.
|
|
|
http://www. cba. upc. edu/projects/logos/Euler_logo. png Кенигсбергские мосты.
Некоторые задачи теории графов
Задач по теории графов не так много. Я рассмотрел материалы
Интернет-ресурсов и книг, разобрал предлагаемые там задачи, попыталась их систематизировать и выделила из них разные, на мой взгляд, задачи, решаемые с помощью графов
Логические задачи
Задача 1. Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени (рис.2), а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки — имена (рис. 3).
Нулевой граф с пятью вершинами
Неполный граф с пятью вершинами
http://school-sector. *****/dckt/projects/ctrana/graf/gr1.htm
Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки — ребрами графа. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; Длины отрезков и расположение точек произвольны.
|
|
|
Рассмотрим процесс соединения точек А, Б, В, Г, Д ребрами.
1. Ситуация, соответствующая моменту, когда рукопожатия еще не совершались, представляет собой точечную схему, изображенную на рисунке 2. Такая схема, состоящая из «изолированных» вершин, называется нулевым графом.
2. Ситуация, когда совершены еще не все рукопожатия, может схематически быть изображена, например, с помощью рисунка З: пожали руки А и Б, А и Г, Д и Г, В и Д.
Графы, в которых не построены все возможные ребра, называются неполными графами.
3. На рисунке 4 изображен граф, соответствующий всем совершенным рукопожатиям. Этот граф является полным графом.
Задачи на связность.
Есть еще одно важное понятие, относящееся к графам – понятие связности.
Граф называется связным, если две его любые вершины можно соединить путем, т. е. непрерывной последовательностью ребер.
Существует целый ряд задач, решение которых основано на понятии связности графа.
Графы Эйлера.
Я часто сталкивался с задачами, в которых требуется нарисовать какую-либо фигуру, не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т. е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.
Задачи по теореме Эйлера о нечетных вершинах
Задача 1. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?
Ответ. Нет (по теореме о четности числа нечетных вершин).
Задача 2. У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?
Ответ. Нет, не может. В противном случае получился бы граф соседства баронств с нечетным количеством нечетных вершин.
|
|
|
Применение теории графов.
Чем больше я изучал теорию графов, тем больше поражалась разнообразию применения этой теории. Графы применяются в различных отраслях науки.
Графы и информация
Графы играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде
конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности.
Графы и химия.
Теория графов в химии применяется для решения различных теоретических и прикладных задач. Применение графов теории базируется на построении и анализе различных классов химических и химико-технологических графов, которые называются также топология, т. е. модели, учитывающие только характер связи вершин. Ребра и вершины этих графов отображают химические и химико-технологические понятия, явления, процессы или объекты и соответственно качественные и количественные взаимосвязи либо определенные отношения между ними.
Графы и биология
Графы играют большую роль в биологической теории ветвящихся процессов. Для простоты я покажу только одну разновидность ветвящихся
процессов – размножение бактерий. Предположим, что через определенный
промежуток времени каждая бактерия либо делится на две новые, либо
погибает. Тогда для потомства одной бактерии я получу двоичное дерево.
Нас будет интересовать лишь один вопрос: в скольких случаях n-е
поколение одной бактерии насчитывает ровно k потомков? Математически вычисляемое на основе значений предыдущих членов последовательности соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.
Графы и физика
|
|
|
Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либо диэлектрика
(изолирующего материала), на которой в виде металлических полосок
вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы, их пересечение в других местах вызовет замыкание электрической цепи.
В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.
Изучая этот материал, я узнал области применения теории графов и сделала вывод, что этот раздел математики является одним из важнейших, который используется в нашей повседневной жизни часто незаметно для нас.
|
|
|
