1079091
столько раз учителя, ученики и родители
посетили сайт «Инфоурок»
за прошедшие 24 часа
+Добавить материал
и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
Дистанционные курсы профессиональной переподготовки и повышения квалификации для педагогов

Дистанционные курсы для педагогов - курсы профессиональной переподготовки от 5.520 руб.;
- курсы повышения квалификации от 1.200 руб.

ВЫБРАТЬ КУРС СО СКИДКОЙ 60%
Манифест «Инфоурок»
ИнфоурокИнформатикаДругие методич. материалыТеория графов
Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Только сейчас Вы можете пройти дистанционное обучение прямо на сайте "Инфоурок" со скидкой 60% по курсу повышения квалификации "Организация работы с обучающимися с ограниченными возможностями здоровья (ОВЗ) в соответствии с ФГОС" (72 часа). По окончании курса Вы получите печатное удостоверение о повышении квалификации установленного образца (доставка удостоверения бесплатна).

Подать заявку на этот курс    Смотреть список всех 646 курсов

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

библиотека
материалов
Скачать материал целиком можно бесплатно по ссылке внизу страницы.

hello_html_m5998934c.gifhello_html_2d463ecf.gifМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ

ИНСТИТУТ ИМЕНИ М.Е.ЕВСЕВЬЕВА»



ФИЗИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА МАТЕМАТИКЕ И МЕТОДИКИ ОБУЧЕНИЯ МАТЕМАТИКЕ







РЕФЕРАТ

на тему:

«Теория графов».





Выполнила:

студентка 5 курса группы МДМ-109

Кондрашина О.А.

Проверила: Лапина И.Э.

Саранск 2014


Оглавление






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

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

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

  1. Основные понятия теории графов



 Граф G – пара (V,X), где V конечное непустое множество, содержащее p вершин, а множество Х содержит q неупорядоченных пар различных вершин из V.

Каждую пару X={u,v} вершин в Х называют ребром графа G и говорят, что Х соединяет u и v.Мы будем писать X=uv и говорить, что u и v – смежные вершины. Вершина u и ребро Х инцидентны, так же как v и Х. Если два различных ребра X и Y инцидентны одной и той же вершине, то они называются смежными. Граф с р вершинами и q ребрами называется (p;q)- графом. Граф (1,0)- называется тривиальным.[6]

Если элементом множества V может быть пара одинаковых элементов u, то такой элемент множества V называется петлёй.[3]

2. Типы графов:

·  Мультиграф, в нём не допускаются петли, но пары вершин могут соединяться более чем одним ребром, эти рёбра называются кратными (рис.1).

·  Псевдограф, в нём допускаются петли и кратные рёбра (рис.2).







http://www.kazedu.kz/images/referats/a58/176077/1.png


http://www.kazedu.kz/images/referats/a58/176077/2.png







Рис.1 Рис.2

·  Ориентированный граф, или орграф, состоит из конечного непустого множества V вершин и заданного набора Х упорядоченных пар различных вершин. Элементы из Х называются ориентированными рёбрами, или дугами. Нет петель и кратных дуг (рис. 3).










http://www.kazedu.kz/images/referats/a58/176077/3.png








http://www.kazedu.kz/images/referats/a58/176077/4.png

















Рис.3



 


Рис.4



 




·  Направленный граф – это орграф, не имеющий симметричных пар ориентированных рёбер (рис.4).

·  Помеченные графы (или перенумерованные), если его вершины отличаются одна от другой какими-либо пометками. В качестве пометок обычно используются буквы или целые числа.[6]

Степенью вершины vi в графе G называется число рёбер, инцидентных v,обозначается di.[6] Для орграфа вводятся понятия степени входа и выхода. Степенью выхода вершины v называется количество рёбер, для которых v является начальной вершиной, обозначается outdeg(v). Степенью входа вершины v называется количество рёбер , для которых v является конечной вершиной, обозначается indeg(v). Если indeg(v)=0, то вершина v называется источником. Если outdeg(v)=0, то вершина v называется стоком.[1]

  3. Маршруты и связность

 

Граф G/(U/,V/) называется подграфом графа G(U,V), если U/ÌU и V/ÌV. Обозначение: G/ÌG.

