Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015

Опубликуйте свой материал в официальном Печатном сборнике методических разработок проекта «Инфоурок»

(с присвоением ISBN)

Выберите любой материал на Вашем учительском сайте или загрузите новый

Оформите заявку на публикацию в сборник(займет не более 3 минут)

+

Получите свой экземпляр сборника и свидетельство о публикации в нем

Инфоурок / Информатика / Другие методич. материалы / Теория графов
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 24 мая.

Подать заявку на курс
  • Информатика

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

библиотека
материалов

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


Краткое описание документа:

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

Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Похожие материалы

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