нем. Graf), дворянский титул. В России введен Петром I (первым его получил в 1706 Б. П. Шереметев). В конце 19 в. учтено свыше 300 графских родов. Ликвидирован Декретом ВЦИК и Совнаркома от 11.11.1917.
Отличное определение
Неполное определение ↓
Граф
Антон (Graf, Anton) 1736, Винтертур - 1813, Дрезден. Немецкий живописец. Учился в 1753-1756 у И. У. Шелленберга в Винтертуре, затем у И. Я. Хайда в Аугсбурге. Работал как портретист в Регенсбурге, Винтертуре, Аугсбурге, Мюнхене, Цюрихе. С 1766 - придворный художник в Дрездене. С 1789 - профессор дрезденской Академии художеств. Член берлинской, венской, мюнхенской академий художеств. Много путешествовал по Германии и Швейцарии. Портретист, писал также пейзажи, занимался миниатюрой. Ранние произведения художника исполнены в традиции парадного барочного портрета. Образы знатных особ королевского дворца Пруссии полны торжественности и представительности в портретах Фридрих, принц Прусский (1777-1778), Фредерика, принцесса Прусская (1787), Фридрих Вильгельм II, король Пруссии (1788, все - Берлин, Шарлоттенбург). Сильная светотень и теплая колористическая гамма свидетельствуют об увлечении молодого художника манерой Рембрандта. В 1780-1790-е Граф часто пишет модели на фоне пейзажа, несколько смягчающего напряженность, статику фигур в его портретах (Генрих VIII, 1804, Германия, частное собрание; И. Ф. фон Тильман, Нюрнберг, Германский нац. музей). В духе неоклассицистических вкусов эпохи изображает портретируемых в виде античных граций в пейзаже (Фредерика Хиллендорф, 1803, Германия, частное собрание). Более глубоки по передаче внутреннего состояния портреты близких художнику людей: Художник К. К. Люнвиг (1808, Гамбург, Кунстхалле), лирические женские образы - Луиза Элизабета Функ (1790, Лейпциг, Музей изобразительных искусств), Каролина Сюзанна Граф (1805, Гамбург, Кунстхалле). Тонкой светотеневой моделировкой подчеркнута присущая образам Графа четкая пластика фигур. Воздушное сфумато, окутывающее фигуры, свидетельствует об изучении приемов английского портрета XVIII в. Портреты выдающихся деятелей эпохи Просвещения - С. Гесснера (1765-1766, Цюрих, Кунстхалле), Г. Э. Лессинга (1771, Лейпциг, библиотека Университета), К. М. Виланда (1794, Веймар, Музей Гете), И. Г. Зульцера (1771, Винтертур, Кунстхалле) - пожалуй, самое значительное, что было создано художником. В портретах тестя художника И. Г. Зульцера, известного немецкого философа, эстетика и математика, и С. Гесснера, швейцарского поэта, автора поэтического сборника Идиллии (1756), Граф использует схему барочного портрета, изображая модели в момент как бы прерванного движения. Подлинный художник века Просвещения, Граф стремится раскрыть одухотворенность и светлый ум людей, ставших культурным достоянием нации. Портреты написаны на темном фоне, как и ряд других поздних произведений (Х. И. Медем, 1796; Г. Л. Гогель, 1796, оба - Санкт-Петербург, Гос. Эрмитаж). Интерес к психологически углубленной разработке образа присущ и автопортретам художника. В ранних автопортретах 1765 (Нью-Йорк, Историческое общество) и 1766 (Дрезден, Картинная галерея) мотив прерванного движения вносит некоторую традиционность в композиционное решение. Поздние работы (1794-1795, Дрезден, Картинная галерея; 1808, Винтертур, Кунстхалле) создают образ художника, чье творчество обозначило многие важные явления немецкой культуры XVIII в., закладывая традиции реалистической образности последующего столетия. В поздний период художником был написан ряд пейзажей, характеризующих прекрасное владение рисунком с натуры, интерес к пленэру, разработке проблемы "пейзажа настроения" (Вид окрестностей Дрездена, 1800; Утро, ок. 1800; Полдень, ок. 1800; Вечер, ок. 1800, все - Дрезден, Картинная галерея).
История возникновения и развития теории графов 1736 г. , Леонард Эйлер, задача о кенигсбергских мостах (Г. Кенигсберг расположен на берегах реки Прегель, в городе 7 мостов. Можно ли совершить прогулку, чтобы выйти из дома и вернуться обратно, пройдя по каждому мосту только один раз?) o Середина XIX в. , Г. Кирхгоф описание с помощью графов электрических цепей, А. Кэли химических схем o Как математическая дисциплина сформировалась в середине 30 -х гг. XX в. (1936 г, выход в свет o
Области применения теории графов o o o Анализ и синтез электрических и пр. цепей и систем, сетевое планирование и управление, исследование операций, выбор оптимальных маршрутов и потоков в сетях, моделирование жизнедеятельности организмов, исследование случайных процессов и др. Практические проблемы, решение которых сводится к рассмотрению совокупности объектов и связей между ними. Например, карта автомобильных дорог – как связь между населенными пунктами, различные связи и отношения между людьми, событиями, состояниями и вообще между любыми объектами Многочисленные головоломки и игры на
o Головоломки, в которых требуется обрисовать некоторую фигуру, не прерывая и не повторяя линии, например или Сабли Магомета
Основные определения o o o Граф – это объединение конечного числа точек и линий, которыми соединены некоторые из точек. Точки называют вершинами графа, а линии, их соединяющие – ребрами Число ребер, выходящих из вершины, называется степенью этой вершины
Примеры графов o o Каркас любого многогранника в пространстве Схема линий в метро Структурные формулы молекул Генеалогическое дерево
Примеры задач, решаемых с помощью графов 1. Путешественники o В бюро по туризму составляют маршрут для путешественников, желающих проехать из города А в город В, осмотрев по пути все достопримечательности, расположенные в городах C, D, E, F, G, H, K, M. Составить маршрут поездки нужно таким образом, чтобы туристы посетили все указанные города и побывали в каждом из них ровно по одному разу.
o По условию задачи путешествие должно начаться в пункте А и закончится в пункте В. Заметим, что в города D и F ведут всего две дороги. Значит по этим дорогам путешественники обязательно проедут. Отметим их жирной линией. Тем самым определен участок маршрута CDEFG. Значит по дорогам AE, AG, EM туристы проезжать не будут (иначе они два раза посетят пункт E). Перечеркнем эти дороги. Отметим жирной линией участок AC, поскольку из A осталась только эта дорога. Перечеркнем CM (в С мы уже были). Через М остались неперечеркнуты две дороги: MH и MB, значит по ним туристы и поедут. Отметим их жирной линией. Осталась единственная возможность проехать из G в H
o Таким образом, мы нашли нужный маршрут. В этом нам помогла схема расположения городов и дорог, которая является на самом деле графом с 10 вершинами и 17 ребрами. Вершины A, D, F имеют степень два, вершины C и K – степень три, H, M, B – вершины четвертой степени, а G и E – пятой.
2. Знакомства o Может ли так случится, что в компании, состоящей из 8 человек, каждый знаком ровно с двумя другими людьми?
2. Знакомства (решение) o o Сопоставим участникам компании вершины графа, соединим две вершины ребром, если соответствующие два человека знакомы между собой. Чтобы каждый был знаком ровно с двумя другими людьми, любая вершина графа должна иметь степень 2. Примеры таких графов: Раз такие графы существуют, значит ситуация, описанная в задаче возможна.
3. Шахматный турнир o Пусть в турнире должны участвовать n шахматистов, все должны сыграть друг с другом ровно по одной партии. Сопоставим каждому участнику вершину графа, а каждой сыгранной парии ребро графа, соединяющее соответствующие вершины
Полный граф o o o До начала турнира граф состоит только из точек, у него нет ни одного ребра. Такие графы называются нуль-графами По окончании турнира каждый участник сыграл с любым другим и каждая пара вершина соединена между собой ребром. Такой граф называется полным. В полном графе с n вершинами степень каждой вершины равна (n-1) Неполный граф можно превратить в полный, добавив недостающие ребра. На рис. толстой линией изображен граф с 5 вершинами, который не является полным. Добавив
Ориентированный граф o o o Часто связи между объектами характеризуются определенной ориентацией (схема дорог с односторонним движением, подчиненность или старшинство в отношениях между людьми, результаты встреч между командами в спортивных состязаниях) Изображенный нами граф шахматного турнира не дает информации о том, кто же выиграл каждую партию. Можно на каждом ребре ставить стрелочку от вершины А к вершине В, если шахматист А проиграл шахматисту В, т. е. ориентировать ребра, указав на них направление Граф, на котором указано направление каждого ребра, называется
o Граф, содержащий как ориентированные, так и неориентированные ребра, называется смешанным (например, граф шахматного турнира, в котором некоторые партии окончились вничью. Ничейному результату сопоставим ребро без стрелочки)
Маршрут графа o o o Маршрут длины m произвольного графа – это такая последовательность m ребер (не обязательно различных), в которой граничные вершины двух соседних ребер совпадают. Длина маршрута – количество ребер (если по ребру проходим 2 раза, то и считаем это ребро 2 раза) Маршрут замкнутый, если его начальная и конечная вершины совпадают Цепь - незамкнутый маршрут, в котором все ребра различны Простая цепь - цепь, в которой все вершины различны (пример – задача 1. (О путешественниках)
Циклы, связные графы o o o Цикл - замкнутый маршрут, в котором все ребра различны. Простой цикл - цикл, в котором все вершины различны (пример – задача о знакомствах. Первый граф содержит один простой цикл, второй и третий – по два простых цикла) Граф называют связным, если существует маршрут из любой его вершины в любую другую, и несвязным в противном случае (пример – задача о знакомствах, первый граф – связный, каждый человек может познакомится с остальными через своих знакомых, второй и третий – несвязные, в компании так и останутся незнакомые люди)
o o o o B-D-A-C-D-A – незамкнутый маршрут A-C-D-A-B-D-A - замкнутый маршрут A-C-D-E-F-D-B – цепь A-B-G-H – простая цепь A-C-D-E-F-D-A – цикл D-E-F-D – простой цикл Посчитайте длину этих маршрутов Определите к какому типу относятся маршруты A-B-D-F-E-D-C-A; A-D-E; D-E-F-D; A-C-D-B-A;
Деревья o o Дерево – связный граф, не имеющий циклов Генеалогическое дерево, файловая система и пр.
Задача 4. Деление на части o Разрезаем лист бумаги на 3 части. Некоторые из полученных листиков снова разрезаем на 3 части. Некоторые из разрезанных листиков – еще раз на три части и т. д. Сколько получится отдельных листиков, если сделано k разрезаний?
Задача 4. Деление на части (решение) o o Листы бумаги вершины графа. Закрашенные вершины соответствуют разрезанным листикам, незакрашенные – неразрезанным. При разрезании одного листика число листиков увеличивается на 2. Если всего было разрезано k листиков, то число листиков увеличится на 2 k. Первоначально у нас был один лист. , поэтому после k разрезаний получится (2 k+1) листик. На графе проиллюстрирован случай, когда k=6. (2 k+1) =13
Теорема о сумме степеней вершин графа o o Пусть граф Г имеет N вершин и M рёбер. Каждая i-ая вершина имеет степень di Поскольку каждое ребро соединяет две вершины, оно добавляет двойку к сумме степеней вершин графа, поэтому сумма степеней вершин равна удвоенному количеству ребер
Задача 5. Количество дорог o Может ли в государстве, в котором из каждого города выходят ровно 3 дороги быть ровно 100 дорог?
Задача 5. Количество дорог (решение) o Предположим, такая ситуация возможна. В государстве N городов, из каждого города выходят 3 дороги. Значит мы имеем граф с N вершинами, каждая из которых имеет степень 3. Следовательно, сумма степеней вершин равна 3 N, а число ребер – 3 N/2. Это число по условию равно 100. Т. е. 3 N/2=100 или 3 N=200. Такого натурального числа не существует. Значит в этом государстве не может быть 100 дорог.
Самостоятельно o В некотором царстве царь издал указ: построить 7 городов и соединить их дорогами так, чтобы из каждого города выходило по 3 дороги. Выполним ли такой приказ? Станет ли он выполним, если из каждого города будут выходить 4 дороги?
Задача 6. о кенигсбергских мостах o Г. Кенигсберг расположен на берегах реки Прегель, в городе 7 мостов. Можно ли совершить прогулку, чтобы выйти из дома и вернуться обратно, пройдя по каждому мосту только один раз?
Решение задачи о кенигсбергских мостах o o o Обозначим части города A, B, C, D. Это будут вершины графа. Мосты, соединяющие части города – ребра графа. Эйлер показал, что задача не имеет решения, т. е. не существует цикла, проходящего по всем рёбрам точно по одному разу. Ведь если бы такой цикл существовал, то в каждой вершине графа было бы столько входящих в неё рёбер, сколько и выходящих из неё, т. е. в каждой вершине графа было бы чётное число рёбер (войдя в вершину по одному ребру, мы должны выйти из нее по другому ребру). Однако это условие, очевидно, не выполнено для графа, представляющего карту Кёнигсберга. Убедитесь в этом, определив степень каждой вершины графа
Эйлеров граф o o Изложив решение задачи о кёнигсбергских мостах, Эйлер в своей работе перешёл к следующей общей проблеме теории графов: на каких графах можно найти цикл, содержащий все рёбра графа, причём каждое ребро в точности по одному разу? Такой цикл называется эйлеровой линией или эйлеровым циклом, а граф, обладающий эйлеровой линией, – эйлеровым графом. Итак, эйлеров граф можно обойти полностью, проходя по каждому ребру только один раз. Поэтому эйлеровы графы можно построить, не отрывая карандаша от бумаги и не проводя одну и ту же линию дважды.
Необходимое и достаточное условие существования эйлерового графа o o o Для того, чтобы граф имел эйлерову линию, он должен быть связным. Как и в задаче о кёнигсбергских мостах, ясно, что каждая эйлерова линия должна входить в каждую вершину и выходить из неё одно и то же число раз, т. е. степени всех вершин графа должны быть чётными. Значит, чтобы граф был эйлеровым, необходимы два условия: связность графа и чётность степеней всех его вершин. Эйлер доказал, что эти условия являются также и достаточными: связный граф, степени всех вершин которого чётные, обладает эйлеровой линией.
Самостоятельно o Определите, являются ли эти графы эйлеровыми? (можно ли обвести их одним росчерком пера, не прерывая и не повторяя линии, и вернуться в ту точку, с которой начали) Если да, найдите в них эйлеровы циклы (покажите, как это сделать)
Эйлеров путь o o Эйлеров путь – это путь, когда все рёбра проходятся по одному разу, но без возвращения в исходную точку. Если граф не обладает эйлеровым циклом, то можно поставить задачу об отыскании эйлерова пути
Достаточное условие существования эйлерового пути o o Если граф Г обладает эйлеровым путём с концами А и В (А не совпадает с В), то граф Г связный и А и В – единственные нечётные его вершины. Действительно, связность графа следует из определения эйлерова пути. Если путь начинается в А, а заканчивается в другой вершине В, то и А и В – нечётные, даже если путь неоднократно проходил через А и В. В любую другую вершину графа путь должен был привести и вывести из неё, т. е. все остальные вершины должны быть чётными.
Необходимое условие существования эйлерового пути o o Верно и обратное: если граф Г связный, а А и В – единственные нечётные вершины его, то граф Г обладает эйлеровым путём с концами А и В. Вершины А и В могут быть соединены ребром в графе, а могут быть и не соединены. В любом случае добавим либо дополнительное, либо новое ребро (А, В), тогда все вершины его станут чётными. Новый граф, согласно приведённому выше конструктивному доказательству достаточного условия существования эйлерового графа, обладает эйлеровым циклом, который можно начать по любому ребру. Начнём эйлеров цикл из вершины А по добавленному ребру (А, В) и кончим его в вершине А. Если удалить теперь
Применение теоремы об эйлеровом пути o o Таким образом, всякую замкнутую фигуру, имеющую в точности две нечётные вершины, можно расчертить одним росчерком без повторений, начав в одной из нечётных вершин, а закончив в другой. В соответствии с этой теоремой через кёнигсбергские мосты не существует эйлерова пути, так как хотя соответствующий граф связный, но степени всех его вершин нечётные, а должно быть только две вершины нечётными, а остальные чётными, чтобы существовал эйлеров путь
Самостоятельно o В соответствии с теоремой об эйлеровом пути определите: существует ли эйлеров путь в графах? (можно ли расчертить одним росчерком без повторений, начав в одной из вершин, а кончив в другой). Если существует, найдите его (покажите, как это сделать)
Задача 7. 2. О кенигсбергских мостах для воображаемого города (самостоятельно) o На рисунке план воображаемого города, который Эйлер использовал для иллюстрации в своей работе. Начертите граф для плана Эйлера и определите, существует ли в нём эйлеров цикл? А эйлеров путь? Если да – то найдите его
Задача 8. Зоопарк (самостоятельно) o На рисунке схема зоопарка (вершины графа – вход, выход, перекрёстки, повороты, тупики, рёбра-дорожки, вдоль которых расположены клетки). Найдите маршрут, по которому экскурсовод мог бы провести посетителей, показав им всех зверей и не проходя более одного раза ни одного участка пути, т. е. найдите эйлеров путь.
Основные понятия теории графов.
Примеры использования теории графов.
История возникновения теории графов.
Мы частенько рисуем на листочках бумаги кружочки, квадратики, точки обозначая ими людей, населённые пункты, дела которые мы должны сделать и тому подобное, и соединяем их прямыми и ломаными линями, стрелочками которыми обозначаем связи между ними, отношения, последовательность действий и тому подобное.
Такие схемы встречаются всюду под разными названиями: социограммы (в психологии), симплексы (в топологии), электрические цепи (в физике), диаграммы организации (в экономике), сети коммуникаций, генеалогические деревья и т.д.
Д.Кёниг, предложил называть такие схемы "графами" и систематически изучать их свойства.
В совершенно различных дисциплинах приходится использовать аналогичные теоремы; так, понятие "матрицы инциденций", введенное Кирхгофом для изучения электрических цепей, было привлечено А.Пуанкаре в топологию при создании его "analysis situs"; понятие "точки сочленения", с давних пор известное в социологии, впоследствии появилось в электронике; все примеры такого рода перечислить невозможно. Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной.
В действительности такие основные понятия, как "цепь", "путь", "центр", будучи определены абстрактно, остаются в то же время неразрывно связанными с графической реальностью и легко распознаются, когда схема начерчена.
Рассматривая теорию графов, мы не ставим целью дать в руки математическое средство, наша задача сформировать общее представление прежде всего о её прикладных возможностях в теории организации управления.
Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, кибернетика, общая теория систем, общая теория организаций, генетика, психология, социология, экономика, антропология и лингвистика и другие науки.
Эта теория тесно связана также со многими разделами математики, среди которых - теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ.
Теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем.
Теория графов «открывалась» независимо много раз: её с полным основанием можно считать разделом прикладной математики. В самом деле, наиболее раннее известное упоминание этой теории встречается в работах Эйлера, и хотя проблему, которой он занимался, можно рассматривать как обычную головоломку, псе же она возникла из практики.
Последующие переоткрытия теории графов Кирхгофом и Кэли также уходят своими корнями в реальную действительность. Изучение Кирхгофом электрических цепей привело к разработке им основных понятий и получению ряда теорем, касающихся деревьев в графах. В свою очередь Кэли подошел к исследованию деревьев, решая задачи перечисления органических изомеров.
Другой подход к графам, связанный с рассмотрением головоломок, был предложен Гамильтоном. После этого появилась знаменитая гипотеза четырёх красок, которая до сих пор пользуется широкой известностью.
В наше столетие также было чрезвычайно много переоткрытий теории графов. Упомянем кратко некоторые из них, придерживаясь хронологического порядка.
Задача о кёнигсбергских мостах
Отцом теории графов (так же как и топологии) является Эйлер (1707-1782), решивший в 1736 г. широко известную в то время задачу, называвшуюся проблемой кёнигсбергских мостов.
В городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке.
Задача состояла в следующем: найти маршрут прохождении всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.
Легко, конечно, попытаться решить эту задачу эмпирически, производя перебор всех маршрутов, но все попытки окончатся неудачей.
Вклад Эйлера в решение этой задачи заключается в том, что он доказал невозможность такого маршрута.
Рисунок 1. Парк в городе Кенигсберге, 1736 г.
Рисунок 2. Граф к задаче о кенигсбергских мостах
Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост - линией (ребром), соединяющей соответствующие точки.
Получился «граф». Этот граф показан на рисунке 2., где точки отмечены теми же буквами, что и четыре части суши.
Утверждение о несуществовании «положительного» решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом граф, представленный на рисунке.
Отправляясь от этого частного случая, Эйлер обобщил постановку задачи и нашел критерий существования обхода (специального маршрута) у данного графа, а именно граф должен быть связным и каждая его вершина должна быть инцидентна (принадлежать) четному числу ребер.
Граф, показанный на рисунке, связный, но не каждая его вершина инцидентна (принадлежит) четному числу ребер.
Электрические цепи
В 1847 г. Кирхгоф разработал теорию деревьев для решения совместной системы линейных алгебраических уравнений, позволяющую найти значение силы тока в каждом проводнике (дуге) и в каждом контуре рассматриваемой электрической цепи.
Будучи физиком по образованию, он подходил к решению задач как математик. Абстрагируясь от электрических схем и цепей, которые содержат сопротивления, конденсаторы, индуктивности и т. д., он рассматривал соответствующие комбинаторные структуры, содержащие только вершины и связи (ребра или дуги), причем для связей не нужно указывать, каким типам электрических элементов они соответствуют.
Таким образом, в действительности Кирхгоф заменил каждую электрическую цепь соответствующим ей графом и показал, что для решения системы уравнений необязательно рассматривать в отдельности каждый цикл графа электрической цепи.
Рисунок 3. Сеть N, соответствующий ей граф G .
Вместо этого он предложил простую, но эффективную методику (ставшую позднее стандартной процедурой), в соответствии с которой достаточно ограничиться только независимыми простыми циклами графа, определяемыми любым из его «остовных деревьев». На рисунке 3 дан пример электрической цепи N, соответствующего ей графа G.
Химические изомеры
Занимаясь чисто практическими задачами органической химии, Кэли в 1857 г. открыл важный класс графов, называемых деревьями.
Он стремился перечислить изомеры предельных (насыщенных) углеводородов С n Н 2 n + 2 с данным числом n атомов углерода; рисунок 4.
Рисунок 4. Изобутан
В социальной психологии.
В 1936 г. психолог Курт Леви н высказал предположение, что «жизненное пространство» индивидуума можно представить с помощью планарной карты 1).
На такой карте области представляют различные типы деятельности человека, например, то, что он делает на работе, дома, или же его хобби.
Рисунок 5. Карта и соответствующий ей граф.
Подчеркнем, что К.Леви н фактически имел дело с графами, как это видно из рисунка 5.
Эта точка зрения привела психологов Научно-исследовательского центра групповой динамики к другой психологической интерпретации графа, в которой люди представляются вершинами, а их отношения - ребрами. Такими отношениями являются, например, любовь, ненависть, общение, подчинение.
Предположение Левина относится только к планарным картам, поскольку он всегда рисовал свои рисунки на плоскости. В последствии идея К.Левина была развита в социометрических процедурах.
В теории организаций
Графы могут быть представлены не только в строгой классической форме. Так жизненный цикл компании И.Адизеса представлен следующим форме.
Рисунок 6. Жизненный цикл компании
Функциональная организационная структура построена по принципу распределения функций внутри организации и создания сквозных подструктур по управлению функциями.
Производственные подразделения
Рис. Функциональная организационная структура
Таким образом, необходимость специальной общей теории, применимой в любой сфере жизнедеятельности человека была обусловлена потребностями практики.
Такой теорией стала «Теория графов».
Основные понятия теории графов
Начнём с определения, однозначного определения теория графов не имеет, ниже представлены три определения, но существуют и другие.
Теория графов - раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами.
Теория графов - раздел математики, особенность которого - геометрический подход к изучению объектов
Теория графов - математический язык для формализованного определения понятий, связанных с анализом и синтезом структур систем и процессов.
Исторически сложилось так, что теория графов зародилась двести с лишним лет назад именно в ходе решения головоломок. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре общего внимания.
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.
В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, нахождении максимального потока в сети, кратчайшего расстояния, максимального паросочетания, проверки планарности графа и др. Как особый класс можно выделить задачи оптимизации на графах. Математические развлечения и головоломки тоже являются частью теории графов, например, знаменитая проблема четырех красок, интригующая математиков и по сей день. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.
Теория графов дает простой и мощный инструмент построения моделей и решения задач упорядочения объектов. В настоящее время существует множество проблем, где требуется построить некоторые сложные системы с помощью определенного упорядочения их элементов. Сюда относятся календарное планирование промышленного производства, задачи теории сетевого планирования и управления, тактические и логические задачи, проблемы построения систем связи и исследования процессов передачи информации, выбор оптимальных маршрутов и потоков в сетях, методы построения электрических сетей, задачи идентификации в органической химии и способы переключения переключательных схем. Таким же является большой круг экономических задач, проблемы выбора структуры социальных групп и т.д. Таким образом, область возможных применений теории графов очень широка. Комбинаторные методы нахождения нужного упорядочения объектов существенно отличаются от классических методов анализа поведения систем с помощью уравнений. Кроме языка теории графов, задачи упорядочения объектов можно формулировать в терминах теории матриц с элементами ноль - один.
С полным основанием можно сказать, что теория графов является одним из простейших и наиболее элегантных разделов современной математики с широкой областью применения. Имея в своей основе простейшие идеи и элементы: точки, соединенные линиями, теория графов строит из них богатое многообразие форм, наделяет эти формы интересными свойствами и в результате становится полезным инструментом при исследовании самых разнообразных систем. Кроме того, теория графов внесла большой вклад в разработку методов анализа широкого круга комбинаторных проблем. Если помимо основных чисто структурных соотношений в графе задаются некоторые количественные характеристики точек и линий, образующих граф, тогда вместо понятий графа можно использовать понятие сеть. В качестве примеров можно назвать электрические сети, сети выполнения работ в проектах сети потоков. При этом ребром сети ставятся в соответствие определенные количественные характеристики энергии, затрат и потока.
вершин (узлов), соединённых рёбрами . В строгом определении графом называется такая пара множеств G = (V , E) {\displaystyle G=(V,E)} , где V {\displaystyle V} есть подмножество любого счётного множества , а E {\displaystyle E} - подмножество V × V {\displaystyle V\times V} .Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. - как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.
История возникновения теории графов
Родоначальником теории графов считается Леонард Эйлер . В 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 с.)