WWW.NAUKA.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, издания, публикации
 


«Теория Графов Alexander Lazarev Institute of Control Sciences of Russian Academy of Sciences 2009-2010 учебный год Элементы теории графов Outline Элементы теории графов Степени вершин О ...»

Элементы теории графов

Теория Графов

Alexander Lazarev

Institute of Control Sciences of Russian Academy of Sciences

2009-2010 учебный год

Элементы теории графов

Outline

Элементы теории графов

Степени вершин

О машинном представлении графов

Поиск в графе

Поиск в глубину в графе

Поиск в ширину в графе

Пути и циклы

Связность

Деревья

Остовное дерево (каркас)

Эйлеровы пути и циклы

Aлгоритм построения эйлерова цикла

Гамильтоновы пути и циклы

Нахождение кратчайших путей в графе

Максимальный поток в сети Минимальное остовное дерево Сортировка данных Элементы теории графов Элементы теории графов Задача о кёнигсбергских мостах. Однажды великому математику Леонарду Эйлеру был задан вопрос: можно ли обойти все семь мостов, стоявших тогда в городе Кёнигсберге (современный Калининград, Россия), побывав на каждом по одному разу?

Элементы теории графов Элементы теории графов Элементы теории графов Леонард Эйлер (нем. Leonhard Euler; 4 (15) апреля 1707, Базель, Швейцария - 7 (18) сентября 1783, Санкт-Петербург, Российская империя) - российский и швейцарский математик, внёсший значительный вклад в развитие математики, а также механики, физики, астрономии и ряда прикладных наук.

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

Элементы теории графов Почти полжизни провёл в России, где внёс существенный вклад в становление российской науки. В 1726 году он был приглашён работать в Санкт-Петербург. В 1731 1741 и, начиная с 1766 года, был академиком Петербургской Академии Наук (в 1741 1766 годах работал в Берлине, оставаясь почётным членом Петербургской Академии). Хорошо знал русский язык и часть своих сочинений (особенно учебники) публиковал на русском. Первые русские академики-математики (С. К.

Котельников) и астрономы (С. Я. Румовский) были учениками Эйлера. Некоторые из его потомков до сих пор живут в России.

Элементы теории графов Рассмотрев эту задачу, в 1736 году Эйлер доказал, что это невозможно, причем он рассмотрел более общую задачу: какие местности, разделенные рукавами рек и соединенные мостами, возможно обойти, побывав на каждом мосту ровно один раз, а какие невозможно.

Элементы теории графов Элементытеории графов Проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 г.

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

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

Элементы теории графов Граф G = V, E есть совокупность множества вершин V и множества рёбер (дуг), причем E V V есть множество упорядоченных пар x, y для ориентированного графа и E {{x, y } : (x, y V )&(x = y )} для неориентированного графа (при этом для неориентированного графа считаем, что ребра {a, b} и {b, a} совпадают {a, b} = {b, a}).

Граф неориентированный, если все его ребра не ориентированы, и граф ориентированный, если все его ребра ориентированы.

Элементы теории графов Ребро ориентированного графа мы обозначаем символом x, y ; ребро неориентированного графа обозначается символом {x, y }. В случае, когда несущественно, о каком ребре идет речь, или когда это ясно из контекста, будем произвольное ребро графа обозначать символом (x, y ).

Говорят, что ребро e E инцидентно вершинам x и y, x, y V, а так же, что x и y инцидентны ребру e.

Вершины x и y графа смежны, если (x, y ) является ребром.

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

Вершина, не инцидентная никакому ребру, называется изолированной.

Элементы теории графов Два графа G = V, E и G = V, E изоморфны, если существует такое взаимно-однозначное соответствие между множествами их вершин V и V, что вершины соединены ребрами в одном графе тогда и только тогда, когда соответствующие им вершины соединены в другом графе.

Если V V и при этом соответствии x x, y y, то (x, y ) E тогда и только тогда, когда (x, y ) E ((x, y ) E (x, y ) E ).

Элементы теории графов Элементы теории графов Пусть G – неориентированный граф. Число (x) ребер, инцидентных вершине x, называется локальной степенью, или просто степенью вершины x графа G. В каждом случае должно быть указано, считается петля однократной или двойной.

Пусть (x, y ) = (y, x) – число ребер, соединяющих вершины x и y.

–  –  –

В теории графов классическим способом представления графа служит матрица инциденций. Для графа G = V, E – это матрица I (G ) с n строками, соответствующими вершинам, |V | = n, и с m столбцами, |E | = m, соответствующими ребрам.

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

Элементы теории графов

О машинном представлении графов

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

Требуется m n ячеек памяти. Доступ неудобен. Ответ на элементарные вопросы типа:

"существует ли ребро x, y ?";

"к каким вершинам ведут ребра из x?" требует перебора всех столбцов матрицы.

Элементы теории графов

О машинном представлении графов

Более удобным способом представление графа является матрица смежности (вершин), определяемая как матрица B = ||bij || размера n n, где bij = 1, если существует ребро, ведущее из вершины i в вершину j, bij = 0 в противном случае. Здесь мы подразумеваем, что ребро {i, j} неориентированного графа идет как от i к j, так и от j к i, так что матрица смежности такого графа всегда является симметричной. Ответ на вопрос типа:

"{x, y } E ?"может быть получен за один шаг.

Недостаток такого способа представления графа n n ячеек занятой памяти независимо от числа ребер.

Элементы теории графов

О машинном представлении графов

Более экономным в отношении требуемого объема памяти (особенно для неплотных графов m n) является метод представления графа с помощью списка пар. Пара (x, y ) соответствует ребру x, y, если граф ориентированный, и ребру {x, y }, если граф неориентированный. Очевидно, что объем памяти в этом случае составляет 2m ячеек.

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

Элементы теории графов

О машинном представлении графов

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

Она содержит для каждой вершины v V список вершин u, таких что v, u E (или {v, u} E в случае неориентированного графа).

Элементы теории графов Поиск в графе

–  –  –

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

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

1) он позволяет легко применить этот метод в алгоритме решения задачи ("погрузить" алгоритм решения нашей задачи в этот метод);

2) каждое ребро графа анализируется не более одного раза (или, что существенно не меняет ситуации, число раз, ограниченное константой, не зависящей от |V | и |E |).

Элементы теории графов Поиск в графе

–  –  –

Мы начинаем поиск с некоторой фиксированной вершины v0.

