Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
История возникновения теории графов.Основные понятия теории графов. Примеры использования теории графов. История возникновения теории графов. Мы частенько рисуем на листочках бумаги кружочки, квадратики, точки обозначая ими людей, населённые пункты, дела которые мы должны сделать и тому подобное, и соединяем их прямыми и ломаными линями, стрелочками которыми обозначаем связи между ними, отношения, последовательность действий и тому подобное. Такие схемы встречаются всюду под разными названиями: социограммы (в психологии), симплексы (в топологии), электрические цепи (в физике), диаграммы организации (в экономике), сети коммуникаций, генеалогические деревья и т.д. Д.Кёниг, предложил называть такие схемы "графами" и систематически изучать их свойства. В совершенно различных дисциплинах приходится использовать аналогичные теоремы; так, понятие "матрицы инциденций", введенное Кирхгофом для изучения электрических цепей, было привлечено А.Пуанкаре в топологию при создании его "analysis situs"; понятие "точки сочленения", с давних пор известное в социологии, впоследствии появилось в электронике; все примеры такого рода перечислить невозможно. Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной. В действительности такие основные понятия, как "цепь", "путь", "центр", будучи определены абстрактно, остаются в то же время неразрывно связанными с графической реальностью и легко распознаются, когда схема начерчена. Рассматривая теорию графов, мы не ставим целью дать в руки математическое средство, наша задача сформировать общее представление прежде всего о её прикладных возможностях в теории организации управления. Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, кибернетика, общая теория систем, общая теория организаций, генетика, психология, социология, экономика, антропология и лингвистика и другие науки. Эта теория тесно связана также со многими разделами математики, среди которых — теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ. Теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем. Теория графов «открывалась» независимо много раз: её с полным основанием можно считать разделом прикладной математики. В самом деле, наиболее раннее известное упоминание этой теории встречается в работах Эйлера, и хотя проблему, которой он занимался, можно рассматривать как обычную головоломку, псе же она возникла из практики. Последующие переоткрытия теории графов Кирхгофом и Кэли также уходят своими корнями в реальную действительность. Изучение Кирхгофом электрических цепей привело к разработке им основных понятий и получению ряда теорем, касающихся деревьев в графах. В свою очередь Кэли подошел к исследованию деревьев, решая задачи перечисления органических изомеров. Другой подход к графам, связанный с рассмотрением головоломок, был предложен Гамильтоном. После этого появилась знаменитая гипотеза четырёх красок, которая до сих пор пользуется широкой известностью. В наше столетие также было чрезвычайно много переоткрытий теории графов. Упомянем кратко некоторые из них, придерживаясь хронологического порядка. Задача о кёнигсбергских мостах Отцом теории графов (так же как и топологии) является Эйлер (1707—1782), решивший в 1736 г. широко известную в то время задачу, называвшуюся проблемой кёнигсбергских мостов. В городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке. Задача состояла в следующем: найти маршрут прохождении всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту. Легко, конечно, попытаться решить эту задачу эмпирически, производя перебор всех маршрутов, но все попытки окончатся неудачей. Вклад Эйлера в решение этой задачи заключается в том, что он доказал невозможность такого маршрута.
В Рисунок 1. Парк в городе Кенигсберге, 1736 г.
Рисунок 2. Граф к задаче о кенигсбергских мостах
Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост — линией (ребром), соединяющей соответствующие точки. Получился «граф». Этот граф показан на рисунке 2., где точки отмечены теми же буквами, что и четыре части суши. Утверждение о несуществовании «положительного» решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом граф, представленный на рисунке. Отправляясь от этого частного случая, Эйлер обобщил постановку задачи и нашел критерий существования обхода (специального маршрута) у данного графа, а именно граф должен быть связным и каждая его вершина должна быть инцидентна (принадлежать) четному числу ребер. Граф, показанный на рисунке, связный, но не каждая его вершина инцидентна (принадлежит) четному числу ребер.
Электрические цепи В 1847 г. Кирхгоф разработал теорию деревьев для решения совместной системы линейных алгебраических уравнений, позволяющую найти значение силы тока в каждом проводнике (дуге) и в каждом контуре рассматриваемой электрической цепи. Будучи физиком по образованию, он подходил к решению задач как математик. Абстрагируясь от электрических схем и цепей, которые содержат сопротивления, конденсаторы, индуктивности и т. д., он рассматривал соответствующие комбинаторные структуры, содержащие только вершины и связи (ребра или дуги), причем для связей не нужно указывать, каким типам электрических элементов они соответствуют. Таким образом, в действительности Кирхгоф заменил каждую электрическую цепь соответствующим ей графом и показал, что для решения системы уравнений необязательно рассматривать в отдельности каждый цикл графа электрической цепи.
Рисунок 3. Сеть N, соответствующий ей граф G. Вместо этого он предложил простую, но эффективную методику (ставшую позднее стандартной процедурой), в соответствии с которой достаточно ограничиться только независимыми простыми циклами графа, определяемыми любым из его «остовных деревьев». На рисунке 3 дан пример электрической цепи N, соответствующего ей графа G. Химические изомеры Занимаясь чисто практическими задачами органической химии, Кэли в 1857 г. открыл важный класс графов, называемых деревьями. Он стремился перечислить изомеры предельных (насыщенных) углеводородов Сn Н2n+2 с данным числом n атомов углерода; рисунок 4. Рисунок 4. Изобутан В социальной психологии. В 1936 г. психолог Курт Левин высказал предположение, что «жизненное пространство» индивидуума можно представить с помощью планарной карты 1). На такой карте области представляют различные типы деятельности человека, например, то, что он делает на работе, дома, или же его хобби.
1) 2)
Рисунок 5. Карта и соответствующий ей граф. Подчеркнем, что К.Левин фактически имел дело с графами, как это видно из рисунка 5. Эта точка зрения привела психологов Научно-исследовательского центра групповой динамики к другой психологической интерпретации графа, в которой люди представляются вершинами, а их отношения — ребрами. Такими отношениями являются, например, любовь, ненависть, общение, подчинение. Предположение Левина относится только к планарным картам, поскольку он всегда рисовал свои рисунки на плоскости. В последствии идея К.Левина была развита в социометрических процедурах. В теории организаций Графы могут быть представлены не только в строгой классической форме. Так жизненный цикл компании И.Адизеса представлен следующим форме.
Рисунок 6. Жизненный цикл компании
Функциональная организационная структурапостроена по принципу распределения функций внутри организации и создания сквозных подструктур по управлению функциями.
Производственные подразделения Рис. Функциональная организационная структура
Таким образом, необходимость специальной общей теории, применимой в любой сфере жизнедеятельности человека была обусловлена потребностями практики. Такой теорией стала «Теория графов».
Основные понятия теории графов Начнём с определения, однозначного определения теория графов не имеет, ниже представлены три определения, но существуют и другие. Теория графов - раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Теория графов - раздел математики, особенность которого - геометрический подход к изучению объектов Теория графов - математический язык для формализованного определения понятий, связанных с анализом и синтезом структур систем и процессов. Мы остановимся на следующем: |
|
Последнее изменение этой страницы: 2016-08-28 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |