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

Теория графов берет начало с решения задачи о кенигсбергских мостах в 1736 году знаменитым математиком Леонардом Эйлером (1707-1783: родился в Швейцарии, жил и работал в России).

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

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

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

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

Задача о трех домах и трех колодцах.

Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена (показано, что решения не существует) Куратовским (1896 – 1979) в 1930 году.

Задача о четырех красках. Разбиение плоскости на непересекающиеся области называется картой . Области карты называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом. С конца XIX века известна гипотеза, что для этого достаточно четырех красок. Гипотеза не доказана до сих пор.

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

Проверить «вручную» полученное решение невозможно – объем перебора выходит за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки…

Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они все сделали правильно.

Определение 7.1. Графом G = G (V , E ) называется совокупность двух конечных множеств: V – называемого множеством вершин и множества E пар элементов из V, т.е. EÍV´V, называемого множеством рёбер , если пары неупорядочены, или множеством дуг , если пары упорядочены.

В первом случае граф G (V , E ) называется неориентированным , во втором – ориентированным.


ПРИМЕР. Граф с множеством вершин V = {а,b,с} и множеством ребер Е ={{а, b}, {b, с}}

ПРИМЕР. Граф, у которого V = {a,b,c,d,e} и Е = {{а, b}, {а, е}, {b, е}, {b, d}, {b, с}, {с, d}},

Если e=(v 1 ,v 2), еÎЕ, то говорят, что ребро е соединяет вершины v 1 и v 2 .

Две вершины v 1 ,v 2 называются смежными , если существует соединяющее их ребро. В этой ситуации каждая из вершин называется инцидентной соответствующему ребру.

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

Число вершин графа G обозначим v , а число ребер - e :

.

Геометрическое представление графов следующее:

1) вершина графа – точка в пространстве (на плоскости);

2) ребро неориентированного графа – отрезок;

3) дуга ориентированного графа – направленный отрезок.

Определение 7.2. Если в ребре e=(v 1 ,v 2) имеет место v 1 =v 2 , то ребро е называется петлёй . Если в графе допускается наличие петель, то он называется графом с петлями или псевдографом .

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

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

Определение 7.3. Граф G (V , E ) называется подграфом (или частью ) графа G (V ,E ), если V V , E E . Если V = V , то G называется остовным подграфом G .

Пример 7 . 1 . Дан неориентированный граф.



Определение 7.4. Граф называется полным , если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через K n .

Графы К 2 , К 3, К 4 и К 5 .

Определение 7.5. Граф G =G (V , E ) называется двудольным , если V можно представить как объединение непересекающихся множеств, скажем V =A B , так что каждое ребро имеет вид (v i , v j ), где v i A и v j B .

Каждое ребро связывает вершину из А с вершиной из В, но никакие две вершины из А или две вершины из В не являются связанными.

Двудольный граф называется полным двудольным графом K m , n , если A содержит m вершин, B содержит n вершин и для каждого v i A , v j B имеем (v i , v j )E .

Таким образом, для каждого v i A , и v j B имеется связывающее их ребро.

K 12 K 23 K 22 K 33

Пример 7 . 2 . Построить полный двудольный граф K 2,4 и полный граф K 4 .

Граф единичного n -мерного куба В n .

Вершины графа - n-мерные двоичные наборы. Рёбра соединяют вершины, отличающиеся одной координатой.

Пример:















Назад Вперёд

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