Затем выбираем произвольную вершину u, смежную с v0, (v0, u) E, и повторяем процесс от u. В общем случае предположим, что мы находимся в вершине v. Если существует новая (еще "непросмотренная") вершина u, (v, u) E, то мы рассматриваем эту вершину (она перестает быть новой) и, начиная с нее, продолжаем поиск. Если же не существует ни одной новой вершины, смежной с v, то мы говорим, что вершина v использована, возвращаемся в вершину, из которой мы попали в v, и продолжаем процесс (если v = v0, то поиск закончен). Таким образом, поиск в глубину из вершины v основывается на поиске в глубину из всех новых вершин, смежных с v.

Элементы теории графов Поиск в графе

–  –  –

5 end. {вершина v использована} Элементы теории графов Поиск в графе Покажем теперь, что этот алгоритм просматривает каждую вершину в точности один раз и его сложность порядка O(n + m). Вызов ПОИСК В ГЛУБИНУ В ГРАФЕ G (v ) влечет за собой просмотр всех вершин связной компоненты графа, содержащей v (если НОВЫЙ[u] = истина для каждой вершины u этой компоненты). Это непосредственно следует из структуры процедуры ПОИСК В ГЛУБИНУ В ГРАФЕ G (v ): после посещения вершины (строка 2) следует вызов процедуры для всех ее новых соседей. Каждая вершина графа просматривается не более одного раза, так как просматриваться может только вершина v, для которой НОВЫЙ[v ] = истина, сразу же после посещения этой вершины исполняется присваивание НОВЫЙ[v ] := ложь (строка 2 процедуры).

Элементы теории графов

Поиск в графе

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

Чтобы оценить сложность алгоритма, отметим сначала, что число шагов в обоих циклах (строки 2 и 3 алгоритма) порядка n, не считая шагов, выполнение которых инициировано вызовом процедуры ПОИСК В ГЛУБИНУ В ГРАФЕ G. Эта процедура выполняется не более n раз во втором цикле сразу после посещения каждой вершины для каждого из ее новых соседей, итого суммарно O(n + m) раз. Полное число шагов, выполняемое циклом в строке 3 процедуры ПОИСК В ГЛУБИНУ В ГРАФЕ G, для всех вызовов этой процедуры будет порядка m, где m – число ребер. Это дает общую сложность алгоритма O(n + m).

Элементы теории графов

Поиск в графе

В связи с тем, что поиск в глубину играет важную роль в проектировании алгоритмов на графах, представляет интерес нерекурсивная версия процедуры ПОИСК В ГЛУБИНУ В ГРАФЕ G. Рекурсия устраняется стандартным способом при помощи стека. Каждая просмотренная вершина помещается в стек и удаляется из стека после ее использования.

Элементы теории графов Поиск в графе

–  –  –

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

Использование вершины происходит с помощью просмотра всех еще непросмотренных соседей этой вершины.

Элементы теории графов Поиск в графе

–  –  –

11 end. {вершина v использована} Элементы теории графов Поиск в графе Способом, аналогичным тому, который был применен для поиска в глубину, можно легко показать, что вызов процедуры ПОИCК В ШИРИНУ В ГРАФЕ G (v ) приводит к посещению всех вершин связной компоненты графа, содержащей вершину v, причем каждая вершина просматривается в точности один раз. Вычислительная сложность алгоритма поиска в ширину также имеет порядок O(m + n), так как каждая вершина (всего n вершин) помещается в очередь и удаляется из очереди в точности один раз, а число итераций цикла 6, очевидно, будет иметь порядок числа ребер (всего m ребер) графа.

Элементы теории графов Пути и циклы

–  –  –

Путем в ориентированном или неориентированном графе G = V, E называют последовательность ребер вида (v1, v2 ), (v2, v3 ),...(vn1, vn ) = S = e1,..., en1, где ei = (vi, vi+1 ) E, ei и ei+1 инцидентны одной вершине, i = 1, n 1. Говорят, что этот путь идет из v1 в vn и имеет длину n 1. Часто такой путь представляют последовательностью вершин v1,..., vn, vi, vi+1 E, лежащих на нем. В вырожденном случае одна вершина обозначает путь длины 0, идущий из этой вершины в нее же.

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

Элементы теории графов

Пути и циклы

Цикл это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине. В неориентированном простом графе длина цикла должна быть не менее 3.

Оба вида поиска в графе – в глубину и в ширину – могут быть использованы для нахождения пути между фиксированными вершинами v и u. Достаточно начать поиск в графе с вершины v и вести его до момента посещения вершины u.

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

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

Элементы теории графов Пути и циклы

–  –  –

11 end. {вершина v использована} Элементы теории графов Пути и циклы По окончании работы модифицированной процедуры ПОИCК В ШИРИНУ В ГРАФЕ массив ПРЕДЫДУЩИЙ содержит для каждой просмотренной вершины u вершину ПРЕДЫДУЩИЙ[u], из которой мы попали в u. Кратчайший путь из исходной вершины v до каждой вершины из массива ПРЕДЫДУЩИЙ.

Элементы теории графов Связность

–  –  –

Пусть граф G неориентированный. Две вершины a и b называются связанными, если существует путь S с начальной вершиной a и конечной вершиной b, S = a, a1,..., an, b. Если S проходит через какую-нибудь вершину ai более одного раза, то можно, очевидно, удалить его циклический участок и при этом остающиеся ребра будут составлять путь S из a в b.

Отсюда следует, что связанные путем вершины связаны и простым путем. Граф называется связным, если любая его пара вершин связана.

Элементы теории графов Связность

–  –  –

на попарно непересекающиеся подмножества вершин Vi, что вершины в каждом Vi связаны, а вершины из различных Vi не связаны. Граф состоит из k непересекающихся связных подграфов k компонентов связанности.

Элементы теории графов Связность Теорема 3.2. Если в конечном неориентированном простом графе G ровно две вершины a и b имеют нечетную локальную степень, то они связаны.

Доказательство. По теореме 3.1, каждый конечный граф имеет четное число вершин нечетной степени. Так как это условие выполняется и для той компоненты G, которой принадлежит a, то b принадлежит той же компоненте связности.

Элементы теории графов Связность Теорема 3.3. Если неориентированный простой граф G имеет n вершин и k связных компонент, то максимальное число ребер в G равно

–  –  –

