Теория графов история возникновения. История возникновения и развития теории графов. Теория графов и важнейшие современные прикладные задачи

ГРАФЫ

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

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

Рис. 4.1.

Первая работа по графам была опубликована двадцатилетним Леонардом Эйлером в 1736 г., когда он работал в Российской Академии наук. Она содержала решение задачи о кенигсбергских мостах (рис. 4.1а): можно ли совершить прогулку таким образом, чтобы, выйдя из любого места города, вернуться в него, пройдя в точности один раз по каждому мосту? Ясно, что по условию задачи не имеет значения, как проходит путь по частям суши а, b, с, d, на которых расположен г. Кенигсберг (ныне Калининград), поэтому их можно представить вершинами. А так как связи между этими частями осуществляются только через семь мостов, то каждый из них изображается ребром, соединяющим соответствующие вершины. В результате получаем граф, изображенный на рис. 4.1б. Эйлер дал отрицательный ответ на поставленный вопрос. Более того, он доказал, что подобный маршрут имеется только для такого графа, каждая из вершин которого связана с четным числом ребер.

Следующий импульс теория графов получила почти 100 лет спустя с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам. Наряду с многочисленными головоломками и играми на графах рассматривались важные практические проблемы, многие из которых требовали тонких математических методов. Уже в середине прошлого века Кирхгоф применил графы для анализа электрических цепей, а Кэли исследовал важный класс графов для выявления и перечисления изомеров насыщенных углеводородов. Однако теория графов как математическая дисциплина сформировалась только к середине тридцатых годов прошлого столетия благодаря работам многих исследователей, наибольшая заслуга среди которых принадлежит Д. Кенигу. Значительный вклад в теорию графов внесли советские ученые Л. С. Понтрягин, А. А. Зыков, В. Г. Визинг и др.

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

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

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

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

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так:

Правило Эйлера:

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

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

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

Существует еще один вид задач, связанных с путешествиями вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий через все вершины, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии(в честь Уильяма Роуэна Гамильтона, знаменитого ирландского математика прошлого века, который первым начал изучать такие линии). К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии.

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

Другая старая топологическая задача, которая особенно долго не поддавалась решению и будоражила умы любителей головоломок, известна как “задача об электро -, газо - и водоснабжении”. В 1917 году Генри Э.Дьюдени дал ей такую формулировку. В каждый из трёх домов, изображенных на рисунке, необходимо провести газ, свет и воду.

Тео́рия гра́фов. 1

История возникновения теории графов. 1

Правило Эйлера. 1

Литература

1. Белов Теория Графов, Москва, «Наука», 1968.

2. Новые педагогические и информационные технологии Е.С.Полат, Москва, «Akademia» 1999 г.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат , 1988.

4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука , 1990.

5. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ , 1992.

6. Оре О. Теория графов. – М.: Наука , 1980.

7. Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по куpсу: Дискpетная математика

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

История возникновения теории графов
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.
Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так:
Правило Эйлера:

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

2016 уч. Год

1. Введение

2. История возникновения теории графов

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

4. Основные теоремы теории графов

5. Способы представления графов в компьютере

6. Обзор задач теории графов

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

8. Список литературы

Введение

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

История возникновения теории графов.

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

рис. 1

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

рис. 2

3. Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

Рис. 3

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

1) Графом G(V,E) называется совокупность двух множеств – непустого множества V(множества вершин) и множества E двухэлементных подмножеств множества V(E – множество ребер).

2) Ориентированным называется граф, в котором - множество упорядоченных пар вершин вида (x,y), где x называется началом, а y – концом дуги. Дугу (x, y) часто записывают как . Говорят также, что дуга ведет от вершины x к вершине y, а вершина y смежная с вершиной x.

3) Если элементом множества E может быть пара одинаковых (не различных) элементов V, то такой элемент множества E называется петлей , а граф называется графом с петлями (или псевдографом ).

4) Если E является не множеством, а набором , содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами , а граф называется мультиграфом .

5) Если элементами множества E являются не обязательно двухэлементные, алюбые подмножества множества V, то такие элементы множества E называются гипердугами , а граф называется гиперграфом .

6) Если задана функция F: V → M и/или F: E → M , то множество M называется множеством пометок , а граф называется помеченным (или нагруженным ). В качестве множества пометок обычно используются буквы или целые числа. Если функция F инъективна, то есть разные вершины (ребра)имеют разные пометки, то граф называют нумерованным .

7) Подграфом называется граф G′(V′,E′), где и/или .

a) Если V′ = V, то G′ называется остовным подграфом G.

b) Если , то граф G′ называется собственным подграфом графа G.

c) Подграф G′(V′,E′) называется правильным подграфом графа G(V,E), если G′ содержит все возможные рёбра G.

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

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

a) Если , то маршрут замкнут , иначе открыт .

b) Если все ребра различны, то маршрут называется цепью.

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

d) Замкнутая цепь называется циклом .

e) Замкнутая простая цепь называется простым циклом .

f) Граф без циклов называется ациклическим.

g) Для орграфов цепь называется путем , а цикл – контуром .

рис. 4. Маршруты, цепи, циклы

Пример

В графе, диаграмма которого приведена на рис.4:

1. v 1 , v 3 , v 1 , v 4 – маршрут, но не цепь;

2. v 1 , v 3 , v 5 , v 2 , v 3 , v 4 – цепь, но не простая цепь;

3. v 1 , v 4 , v 3 , v 2 , v 5 – простая цепь;

4. v 1 , v 3 , v 5 , v 2 , v 3 , v 4 , v 1 – цикл, но не простой цикл;

5. v 1 , v 3 , v 4 , v 1 – простой цикл.

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

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

12) Деревом называется связный граф без циклов.

13) Остовом называется дерево, содержащее все вершины графа.

14) Паросочетанием называется множество ребер, в котором никакие два не смежны.

15) Паросочетание называется максимальным , если никакое его надмножество не является независимым.

16) Две вершины в графе связаны , если существует соединяющая их простая цепь.

17) Граф, в котором все вершины связаны, называется связным.

18) Граф, состоящий только из изолированных вершин, называется вполне несвязным.

19) Длиной маршрута называется количество ребер в нем (с повторениями).

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

21) Диаметром графа G называется длина длиннейшей геодезической.

22) Эксцентриситетом вершины v в связном графе G(V,E) называется максимальное расстояние от вершины v до других вершин графа G.

23) Радиусом графа G называется наименьший из эксцентриситетов вершин.

24) Вершина v называется центральной , если ее эксцентриситет совпадает с радиусом графа.

25) Множество центральных вершин называется центром графа.

рис. 5 Эксцентриситеты вершин и центры графов (выделены).

Похожая информация.

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

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

История возникновения теории графов

Родоначальником теории графов считается Леонард Эйлер . В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах , ставшей впоследствии одной из классических задач теории графов. Термин «граф» впервые ввел Сильвестр, Джеймс Джозеф в 1878 году в своей статье в Nature [ ] .

Терминология теории графов

Применение теории графов

См. также

Примечания

Литература

• Дистель Р. Теория графов Пер. с англ. - Новосибирск: Издательство института математики, 2002. - 336 с. ISBN 5-86134-101-X .
• Diestel R. Graph Theory, Electronic Edition . - NY: Springer-Verlag, 2005. - С. 422.
• Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368c.
• Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. - М. : Высш. школа, 1976. - С. 392.
• Берж К. Теория графов и её приложения. М.: ИЛ, 1962. 320c.
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)