metod_15.03.04_atppp_moas_2016 (1016590), страница 10

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

Текст из файла (страница 10)

Таким образом, индукцияпроведена, и теорема доказана.На самом деле верно и обратное утверждение, которое является частьюболее общей теоремы, отражающей простейшие свойства дерева.Теорема. Следующие 4 условия равносильны:граф G является деревом;число ребер (т) и число вершин в графе (п) связаны соотноше-нием т = п – 1;любые две вершины в графе могут быть связаны (простым) путем, иэтот путь единствен;граф G связен и не содержит контуров.Заметим, что генеалогическое дерево (в котором вершины графа – это некоторый человек и его прямые предки, а смежные вершины – это люди, связанные родством: мать и ее ребенок или отец и его ребенок) деревом в смысле теории графов не является (так как оно обязательно должно содержать циклы: некоторые предки данного человека должны иметь общего предка).Однако игры с полной информацией (т.

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

Связав эти вершины ребрамитак, чтобы отсутствовали циклы, получим некоторое дерево, покрывающее данное множество вершин. Для двух вершин существует одно покрывающее дерево - сами вершины и ребро, их связывающее. С увеличениемных деревьевбыстро увеличивается:число различ-.Деревья считаются существенно различными, если они не изоморфны.Всего деревьев с четырьмя вершинами 16, из них существенно различныхтолько 2; деревьев с шестью вершинами 1296, а существенно различных всего6, но уже принасчитывается около миллиона существенно различных де-ревьев.. На рис. 4.34 приведены существенно различные деревья с четырьмя и сшестью вершинами:Среди графов n-го порядка (с n вершинами) без кратных ребер полныйграф имеет наибольшее количество ребер, а дерево (n-го порядка) - наименьшее.

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

◄Нетрудно убедиться в справедливости следующих теорем.Теорема 4.10. Граф является деревом тогда и только тогда, когда каж-дая пара различных вершин графа соединяется одной и только одной простойцепью.Теорема 4.11. У каждого дерева найдется висячая вершина.Теорема 4.12. При удалении любого ребра дерева оно распадается на связные компоненты, являющиеся либо изолированными вершинами, либо деревьями.

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

Назовем его концевые вершины-вершинами типа 1. Теперь удалим все вершины типа 1 и концевые ребра. В результате получим связный граф без циклов, то есть опять дерево, но с ужеменьшим количеством вершин. Концевые вершины дереванами типа 2 в деревеназовем верши-. Аналогично определяются вершины типов 3, 4 и т. д.Легко видеть, что дерево может иметь либо одну вершину максимального типа,либо две таких вершины.

Типы вершин дерева, изображенного на рис. 4. 37,записаны рядом с соответствующими вершинами. Здесь же показаны последовательные этапы процедуры, позволяющей их определить. Это дерево имеетдве вершины максимального типа. Если у дереваудалить одну из вершинтипа 2 и ребра, ей инцидентные, то получившееся при этом дерево будет иметьуже только одну вершину максимального типа.Пусть вершина типа k есть вершина максимального типа.

Из определения типа вершин дерева следует, что эксцентриситет единственной вершинымаксимального типа равен ее типу, то есть равен k, а эксцентриситет каждой издвух вершин максимального типа равен k-1. При этом эксцентриситет любойвершины не максимального типа будет обязательно больше. Поэтому центрамилюбого дерева являются его вершины максимального типа, следовательно, дерево имеет либо один, либо два центра. Нетрудно убедиться, что диаметральные цепи в деревьях проходят через его центр или через оба центра, если ихдва. В первом случае длина диаметральной цепи равна 2k-2, а во втором 2k-1.Результаты и методы теории графов применяются при решении транспортных задач о перевозках, для нахождения оптимальных решений задачи о назначениях, для выделения «узких мест» при планировании и управлении разработокпроектов, при составлении оптимальных маршрутов доставки грузов, а такжепри моделировании сложных технология, процессов, в построении различныхдискретных устройств, в программировании и т.

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

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

Любую из этих задач можно решить симплекс-методом, нокаждая специализация имеет свой более эффективный алгоритм, опирающийсяна особенности структуры задачи.Если целевая функция выражается через квадраты, говорят о квадратичной задаче о назначениях.Предположим, что таксомоторная компания имеет три свободные машины (исполнители), и три заказчика (работы), желающих получить такси какможно быстрее. Фирма заботится о времени доставки такси к заказчику, так чтодля каждой машины "стоимость" определяется скоростью, с какой машина доберётся до места ожидания, определённого заказчиком. Решением задачи оназначениях будет распределение машин по заказчикам, такое, что суммарнаяцена (суммарное время ожидания) минимально.Задачу о назначениях можно сделать более гибкой. В вышеприведенномпримере могут оказаться не три, а четыре свободных такси, но заказчика, попрежнему, три. Можно назначить четвертую задачу, которую можно назвать"сиди тихо, ничего не делай", с ценой 0 для машины, которой она назначается.Задача может быть решена обычным методом и снова даст наилучшее решение.Аналогичный приём можно использовать в случае, когда число заказовможет превышать число доступных машин, и машина может быть назначена навыполнение нескольких работ, а также когда работа может быть назначена нескольким исполнителям (например, если заказчик – группа, не помещающаясяв одно такси).

Можно также поставить задачу увеличения дохода, а не минимизацию цены.Формальная постановка задачи о назначениях:Даны два множества, A и T, одного размера и задана функция стоимости C : A × T → R.Необходимо найти биекцию f : A → T, такую, что целевая функция:минимальна.Обычно функция стоимости задается как квадратная матрица C, состоящая из вещественных чисел, так что целевую функцию можно записать в виде:Задача называется "линейной", поскольку и целевая функция, и ограничения содержат только линейные выражения.Задачу можно представить как задачу линейного программирования c целевой функциейи ограничениямидля,для,дляПеременная.представляет назначение исполнителя на работу , при-нимая значение 1 если исполнитель назначен на эту работу и 0 в противномслучае. В этой формулировке решение может и не быть целым, но всегда существует оптимальное решение с целыми значениями.

Характеристики

Список файлов учебной работы