Это число достигается, когда каждый из графов Gi полный и имеет ni вершин. Допустим, что среди графов Gi найдутся хотя бы два графа G1, G2, которые имеют более одной вершины, например n2 n1 1. Построим вместо G другой граф G с тем же числом вершин и компонент, заменяя G1 и G2 полными графами G1 и G2 соответственно с n1 1 и n2 + 1 вершинами.

Общее количество вершин не изменилось.

Элементы теории графов Связность

–  –  –

Число ребер увеличилось на (n2 n1 ) + 1 0.

Элементы теории графов Связность Таким образом максимальное число ребер должен иметь граф, состоящий из k 1 изолированных вершин и одного полного графа с n k + 1 вершинами.

–  –  –

Связный неориентированный граф называется деревом, если он не имеет циклов. Дерево не имеет петель и кратных ребер.

Граф без циклов есть граф, связные компоненты которого являются деревьями лес.

Любая связанная компонента дерева будет также деревом.

Элементы теории графов Деревья Теорема 3.5. В дереве любые две вершины связаны единственным простым путем.

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

Элементы теории графов Деревья Наглядное представление для произвольного дерева T = V, E можно получить при помощи следующей конструкции. Выберем произвольную вершину a0 и будем рассматривать ее как корень дерева или вершину нулевого уровня. Затем "потрясём" дерево.

Будем называть вершину a дерева концевой, если (a) = 1.

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

Элементы теории графов

Деревья

Утверждение 3.6. Любое нетривиальное конечное дерево имеет хотя бы две концевые вершины и хотя бы одно концевое ребро.

Теорема 3.7.

Каждое дерево с n вершинами имеет n 1 ребро.

Доказательство. Доказательство легко проводится индукцией по числу вершин. Для n = 1 утверждение, очевидно, справедливо. Пусть n 1. Тогда в дереве существует концевая вершина v. Удаляя из дерева v и ребро (u, v ), инцидентное v, получим дерево с n 1 вершиной, которое в силу индуктивного предположения имеет n 2 ребра. Следовательно, первоначальное дерево имеет n 2 + 1 = n 1 ребро.

Элементы теории графов Деревья

–  –  –

Деревья Доказательство. Обозначим элементы данного множества V, расположенные в некотором фиксированном порядке, числами V = {1, 2,..., n}.

Для любого дерева T, определенного на V, введем некоторый символ, характеризующий его однозначно. В T существуют концевые вершины. Обозначим через b1 первую концевую вершину в последовательности V = {1, 2,..., n}, а через e1 = {a1, b1 } – соответствующее концевое ребро. Удалив из T ребро e1 и вершину b1, мы получим новое дерево T1. Для T1 найдется первая в списке V = {1, 2,..., n} концевая вершина b2 с ребром e2 = {a2, b2 }. Эта редукция повторяется до тех пор, пока после удаления ребра en2 = {an2, bn2 } не останется единственное ребро en1 = {an1, bn1 }, соединяющее две оставшиеся вершины.

Элементы теории графов Деревья Список (T ) = [a1, a2,..., an2 ] однозначно определяются деревом T и двум различным деревьям T и T, соответствуют разные символы такого вида. Каждая вершина ai появляется в (ai ) 1 раз.

(T ) Элементы теории графов Деревья Последовательность (T ) однозначно определяет дерево T с помощью обратного построения. Если дана последовательность (T ), то находится первая вершина b1 в списке V = {1, 2,..., n}, которая не содержится в (T ). Это определяет ребро e1 = {a1, b1 }. Далее удаляем вершины a1 из последовательности (T ) и b1 из списка V = {1, 2,..., n} и продолжаем построение для оставшихся элементов.

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

После удаления e1 последовательность (T ) будет содержать n 3 элемента. Если она соответствует дереву T1, то граф T, получаемый из него добавлением e1, также есть дерево, так как вершина b1 не принадлежит T1. B (T ) каждая вершина может принимать все n возможных значений. Все они соответствуют различным деревьям, откуда и получается формула tn = nn2.

Элементы теории графов Деревья

–  –  –

Для связного неориентированного графа G = V, E без петель каждое дерево V, T, содержащее все вершины графа G, где T E, будем называть остовным деревом (каркасом) графа G.

Элементы теории графов Деревья Напомним, что длина пути есть количество составляющих его ребер.

Процедуры поиска в глубину и в ширину можно простым способом использовать для нахождения остовных деревьев. В обоих случаях достижение новой вершины u из вершины v вызывает включение в дерево ребра (v, u).

Элементы теории графов Деревья

–  –  –

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

1) В момент добавления к множеству T нового ребра (v, u) в строке 5 в V, T существует путь из r в v (этот факт легко доказывается по индукции). Таким образом, алгоритм строит связный граф.

2) Каждое новое ребро (v, u), добавляемое ко множеству T, соединяет уже рассмотренную вершину v (т.е. НОВЫЙ[v ] = ложь) с новой вершиной u. Отсюда следует, что построенный граф V, T не содержит циклов. Последнее ребро, "замыкающее" цикл, должно было бы соединить две уже рассмотренные вершины.

3) Из свойства поиска в глубину следует, что процедура КАРКАС ГЛУБИНА просматривает все вершины связного графа.

Элементы теории графов Деревья Следовательно, граф V, T, построенный нашим алгоритмом, есть остовное дерево графа G. Вычислительная сложность алгоритма есть, очевидно, O(n + m), т.е. того же порядка, что и сложность поиска в глубину.

Элементы теории графов Деревья

–  –  –

Деревья Алгоритм построения остовного дерева методом поиска в ширину корректно строит остовное дерево для призвольного связного графа за O(n + m) шагов.

Элементы теории графов Деревья Вершину r, из которой начинается поиск, назовем корнем остовного дерева. Для двух различных вершин v и u дерева V, T будем говорить, что u является потомком вершины v, если v лежит на пути (в дереве V, T ) из вершины u в вершину v.

Элементы теории графов Деревья Теорема 3.9. Пусть V, T – остовное дерево связного неориентированного графа G = V, E, построенное с помощью алгоритма В ГЛУБИНУ, и пусть (u, v ) E. Тогда либо u – потомок v, либо v – потомок u.

Теорема 3.10.

Пусть V, T – остовное дерево связного неориентированного графа G = V, E, построенное с помощью алгоритма В ШИРИНУ. Тогда путь в V, T из произвольной вершины v до корня r является кратчайшим путем из v в r в графе G.

Элементы теории графов Эйлеровы пути и циклы

–  –  –