Цели урока:

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

    • Оборудование:

    • компьютерный класс, оснащенный современной техникой, видеопроектор, экран;
    • компьютеры с ОС Windows XP, программа Microsoft Office 2003 PowerPoint;
    • оборудование доски (тема урока, новые термины). Раздаточный материал.

    План урока.

    II. Изложение нового материала. (10 мин.)

    III. Закрепление материала. Практическая работа. (15-20 мин.)

    IV. Подведение итога урока.(2 мин)

    V. Домашнее задание.

    I. Организационный момент. Актуализация знаний.

    Здравствуйте! Наш урок называется “Графы”. Мы познакомимся с понятие “Графы”, научимся их изображать и решать задачи по этой теме.

    II Изложение нового материала.

    Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 г.), хотя термин “граф” впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке 1)

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

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

    Граф – это некоторая информационная модель

    Граф состоит из вершин или узлов, связанных дугами или отрезками - рёбрами. Линия может быть направлена, т. е. иметь стрелку (дуга), если не направлена – ребро. Две вершины, соединённые дугой или ребром называются смежными.

    Примеры графов (Слайд 4, 5, 6)

    Задание 1 (Слайд 7):

    Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:

    Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс; Марс – Уран.

    Можно ли долететь на рейсовых ракетах с Земли до Марса?

    Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

    Теперь сразу видно, что долететь с Земли до Марса нельзя.

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

    Задание 2 (9 слайд) – решение у доски. Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти? Желтая, красная, зеленая?

    Задание 3 (11 слайд) – решение у доски. Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г; Б с А, В, Д. сколько матчей уже сыграно? Сколько осталось сыграть?

    Представление графов (Слайд 12)

    Граф может быть представлен в виде списка дуг (АВ; 7), графически или с помощью таблицы.

    Списки дуг Графическая форма Табличная форма
    (АВ; 7),
    А В С
    А 3
    В 4
    С 3 4

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

    Задание 2 (Слайд 13)

    IV. Итог урока

    Ребята, какие новые слова вы сегодня узнали? (Граф, вершина графа, ребра графа.)

    Что могут обозначать вершины графа? (Города; объекты, которые; связаны.)

    Что обозначают ребра графа (Пути, движения, направления)

    Приведите пример, где в жизни мы можем с ними встретиться?

    Как изображаются графы?

    V. Домашнее задание. (Слайд 15)

    Тема графов — это интересная, полезная и пугающая тема. Теория графов — "Ужас студента". Алгоритмы на графах — потрясающий ум людей их открывших.

    Что такое граф? Чтобы ответить на этот вопрос своим читателям, я буду описывать тему немного по-своему.
    Граф — это множество объектов.
    В большинстве задач это однотипные объекты. (Множество городов или множество домов, или множество людей, или множество чего-то ещё однотипного)

    Чтобы решать задачи с таким множеством, нужно каждый объект из этого множества обозначить как что-то. Общепринято это самое что-то называть вершинами графа.

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

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

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

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

    В литературе, в интернете и вообще везде, где что-то написано о графах, вы будете встречать такие понятия, как дуги и ребра. На этом рисунке изображены ребра графа. Т.е. это три ребра Е1, Е2 и Е3.

    Дуга и ребро отличаются тем, что ребро — это такая двунаправленная связь. Захотел, ушел к соседу, захотел, вернулся от соседа. Если не очень понятно, то можно представить дом, аэродром, летящий самолет и парашютиста. Парашютист может пойти из своего дома на аэродром, но когда пришел на аэродром, вспомнить, что свой счастливый парашют забыл дома, затем вернуться домой, взять парашют. — Такая дорога, по которой можно гулять туда и обратно, называется ребром.
    Если парашютист находится в самолете и прыгает с самолета, но парашютист забыл в самолете надеть свой счастливый парашют, то сможет ли парашютист забрать что забыл? Такой путь, который идет только в одну сторону, называется дугой. Обычно говорят, что ребро соединяет две вершины, а дуга идет из одной вершины в другую.

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


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

    Многое не описано, но эта часть информации может быть кому-то поможет.

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

    О курсе

    Этот курс служит введением в современную теорию графов. Граф как математический объект оказывается полезным во многих теоретических и практических задачах. Дело, пожалуй, в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. В нашем курсе мы, конечно же, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов.

    Формат

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

    Информационные ресурсы

    1. В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. М.: Книжный дом «Либроком», 2009.
    2. А. А. Зыков. Теория конечных графов. Новосибирск: Наука, 1969.
    3. М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. М.: Мир, 1984.
    4. M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009.
    5. B. Bollobás. Modern Graph Theory. Springer, 1998.
    6. J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008.

    Требования

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

    Программа курса

    1. Понятие графа и виды графов.
    2. Различные применения графов: от Кенигсберских мостов до Интернета.
    3. Связность графа, подграфы и степень вершины.
    4. Эквивалентные определения деревьев.
    5. Планарность и критерий Куратовского
    6. Формула Эйлера.
    7. Хроматическое число планарного графа.
    8. Перечисление деревьев: код Прюфера и формула Кэли.
    9. Формула для числа унициклических графов.
    10. Эйлеровы циклы и критерий эйлеровости.
    11. Гамильтоновы циклы. Критерий Дирака и критерий Хватала.
    12. Паросочетания. Теорема Холла и Кенига.
    13. Экстремальная теория графов. Теорема Турана.
    14. Аналог теоремы Турана для графов на плоскости.
    15. Теория Рамсея. Знакомства среди шести человек.
    16. Определение числа Рамсея.
    17. Нижняя и верхняя оценки чисел Рамсея.

    Результаты обучения

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

    Неформально граф можно рассматривать как множество точек и соединяющих эти точки линий со стрелками или без них.

    Первой работой теории графов как математической дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кёнингсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.

    С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Точками на ней представлены станции, а линиями - пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое древо. И это древо - граф.

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

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

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

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

    • Основные определения

      Графы, как уже отмечалось в примерах, есть способ „визуализации" связей между определенными объектами. Связи эти могут быть „направленными", как, например, в генеалогическом древе, или "ненаправленными" (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные (или направленные) и неориентированные.

    • Способы представления

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

    • Деревья

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

    • Остовное дерево наименьшего веса

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

    • Методы систематического обхода вершин графа

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

    • Задача о путях во взвешенных ориентированных графах

    • Изоморфизм графов

      Для ориентированного графа (V, Е) множество Е дуг можно рассматривать как график бинарного отношения непосредственной достижимости, заданного на множестве вершин. В неориентированном графе (V, Е) множество Е ребер является множеством неупорядоченных пар. Для каждой неупорядоченной пары {u, v} ∈ Е можно считать, что вершины u и v связаны симметричным бинарным отношением р, т.е. (u, v) ∈ р и (v, u) ∈ р.

    • Топологическая сортировка

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

    • Элементы цикломатики

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