Понятие ориентированного графа. Его основные структуры

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

Родоначальником теории графов является Леонард Эйлер (1707 - 1782).

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

Река Преголь

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

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

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

В 1857 году Келли открыл важный класс графа - деревья. Он стремился перечислить число изомерных предельных углеводородов СnH2n+2

В 1869 Жордан независимо от Келли ввел и изучал деревья, как отдельные математические объекты. С того времени можно считать, что теория графов возникла как самостоятельная математическая дисциплина.

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

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) Для орграфов цепь называется путем, а цикл – контуром.

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) Множество центральных вершин называется центром графа.

Понятие неориентированного графа. Его основные структуры.

Граф, или неориентированный граф — это упорядоченная пара, для которой выполнены следующие условия:

— это непустое множество вершин, или узлов,

— это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

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

Вершины и рёбра графа называются также элементами графа, число вершин в графе — порядком, число рёбер — размером графа.

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

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

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть.

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

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (и ли листом), если она является концом ровно одного ребра

Степени и полустепени вершин. Теорема Эйлера о рукопожатии.

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

Доказательство этой теоремы начнем с так называемой леммы о рукопожатиях. Название этой леммы связано с тем, что эта лемма отвечает на следующий вопрос: У Вас собрались гости. Некоторые из них здороваются друг с другом посредством рукопожатий. Какими свойствами обладает число таких людей? Ответ дается следующей достаточно простой леммой.

Лемма о рукопожатиях. Число вершин в графе (или мультиграфе без петель), имеющих нечетную степень, четно.

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

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

Гамильтоновы графы

Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.

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

Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.

Условия существования

Необходимое условие

Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины x(i) с локальной степенью p(x(i)) < 2. Доказательство следует из определения.

Параметры сетевых моделей

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

При расчетах применяют следующие обозначения параметров сетевой модели:

tjp — ранний срок свершения j-го события;

tjn — поздний срок свершения j-го события;

Rj — резерв времени на свершение j-го события;

tijP.H — ранний срок начала работы (i, j);

tijP.O — ранний срок окончания работы (i, j);

tijП.H — поздний срок начала работы (i, j);

tijП.О — поздний срок окончания работы (i, j);

rijП — полный резерв времени работы (i, j);

rijC.B — свободный резерв времени работы (i, j),

kijH — коэффициент напряженности работы (i, j);

ТП — продолжительность пути LП; TП = t(LП);

TКР — продолжительность критического пути LКР;

R(Lп) — полный резерв времени пути Lп.

Рассмотрим определения и модели расчета параметров сетевой модели.

Ранний срок свершения j-го события tjp — наиболее ранний (минимальный) из возможных моментов наступления данного события при заданной продолжительности работ.

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

Резерв времени на свершение j-го события Rj — это промежуток времени, на который может быть отсрочено наступление события j без нарушения сроков завершения всего комплекса, определяется как разность между поздним tjn и ранним tjp сроками наступления события Rj = tjn - tjp.

Ранний срок начала работы tijP.H — наиболее ранний (минимальный) из возможных моментов начала данной работы при заданной продолжительности работ. Он совпадает с ранним сроком наступления ее начального события:

tijP.H= tjp

Ранний срок окончания работы tijP.O — наиболее ранний (минимальный) из возможных моментов окончания данной работы при заданной продолжительности работ. Он превышает ранний срок наступления ее события i на величину продолжительности работы:

tijP.O= tiP+tij

Поздний срок начала работы tijП.H — наиболее поздний (максимальный) из допустимых моментов начала данной работы, при котором еще возможно выполнение всех последующих работ в установленный срок:

tijП.H= tjП-tij

Поздний срок окончания работы tijП.О — наиболее поздний (максимальный) из допустимых моментов окончания данной работы, при котором еще возможно выполнение последующих работ в установленный срок:

tijП.О= tjП

Полный резерв времени работы (i, j) rijП — максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы ttj без изменения общего срока выполнения комплекса:

rijП = tjП -tiP-tij

Свободный резерв времени работы (i, j) rijC.B — максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы при условии, что все события сети наступают в свои ранние сроки:

rijC.B= tjP- tiP-tij

Полный резерв времени пути R(Lп), — показывает, на сколько могут быть увеличены продолжительности всех работ в сумме пути Ln относительно критического пути LKP:

R(Lп)=t(LKP)-t(LП)=TKP-TП

Коэффициент напряженности работы (i, j) kijH — характеризует напряженность по срокам выполнения работы (i, j) и определяется по формуле:

kijH = (t(Lmax) - t'(Lkp)/(Tkp - t'(Lkp))

где t(Lmax) - длительность максимального из некритических путей, проходящих через работу (i, j); t'(Lkp) - продолжительность части критических работ, входящих в рассматривыемый путь Lmax.

Чем ближе коэффициент напряженности к 1, 0, тем сложнее выполнять эту работу в установленные сроки.

Методы расчета параметров сетевой модели делятся на две группы.

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

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

Анализ сетевых моделей

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

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

Анализ сетевой модели начинаем с определения минимального времени выполнения всего комплекса работ. Для этой цели проследим все возможные пути перехода из одного события (0) к завершающему (9). Таких путей четыре:

L1 = [(0, 1) (1, 2) (2, 4) (4, 6) (6, 8) (8, 9)]

L2 - [(0, 1) (1, 3) (3, 5) (5, 6) (6, 8) (8, 9)]

L3 = [(0, 1) (1, 3) (3, 5) (5, 6) (8, 9)]

L4 - [(0, 1) (1, 3) (3, 5) (5, 7) (7, 8) (8, 9)]

Определим длительность этих путей:

Т1 = t(L1) = t0, 1 + t1, 2 + t2, 4 + f4, 6+ t6, 8 + t8, 9 = 16 + 16 + 6 + 8 + 2 + 3 = 50 дн.

Т2 = t(L2) = t0, 1 + t1, 3 + t3, 5 + f5, 6+ t6, 8 + t8, 9 =15 + 6 + 5 + 6 + 2 + 3=37дн.

Т3 = t(L3) = t0, 1 + t1, 3 + t3, 5 + f5, 6+ t8, 9 = 15 + 6 + 5 + 14 + 3 = 43 дн.

Т4 = t(L4) = t0, 1 + t1, 3 + t3, 5 + f5, 7+ t7, 8 + t8, 9 = 15+ 6 + 5 + 8 + 4 + 3 = 41 дн.

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

ТКР = max {t(Li)} = 50 дн.

Длительность пути L2 составляет t(L2) = 37 дней минимальна, однако не позволяет выполнить все работы комплекса.

Длительность пути L2 составляет t(L2) - 50 дней, однако за это время все работы комплекса могут быть выполнены. Следовательно, минимальное время, за которое может быть выполнен весь комплекс работ, составляет 50 дней, следовательно, путь L1 является критическим.

Теперь определим полные резервы времени по всем путям:

R(L1)=TKP-T1=0

R(L2)=TKP-T2= 13 дн.

R(L3)=TKP-T3 = 7дн.

R(L4)=TKP-T4=9дн.

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

Построение начинается с критического пути LKP в соответствии с правилами сетевого моделирования по графику событий с учетом изображения длительностей работ tij в масштабе времени по оси абсцисс. По оси ординат длины стрелок выбираются из соображений удобства восприятия топологии сети в целом. Этим объясняется большая длина стрелки работы (6, 8) в сравнении с работой (4, 6), хотя по масштабу времени длительность t4, 6 больше t6, 8.

Длительность всех остальных путей T2, Т3, Т4 меньше, поэтому вводим фиктивные события 5', 8', 7' и фиктивные работы (5', 6), (8', 8), (7', 8) с нулевой продолжительностью.

В результате мы получили полную картину расположения мест свободных резервов времени работ r5, 6C.B =13 дням, r5, 8C.B = 7 дням r7, 8C.B =9 дням. Наиболее напряженными являются работы критического пути L1, которые не имеют резервов и поэтому являются «узкими местами» комплекса работ.

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

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

Метод ветвей и границ

Основные понятия динамического программирования

Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

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

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

Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

Слово «программирование» в словосочетании «динамическое программирование» в действительности к " традиционному" программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

Основные понятия производственных функций. Их экономический смысл.

Производственная функция, также функция производства — экономико-математическая количественная зависимость между величинами выпуска (количество продукции) и факторами производства, (затраты ресурсов, уровень технологий и др.) может выражаться как множество изоквант.[1]

Агрегированная производственная функция может описывать объёмы выпуска народного хозяйства в целом.

В зависимости от анализа влияния факторов производства на объём выпуска в определённый момент времени или в разные промежутки времени производственные функции делятся на статические: и динамические

ПРОИЗВОДСТВЕННАЯ ФУНКЦИЯ — экономико-математическая зависимость в форме связи между количеством производимой продукции и факторами производства, в качестве которых в этой функции рассматриваются труд и капитал. П.Ф. чаще всего представляется в виде степенной зависимости между объемом производства Q и факторами производства в виде капитала К и труда L, имеющей вид Q-AKaLb, где А — постоянный коэффициент, а и b — показатели степени, характеризующие отдачу, использование каждого из двух основных видов ресурсов.

Понятие функции полезности.

Фу́ нкция поле́ зности — экономическая модель для определения предпочтений экономических субъектов. Основополагающим условием концепта функции полезности является рациональное поведение потребителя, выражающееся в выборе из многочисленных альтернатив именно тех, которые выводят его на более высокий уровень полезности. В микроэкономике концепт функции полезности служит для объяснения поведения потребителей и производителей, в то время как в макроэкономике им пользуются для изображения предпочтений государственных интересов. Первая производная функции полезности по количеству определённого блага называется предельной полезностью этого блага. Предельная полезность выражает, сколько дополнительной полезности приносит дополнительная единица блага. Предельная полезность, равная 0, означает достижение насыщенности.

Большинство функций полезности, рассматриваемых в экономике, имеют отрицательную вторую производную — закон убывающей предельной полезности.

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

Понятие линий безразличия. Бюджетное множество

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