Очевидно, не существует циклических обходов, проходящих по всем ребрам (мостам) по одному разу.

Элементы теории графов Эйлеровы пути и циклы Эйлеровым путем в графе G = V, E называется произвольный путь, проходящий через каждое e E ребро графа в точности один раз, т.е. каждое ребро появляется в последовательности S = v1,..., vm+1 в точности один раз как e = {vi, vi+1 } для каждого i.

Если v1 = vm+1, то такой путь называется эйлеровым циклом.

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

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

Элементы теории графов Эйлеровы пути и циклы Доказательство.

Условие связности, очевидно, необходимое условие.

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

Предположим теперь, что эти два условия выполнены.

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

Элементы теории графов

Эйлеровы пути и циклы

Пусть P содержит не все рёбра графа G.

Графы P и G имеют четные степени вершин, то же будет справедливо и для остающегося графа P.

Так как граф G связен, в должна найтись вершина b, инцидентная также ребрам из P. Из b построим новый путь P, содержащий ребра только из P. Снова такой путь может закончится только при возвращении в b. Но тогда из P и P составим новый путь P1 P1 = P(a, b) P P(b, a), который возвращается в и содержит больше ребер, чем P.

Если P1 не является эйлеровым циклом (не все рёбра включены в цикл), то это построение повторяется. Когда процесс закончится, эйлеров цикл будет построен.

Элементы теории графов Эйлеровы пути и циклы

–  –  –

Эйлеровы пути и циклы Оценим вычислительную сложность алгоритма. Для этого отметим, что каждое повторение главного цикла либо помещает вершину в стек ПУТЬ и удаляет ребро из графа, либо переносит вершину из стека ПУТЬ в стек ЦИКЛ. Таким образом, число итераций этого цикла (и всего алгоритма) – O(m), где m – число рёбер.

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

Слово "гамильтонов" связано с именем известного ирландского математика У. Гамильтона, который в 1859 г.

предложил игру "Кругосветное путешествие".

Элементы теории графов

Гамильтоновы пути и циклы

ГАМИЛЬТОН Уильям Роуан (Hamilton William Rowan) (4.8.1805-2.9.1865) – ирландский математик, член Ирландской Академии Наук. Родился в Дублине. В 3 года Гамильтон умел читать, неплохо знал арифметику и географию, в 10 лет стал студентом, к 12 годам изучил 12 языков. Достав латинский перевод "Начал" Евклида, он изучил это сочинение с 13 до 17 лет, изучал сочинения И. Ньютона и П.Лапласа. Окончил Тринити-колледж Дублинского университета, в 22 года стал профессором астрономии в Дублинском университете и директором университетской астрономической обсерватории.

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

Гамильтон ввел термины "вектор", "ассоциативный закон".

Известны работы Гамильтона в геометрии (где он занимался теорией волновых поверхностей) и алгебре. Гамильтон и Кэли разработали теорию матриц.

Элементы теории графов

Гамильтоновы пути и циклы

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

Элементы теории графов

Гамильтоновы пути и циклы

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

Элементы теории графов Доказательство. Пусть S = a0,..., ak – некоторый простой путь длины k в графе G = V, E. Выделим подграф G0 = S, E, содержащий все вершины и рёбра данного пути.

Пусть (a0, ai ) – некоторое ребро в графе G0. Если существует также ребро (ak, ai1 ), то в G0 будет гамильтонов цикл, а именно

–  –  –

Гамильтоновы пути и циклы Если 0 (ak ) k 0 (a0 ), где 0 (a0 ) и 0 (ak ) степени вершин a0 и ak в графе G0, то хотя бы для одного ребра (a0, ai ) должно существовать соответствующее ребро (ak, ai1 ). Поэтому если 0 (a0 ) + 0 (ak ) k + 1, то простой путь S будет иметь тип цикла.

Элементы теории графов Гамильтоновы пути и циклы Теорема 3.14. Максимальный простой путь в связном графе может иметь тип цикла только тогда, когда граф имеет гамильтонов цикл.

Доказательство.

1). Если G имеет гамильтонов цикл, то максимальный простой путь длины n 1 имеет тип цикла.

2). Если подграф G0, соответствующий максимальному простому пути имеет гамильтонов цикл, но G0 не составляет всего графа, то из-за связности G существует некоторое ребро (ai, b), в котором b не принадлежит G0. Это, однако, невозможно так как тогда нашелся бы простой путь, который был бы длиннее данного простого пути S.

Элементы теории графов Гамильтоновы пути и циклы Теорема 3.15. В связном графе либо имеется гамильтонов цикл, либо длина его максимальных простых путей удовлетворяет неравенству

–  –  –

для всех пар вершин a0 и ak.

Элементы теории графов Гамильтоновы пути и циклы Теорема 3.16. В графе без гамильтоновых циклов длина его максимальных простых путей k удовлетворяет неравенству k 1 + 2, где 1 и 2 две наименьшие степени вершин.

Элементы теории графов Гамильтоновы пути и циклы В графе с n вершинами максимальный простой путь имеет длину, не превышающую n 1.

Теорема 3.17.

Если в графе G с n вершинами для любой пары вершин a0 и ak имеет место соотношение (a0 ) + (ak ) n 1, то граф G имеет гамильтонов путь.

Если (a0 ) + (ak ) n, то G имеет гамильтонов цикл.

Элементы теории графов Гамильтоновы пути и циклы Результат Дирака: граф с n вершинами имеет гамильтонов цикл, если для каждой его вершины (a) n.

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

Случаи, когда k = 2 или k = 3 в теории графов имеют особую роль.

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

Элементы теории графов Гамильтоновы пути и циклы

Свойства 2-связных графов:

степени вершин двусвязного графа больше единицы;

Элементы теории графов Гамильтоновы пути и циклы

Свойства 2-связных графов:

степени вершин двусвязного графа больше единицы;

если графы G1 и G2 2-связны и имеют не менее двух общих вершин, то граф G1 G2 также 2-связен;

Элементы теории графов Гамильтоновы пути и циклы Графы, имеющие гамильтонов цикл, называть гамильтоновыми. Гамильтонов граф должен быть двусвязным.

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

Элементы теории графов Гамильтоновы пути и циклы Теорема 3.18. Пусть G = V, E – связный граф и количество его вершин |V | 2. Тогда следующие утверждения эквивалентны:

1) граф 2-связен;

Элементы теории графов Гамильтоновы пути и циклы Доказательство.