Если V/=V, то G/ называется остовным подграфом G.[3]

Маршрутом в графе G называется чередующаяся последовательность вершин и рёбер v0,x1,v1,…vn-1,xn,vn; эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины v и vи его можно обозначить v0v1v2…v (наличие рёбер подразумевается). Эта последовательность иногда называется (v0-vn)-маршрутом. Маршрут замкнут, если v0=vn, и открыт в противном случае. Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины (а следовательно, и рёбра ) различны. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его n вершин различны и n³3.

Граф G называется связным, если любая пара его вершин соединена простой цепью.[6]

 

4. Задача о кёнигсбергских мостах.

 

Отцом теории графов является Эйлер (1707-1782), решивший в 1736г. широко известную в то время задачу, называвшуюся проблемой Кёнигсбергских мостов. В городе Кёнигсберге (ныне Калининград) было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке 5. Задача состояла в следующем: найти маршрут прохождения всех четырёх частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.













































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

Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост – линией (ребром), соединяющей соответствующие точки. Получился “граф”. Этот граф показан на рисунке 6, где точки отмечены теми же буквами, что и четыре части суши на рисунке 5.

http://www.kazedu.kz/images/referats/a58/176077/21.png



Рис.6.

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

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

5. Некоторые задачи теории графов



Проблема семи мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736.

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

Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.

Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания (англ. Decision problem) требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера.

  • Нахождение минимального стягивающего (остовного) дерева.

  • Изоморфизм графов — можно ли путем перенумерации вершин одного графа получить другой.

  • Планарность графа — можно ли изобразить граф на плоскости без пересечений ребер (или с минимальным числом слоев, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).

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



Список используемых источников



  1. http://www.kazedu.kz/referat/176077

  2. http://ru.wikipedia.org/wiki/

  3. http://ru.wikipedia.org/wiki/

  4. http://ru.wikipedia.org/wiki/


11


Ого! На "Инфоуроке" олимпиады стали бесплатными    успеть подать заявку
Не тот материал, который искали? Воспользуйтесь поиском по нашей базе из 3117071 материала.
Искать
Краткое описание документа:
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем. В настоящее время эта теория находит многочисленное применение в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов, в программировании и теории игр, теории передачи 
Общая информация

Вам будут интересны эти курсы:

Курс повышения квалификации «Табличный процессор MS Excel в профессиональной деятельности учителя математики»
Курс повышения квалификации «Информационные технологии в деятельности учителя физики»
Курс повышения квалификации «Методика преподавания информатики в начальных классах»
Курс повышения квалификации «Современные информационные технологии и их использование в работе преподавателей. Системы автоматизированного проектирования одежды и организация технологического процесса»
Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
Курс профессиональной переподготовки «Информатика: теория и методика преподавания в образовательной организации»
Курс «Фирменный стиль» (Corel Draw, Photoshop)
Курс «Оператор персонального компьютера»
Курс «WEB-ВЕРСТКА (HTML, CSS)»
Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»
Курс профессиональной переподготовки «Информационные технологии в профессиональной деятельности: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Введение в программирование на языке С (СИ)»
Курс профессиональной переподготовки «Управление в сфере информационных технологий в образовательной организации»
Курс повышения квалификации «Современные тенденции цифровизации образования»
Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.
Благодарность за вклад в методическое обеспечение учебного процесса по преподаваемой дисциплине

Опубликуйте 3 материала, чтобы БЕСПЛАТНО получить и скачать данную благодарность

Добавить материал
Сертификат о создании персонального учительского сайта

Опубликуйте 5 материалов, чтобы БЕСПЛАТНО получить сертификат о создании сайта

Добавить материал
Грамота за высокий уровень сформированности информационно-коммуникационной компетентности

Опубликуйте 10 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Добавить материал
Свидетельство за транслирование результатов своей профессиональной деятельности

Опубликуйте 15 материалов, чтобы БЕСПЛАТНО получить и скачать данное cвидетельство

Добавить материал
Грамота за личный вклад в повышение качества образования

Опубликуйте 20 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

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

Опубликуйте 25 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

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

Опубликуйте 40 материалов, чтобы БЕСПЛАТНО получить и скачать данную золотую грамоту

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