1) 2) Пусть a и b – две вершины графа G. Рассмотрим множество всех простых циклов графа G, содержащих вершину a. Обозначим через U множество всех вершин, входящих в эти циклы. Ясно, что U =. Действительно, простой цикл, содержащий a, можно получить, объединив два ребра (a, x) и (a, y ) (x = y ) и простой (x, y )-путь, не проходящий через a (существующий согласно свойству 3 двусвязных графов).

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

Элементы теории графов

Гамильтоновы пути и циклы

Предположим, что b U, и положим U = V \U. Поскольку / граф G связен, то в нем найдется такое ребро (x, t), что x U, t U. Пусть S-простой цикл, содержащий a и x. Так как G -двусвязный граф, то в нем имеется простой (a, t)-путь P, не содержащий x. Пусть v – первая, считая от t, вершина, входящая в S, т.е. (t, v )-подпуть пути P не имеет с S общих вершин, отличных от v. Теперь легко построить простой цикл, содержащий v и t. Он получается объединением (v, x)-пути, проходящего через a и являющегося частью S, с ребром (x, t) и (t, v )-частью пути P (пунктирной линией). Следовательно, t U, но это противоречит выбору ребра (x, t). Таким образом U =, т.е. a и b принадлежат одному общему простому циклу.

Элементы теории графов

Гамильтоновы пути и циклы

2) 3) Пусть a – вершина и (x, t) – ребро графа. По условию G содержит цикл S, проходящий через вершины a и x. Не теряя общности будем считать, что ребро (x, t) S. Если при / этом окажется, что S проходит через вершину t, то требуемый цикл строится очевидным образом. Пусть S не проходит через вершину t. Тогда рассмотрим простой цикл, проходящий через вершины t и a. Такой цикл, по условию, существует. Частью этого цикла является простой путь P, соединяющий t с некоторой вершиной v S. Путь P можно выбрать так, чтобы пути P и S пересекались только в вершине v. Искомый цикл строится точно так же, как в предыдущем пункте.

Элементы теории графов Гамильтоновы пути и циклы 3) 4) Пусть (a, b) и (t, x) – два ребра графа G. По условию G имеет простые циклы S и S, первый из которых содержит ребро (a, b) и вершину x, а второй – (a, b) и t. Далее искомый цикл строится точно так же, как в предыдущих пунктах.

Элементы теории графов Гамильтоновы пути и циклы 4) 5) Пусть a и b – вершины графа G, и (t, x) – его ребро.

Будучи связным, граф G содержит простой путь P = (a, x,..., b). Согласно утверждению 4), в графе G есть простой цикл S, содержащий ребра (a, x) и (t, x). Легко видеть, что в объединении S P имеется требуемый путь.

Элементы теории графов Гамильтоновы пути и циклы 5) 6) Пусть a, b, c – вершины графа G, (c, d ) – его ребро. По условию в графе имеется простой (a, b)-путь, проходящий через (c, d ), и следовательно, содержащий c.

Элементы теории графов Гамильтоновы пути и циклы 6) 1) Пусть v – вершина графа G. Покажем, что граф G с удаленной вершиной v (граф G \{v }) – связен, т.е. любая пара a, b его вершин соединена путем. Действительно, согласно утверждению 6) в графе G имеется простой (v, b)-путь, проходящий через вершину a. Этот путь содержит (a, b)-подпуть, который, очевидно, не проходит через v и, следовательно, является (a, b)-путем и в графе G \{v }.

Элементы теории графов Гамильтоновы пути и циклы Теорема 3.19. Каждый негамильтонов двусвязный граф содержит тэта-подграф.

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

Элементы теории графов Гамильтоновы пути и циклы Доказательство.

Пусть G = V, E – негамильтонов двусвязный граф и C – простой цикл максимальной длины в этом графе. По условию теоремы множество S вершин графа G, не принадлежащих циклу S, непусто.

Среди двусвязных графов, порядок которых меньше пяти, нет негамильтоновых, поэтому |V | 5.

Из двусвязности графа и теоремы 3.18 следует, что количество вершин в цикле C не менее четырех.

Элементы теории графов Гамильтоновы пути и циклы Степенной последовательностью графа будем называть последовательность степеней его вершин.

Теорема 3.20.

Граф со степенной последовательностью

–  –  –

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

Элементы теории графов Гамильтоновы пути и циклы Теорема Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда в нем нет подграфов, полученных подразбиением ребер из K5 и K3,3.

Элементы теории графов Гамильтоновы пути и циклы Лев Семёнович Понтрягин (21 августа (3 сентября) 1908, Москва 3 мая 1988) советский математик, академик АН СССР (1958; член-корреспондент 1939), Герой Социалистического Труда (1969).

В 14 лет потерял зрение в результате несчастного случая.

Окончил Московский университет (1929). С 1939 года заведующий отделом Математического института им. В. А.

Стеклова АН СССР, одновременно с 1935 года профессор МГУ.

Элементы теории графов

Гамильтоновы пути и циклы

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

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

Понтрягин написал подробные мемуары, в которых дал оценки многим учёным и событиям, свидетелем и участником которых он был, в частности, кампании против Н. Н. Лузина.

КУРАТОВСКИЙ (Kuratowski) Казимеж (1896-1980) - польский математик, иностранный член АН СССР (1966). Труды по топологии, теории функций.

Элементы теории графов Гамильтоновы пути и циклы Теорема 3.21. Всякий 4-связный планарный граф является гамильтоновым.

Элементы теории графов Гамильтоновы пути и циклы Пусть G = V, E – связный граф, u, v – две его несовпадающие вершины. Длина кратчайшего (u, v )-пути (он, естественно, является простым путем) называется расстоянием между вершинами u и v и обозначается через d (u, v ).

Понятие расстояния между вершинами в связном графе позволяет определить k-ую степень графа. Пусть G - связный граф, k – натуральное число. Граф G k имеет тоже множество вершин, что и G, несовпадающие вершины u и v смежны в графе G k тогда и только тогда, когда для графа G верно неравенство d (u, v ) k. Очевидно, что если k |V | 1, то G k

– полный граф, который является гамильтоновым.

Интуитивно ясно, что если граф порядка n = |V | 3 связен, то при достаточно больших k граф G k гамильтонов.

Элементы теории графов Гамильтоновы пути и циклы Теорема 3.22. Если граф G порядка n = |V | 3 связен, то G 3

– гамильтонов граф.

Теорема 3.23.

Если G – двусвязный граф порядка n = |V | 3, то G 2 – гамильтонов граф.

Элементы теории графов Нахождение кратчайших путей в графе Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами. Длину такого кратчайшего пути d (v, t) и будем называть расстоянием от v до t. Отметим, что если каждый цикл нашего графа имеет положительную длину, то кратчайший путь будет всегда простым, не будет "зацикливания".

Элементы теории графов Нахождение кратчайших путей в графе Задача нахождения кратчайших путей от одного источника решается для трех случаев.

1) Веса всех ребер неотрицательны (сложность алгоритма

– O(n2 )).

Элементы теории графов Нахождение кратчайших путей в графе Задача нахождения кратчайших путей от одного источника решается для трех случаев.

1) Веса всех ребер неотрицательны (сложность алгоритма

– O(n2 )).

2) Ориентированный граф без циклов с отрицательной длиной (сложность алгоритма – O(n3 ), где n – число вершин).

Элементы теории графов Исходные данные: G = V, E – ориентированный, связный, конечный граф c неотрицательными весами рёбер.

v0 – источник, v V.

C = c(u, v ) – матрица весов ребер.

Результат: расстояния от источника до всех вершин графа D[v ] = d (v0, v ), v V.

Метод. Строим такое подмножество S множества вершин графа, S V, что кратчайший путь из источника в каждую вершину целиком лежит в S.

Элементы теории графов O(n2 ) Жадный (greedy) алгоритм, Дейкстра, 1959.

Элементы теории графов Нахождение кратчайших путей в графе Элементы теории графов Нахождение кратчайших путей в графе Если число D[u] не равно длине кратчайшего пути из v0 в u, то должен быть более короткий путь P. Этот путь должен содержать вершину, отличную от u и не принадлежащую S.

Пусть v – первая такая вершина на пути P из вершины v0 в вершину u. Но тогда расстояние от v0 до v меньше D[u], а кратчайший путь в вершину v, целиком (исключая сам узел v ) лежит в S. Следовательно, D[v ] D[u] в момент выбора u;

таким образом, мы пришли к противоречию. Отсюда заключаем, что такого пути P нет и D[u] – длина кратчайшего пути из v0 в u.

Элементы теории графов Нахождение кратчайших путей в графе

Нахождение максимальных путей в графе:

1) через каждое ребро не более одного раза;

Элементы теории графов Нахождение кратчайших путей в графе

Нахождение максимальных путей в графе:

1) через каждое ребро не более одного раза;

1) построение эйлерового пути – полиномиально разрешима;

Элементы теории графов Нахождение кратчайших путей в графе

Нахождение максимальных путей в графе:

1) через каждое ребро не более одного раза;

1) построение эйлерового пути – полиномиально разрешима;

2) через каждую вершину не более одного раза;

Элементы теории графов Нахождение кратчайших путей в графе

Нахождение максимальных путей в графе:

1) через каждое ребро не более одного раза;

1) построение эйлерового пути – полиномиально разрешима;

2) через каждую вершину не более одного раза;

2) построение гамильтонова пути – NP-трудная задача.

Элементы теории графов Под минимальным разрезом, разделяющим s и t, разрез P(A), s A, t V \A, с минимальной пропускной способностью.

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

Элементы теории графов

Максимальный поток в сети

Впервые проблемы связанные с потоками в сетях были рассмотрены Канторовичем в 1933 году. (Более того – он рассматривал более общую задачу с движением потока жидкостей различных типов (multicommodity ows)). Основы теории потоков были заложены в период с ноября 1954 по декабрь 1955 года исследователями корпорации RAND (Санта-Моника, Калифорния).

Первый отчет "Максимальный поток в сети"датируется 19 ноября 1954 года. Авторы отчета – Форд (Ford) и Фалкерсон (Fulkerson), доказали теорему о максимальном потоке и минимальном разрезе для неориентированных графов:

значение максимального потока в сети равно минимальной пропускной способности разреза.

Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети Элементы теории графов Максимальный поток в сети

Рассмотрим случаи:

1) два и более источника;

Элементы теории графов Минимальное остовное дерево Жадные алгоритмы Крускала и Прима Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Трудоёмкость алгоритма Крускала O(m log m), где m – количество рёбер в графе Элементы теории графов Минимальное остовное дерево Алгоритм Прима Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Элементы теории графов Минимальное остовное дерево Трудоёмкость алгоритма Прима O(n log n + m log n), где m

– количество рёбер в графе, n – количество вершин Элементы теории графов Сортировка данных

–  –  –

Важным является способ хранения информации и обращение к ней.

Элементы теории графов Сортировка данных O(n log n) Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных O(n2 ) Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных O(n log n) Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Сортировка данных Элементы теории графов Хранение информации. Пирамиды.

–  –  –

Хранение информации. Пирамиды.

Элементы теории графов Хранение информации. Пирамиды.

Элементы теории графов Хранение информации. Пирамиды.

Элементы теории графов Хранение информации. Пирамиды.

Сортировка в бинарной пирамиде Элементы теории графов Хранение информации. Пирамиды.

Элементы теории графов Хранение информации. Пирамиды.

Элементы теории графов Хранение информации. Пирамиды.

Элементы теории графов Хранение информации. Пирамиды.

Элементы теории графов Хранение информации. Пирамиды.

Элементы теории графов Хранение информации. Пирамиды.

Элементы теории графов Хранение информации. Пирамиды.




Похожие работы:

«АЗЕРБАЙДЖАНО-АРМЯНСКИЕ ОТНОШЕНИЯ И ВЛИЯНИЕ НА НИХ “ТУРЕЦКОГО ФАКТОРА” Результаты исследования СМИ СОДЕРЖАНИЕ РАЗДЕЛ I.ОТЧЕТ О МОНИТОРИНГЕ ОСВЕЩЕНИЯ АЗЕРБАЙДЖАНО-АРМЯНСКИХ ОТНОШЕНИЙ И ВЛИЯНИЯ НА НИХ “ТУРЕЦКОГО ФАКТОРА” 3 ГЛАВА I.1. ОБЩАЯ ИНФОРМАЦИЯ О МОНИТОРИНГЕ 3 ГЛАВА I.2. МОНИТОРИНГ СМИ АЗЕРБАЙДЖАНА 8 СПИСОК И КРАТКАЯ ХАРАКТЕРИСТИКА ИССЛЕДОВАННЫХ СМИ 8 АНАЛИЗ ДАННЫХ МОНИТОРИНГА СМИ АЗЕРБАЙДЖАНА 10 ГЛАВА I.3. МОНИТОРИНГ СМИ АРМЕНИИ 22 СПИСОК И КРАТКАЯ ХАРАКТЕРИСТИКА ИССЛЕДОВАННЫХ СМИ 22 АНАЛИЗ...»

«Права лиц, переживших Холокост, проживающих в Израиле Claims Conference  The Conference on Jewish Material Claims Against Germany Права лиц, переживших Холокост, проживающих в Израиле Содержание Права, пособия и льготы, предоставляемые пережившим Холокост, правительством Израиля Часть А: 1. Новое пособие для людей, бывших в лагерях и гетто во время Второй мировой войны и не получающих пособия для переживших Холокост и подвергавшихся преследованиям 12 2. Новые льготы для получающих пособие...»

«ISSN 2304–2338 (Print) ISSN 2413–4635 (Online) PROBLEMS OF MODERN SCIENCE AND EDUCATION 2015. № 11 (41) EDITOR IN CHIEF Valtsev S. EDITORIAL BOARD Abdullaev K. (PhD in Economics, Azerbaijan), Alieva V. (PhD in Philosophy, Republic of Uzbekistan), Alikulov S. (D.Sc. in Engineering, Republic of Uzbekistan), Anan'eva E. (PhD in Philosophy, Ukraine), Asaturova A. (PhD in Medicine, Russian Federation), Askarhodzhaev N. (PhD in Biological Sc., Republic of Uzbekistan), Bajtasov R. (PhD in Agricultural...»

«1.Цели и планируемые результаты изучения дисциплины Цель изучения дисциплины «Проектирование и конструирование изделий с помощью систем автоматизированного проектирования» – сформировать специалистов, умеющих обоснованно и результативно применять существующие и осваивать новые методы проектирования перспективного оборудования, строить трехмерные модели деталей и узлов, проводить инженерные расчеты в системе автоматизированного проектирования Solid Works. Результаты обучения (компетенции)...»

«Мир без преград. Группа ВТБ Социальный отчет 201 Социальный отчет Основные сокращения АСУН Автоматизированнаясистемауправлениянедвижимостью АСУОР Автоматизированнаясистемауправленияоперационнымиикомплаенс-рисками БанкВТБ(Азербайджан) ОАОБанкВТБ(Азербайджан) БанкВТБ(Армения) ЗАО«БанкВТБ(Армения)» БанкВТБ(Беларусь) ЗАОБанкВТБ(Беларусь) БанкВТБ(Белград) AOБанкВТБ(Белград) БанкВТБ(Грузия) АО«БанкВТБ(Грузия)» БанкВТБ(Казахстан) ДОАОБанкВТБ(Казахстан) БанкВТБ(Украина) ПАО«ВТББанк»(Украина)...»

«Томская область городской округ закрытое административно-территориальное образование Северск УПРАВЛЕНИЕ ОБРАЗОВАНИЯ АДМИНИСТРАЦИИ ЗАТО СЕВЕРСК ПРИКАЗ № 414 16.09.2014 Об организации школьного этапа Всероссийской олимпиады школьников в 2014-2015 учебном году в ЗАТО Северск В соответствии с приказом Министерства образования и науки Российской Федерации от 18.11.2013 №1252 «Об утверждении Порядка проведения Всероссийской олимпиады школьников», с Распоряжением Департамента общего образования...»

«МЕЖДУНАРОДНЫЙ ИНСТИТУТ НОВЕЙШИХ ГОСУДАРСТВ INTERNATIONAL INSTITUTE OF NEWLY ESTABLISHED STATES БОЛЬШОЙ ЭЛЕКТОРАЛЬНЫЙ ГОД В ПОЛЬШЕ Аналитический доклад по итогам президентских и парламентских выборов в Республике Польша в 2015 г. По заказу Фонда ИСЭПИ Москва – Варшава Большой электоральный год в Польше. Аналитический доклад по итогам президентских и парламентских выборов в Республике Польша в 2015 г. – М.: Международный Институт Новейших Государств, 2015. – 96 с. Авторский коллектив: Алексей...»

«ПРОЕКТ УТВЕРЖДЕН ПРЕДВАРИТЕЛЬНО УТВЕРЖДЕН Советом директоров Общим собранием акционеров ОАО «Корпорация «Иркут» ОАО «Корпорация «Иркут» Протокол от 19 мая 2015 г. № 16 протокол от _ 2015 г. № 35 ГОДОВОЙ ОТЧЕТ открытого акционерного общества «Научно-производственная корпорация «Иркут» за 2014 г. Президент О.Ф. Демченко (подпись) Главный бухгалтер С.К. Смехов (подпись) Москва Содержание: Введение... Общие сведения о Корпорации.. 5 Раздел 1.Состав органов управления ОАО «Корпорация «Иркут». 14...»

«ТРЕТИЙ МЕЖДУНАРОДНЫЙ КОНГРЕСС «ЦВЕТНЫЕ МЕТАЛЛЫ – 2011», 7–9 СЕНТЯБРЯ, РОССИЯ, Г. КРАСНОЯРСК РАЗДЕЛ X НОВОСТИ НАУКИ И ТЕХНИКИ Третий международный конгресс «Цветные металлы–2011» • Раздел X • Новости науки и техники КОНСОРЦИУМ SET – ОПТИМАЛЬНЫЙ СПОСОБ РАБОТЫ НАД СЛОЖНЫМИ КОМПЛЕКСНЫМИ ПРОЕКТАМИ С. Г. Федоров ОАО «Сибцветметниипроект», г. Красноярск, Россия Красноярский край является одним из ключевых российских сырьевых регионов – на его территории расположены практически все виды минеральных...»

«Содержание Вступительное слово Введение 5 Глоссарий 5 Сводное резюме Аналитический раздел Объект исследования 8 Предмет исследования 8 Основные тренды в развитии отрасли НКТ Образ индустрии НКТ Коммерческие проекты в области НКТ 17 Исследовательская деятельность в области нейротехнологий. 25 Основные игроки и роли участников рынка НКТ за рассматриваемый период. Качественный анализ Основные формы и характеристики практик стимулирования и поддержки развития нейротехнологий в мире 29 Выводы и...»

«ISSN 2304–2338 (Print) ISSN 2413–4635 (Online) PROBLEMS OF MODERN SCIENCE AND EDUCATION 2015. № 12 (42) EDITOR IN CHIEF Valtsev S. EDITORIAL BOARD Abdullaev K. (PhD in Economics, Azerbaijan), Alieva V. (PhD in Philosophy, Republic of Uzbekistan), Alikulov S. (D.Sc. in Engineering, Republic of Uzbekistan), Anan'eva E. (PhD in Philosophy, Ukraine), Asaturova A. (PhD in Medicine, Russian Federation), Askarhodzhaev N. (PhD in Biological Sc., Republic of Uzbekistan), Bajtasov R. (PhD in Agricultural...»

«ОнЛайн семинар: Бюджетный учет. Практика применения изменений 2011 года Лектор: Гейц Игорь Викторович к.э.н., главный редактор журнала «Заработная плата. Расчеты, учет, налоги». Автор многочисленных изданий и публикаций по вопросам заработной платы, учета и отчетности, налогообложения, разработчик ведомственных приказов ряда силовых министерств и ведомств по особенностям применения Инструкции по бюджетному учету Бюджетный учет. Практика применения изменений 2011 года Бюджетный учет. Практика...»

«Утвержден Общим собранием акционеров ОАО «ТРК» Протокол № 14 от «28» июня 2013 г. Проект предварительно утверждн решением Совета директоров ОАО «ТРК» Протокол № 16 от «07» мая 2013 г. ГОДОВОЙОТЧЕТ Открытого акционерного общества «Томская распределительная компания» по результатам 2012 финансового года Управляющий директор – Первый заместитель генерального директора ОАО «ТРК» О.В. Петров Заместитель генерального директора по финансам – главный бухгалтер ОАО «ТРК» И.Н. Разманова г. Томск, 2013...»

«Приказ Минобрнауки России от 27.10.2014 N Об утверждении федерального государственного образовательного стандарта среднего профессионального образования по специальности 54.02.01 Дизайн (по отраслям) (Зарегистрировано в Минюсте России 24.11.2014 N 34861) Документ предоставлен КонсультантПлюс www.consultant.ru Дата сохранения: 11.10.2015 Приказ Минобрнауки России от 27.10.2014 N 1391 Документ предоставлен КонсультантПлюс Об утверждении федерального государственного образовательного Дата...»

«КАРТИРОВАНИЕ НЕУРЕГУЛИРОВАННОЙ МИГРАЦИИ В ЦЕНТРАЛЬНОЙ АЗИИ Картирование неурегулированной миграции в Центральной Азии Мж на о ная о аниза ия о ми а ии (М М) 2 КАРТИРОВАНИЕ НЕУРЕГУЛИРОВАННОЙ МИГРАЦИИ В ЦЕНТРАЛЬНОЙ АЗИИ УДК 314.1 ББК 60.7 K Картирование неурегулированной миграции в Центральной Азии 2014 — Астана, 2015. — 164 стр. ISBN 978-601-7313-74-6 K 27 Доклад «Картирование неурегулированной миграции в Центральной Азии» был подготовлен командой международных и национальных экспертов при...»

«НАЦИОНАЛЬНАЯ БИБЛИОТЕКА РЕСПУБЛИКИ БУРЯТИЯ ЕЖЕГОДНЫЙ ДОКЛАД О ДЕЯТЕЛЬНОСТИ ГОСУДАРСТВЕННЫХ И МУНИЦИПАЛЬНЫХ БИБЛИОТЕК РЕСПУБЛИКИ БУРЯТИЯ в 2014 году Улан-Удэ УДК 0 ББК 78.23(2) Б 5 Ответственный редактор Ж. Б. Ильина директор Национальной библиотеки Республики Бурятия Ответственные за выпуск Д. Ц. Мункуева, В. А. Трончеева, И.Н. Цыдыпова Б 594 Ежегодный доклад о деятельности государственных и муниципальных библиотек Республики Бурятия в 2014 году / Нац. б-ка Республики Бурятия ; [сост. : Д. Ц....»

«1. Цели освоения дисциплины Целями освоения дисциплины «Метрология» являются: – получение знаний о современных мировоззренческих концепциях и принципов в области метрологии;– овладение знаниями о методах обеспечения единства измерений в стране; об органах и службах, обеспечивающих единства измерений; о метрологической службе предприятия и решаемых ею задачах;– приобретение навыков для применения их в практической деятельности. Область профессиональной деятельности магистров включает:...»

«ИЗВЕЩЕНИЕ И ДОКУМЕНТАЦИЯ о проведении запроса котировок № 40-15/А на поставку мобильного здания для нужд ФГАОУ ВПО «Сибирский федеральный университет» (от 13.08.2015) Заказчик: Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Сибирский федеральный университет» (далее по тексту – Заказчик), расположенное по адресу: 660041, г. Красноярск, пр. Свободный, 79; адрес электронной почты: zakupka@sfu-kras.ru; контактный телефон: +7 (391) 206-20-35...»

«РОССИЙСКАЯ АКАДЕМИЯ НАУК КАРЕЛЬСКИЙ НАУЧНЫЙ ЦЕНТР ИНСТИТУТ ВОДНЫХ ПРОБЛЕМ СЕВЕРА RUSSIAN ACADEMY OF SCIENСES KARELIAN RESEARCH CENTER NORTHERN WATER PROBLEMS INSTITUTE Посвящается Международному полярному году Russian Academy of Scienсes Karelian Research Center Northern Water Problems Institute THE WHITE [BELOE] SEA AND THEIR WATERSHED UNDER INFLUENSES OF CLIMATE AND ANTROPOGENIC IMPACT Eds. N. Filatov and A. Terzhevik Petrozavodsk Российская академия наук Карельский научный центр Институт...»

«Владимир ПЕТРОВ Астана Казахстан избранные стихи и песни том первый Астана 2008 Петров в.И., Избранные стИхИ И ПеснИ АстАнА кАзАхстАн ББК 84 (5 Каз-Рус)-5 П 31 Петров Владимир П 31 Астана – Казахстан. Избранные стихи и песни, в 2-х томах. I том – Астана: Петров В.И., 2008. – 176 с. ISBN 9965-06-494-6 В первый том издания вошли сочинения Петрова В.И., посвященные Отечеству, государственным символам Республики Казахстан, ветеранам Великой Отечественной войны и труда, а также нынешнему поколению...»








 
2016 www.nauka.x-pdf.ru - «Бесплатная электронная библиотека - Книги, издания, публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.