WWW.METODICHKA.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Методические указания, пособия
 

Pages:   || 2 | 3 |

«Образовательный проект В.Е. Алексеев Графы и алгоритмы Нижний Новгород GtlBook1_0_7 Учебник является компонентом образовательного модуля GTLView, подготовленного в рамках внутреннего ...»

-- [ Страница 1 ] --

ЗАО "Нижегородская лаборатория программных технологий"

603600, Нижний Новгород, ГСП-900, ул. Тургенева д. 24, тел.(8312) 36-75-77, 36-84-54; факс (8312) 38-02-0

Образовательный проект

В.Е. Алексеев

Графы и алгоритмы

Нижний Новгород

GtlBook1_0_7

Учебник является компонентом образовательного модуля GTLView,

подготовленного в рамках внутреннего проекта компании ЗАО "Нижегородская

лаборатория программных технологий" Может использоваться



NSTLab.

студентами, молодыми специалистами при изучении соответствующих курсов прикладной математики.

Автор Алексеев В.Е., доцент, кандидат физ.-мат.наук.

Редактор Полотовский Г.М., доцент, кандидат физ.-мат.наук.

2 ©Нижегородская лаборатория программных технологий NSTLab Оглавление Оглавление

ПРЕДИСЛОВИЕ

ГЛАВА 1. ОСНОВЫ ТЕОРИИ ГРАФОВ 5

1.1. Начальные понятия 5

1.2. Операции над графами 17

1.3. Маршруты, связность, расстояния 21

1.4. Деревья 27

1.5. Двудольные графы

1.6. Планарные графы 33

ГЛАВА 2. СТРУКТУРНЫЙ И МЕТРИЧЕСКИЙ АНАЛИЗ ГРАФОВ 37

2.1. Каркасы и компоненты связности 37

2.2. Поиск в ширину и расстояния

2.3. Поиск в глубину

2.4. Блоки ГЛАВА 3. ЦИКЛЫ 57

3.1 Эйлеровы циклы 57

3.2. Пространство циклов графа

3.3. Гамильтоновы циклы 65 GtlBook1_0_7 Предисловие Настоящее учебное пособие основано на материале лекций, читающихся в Нижегородском государственном университете для студентов, обучающихся по специальностям "прикладная математика" и "информационные системы". Это лекции по разделу "теория графов" курса дискретной математики, по курсу "анализ и разработка алгоритмов" для магистрантов и по одноименным спецкурсам.

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

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

Предлагаемая первая часть пособия состоит из трех глав.

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

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

Третья глава посвящена вопросам анализа цикловой структуры графа. Рассматриваются эйлеровы и гамильтоновы циклы, алгоритмы их построения, пространство циклов графа и алгоритм построения системы фундаментальных циклов.

–  –  –

Глава 1. Основы теории графов

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

–  –  –

На таких диаграммах часто ни способ изображения элементов, ни форма или длина линий не имеют значения – важно лишь, какие именно пары элементов соединены линиями. Если посмотреть внимательно, то можно заметить, что рисунки 1.1(а) и 1.1(б) изображают одну и ту же структуру связей между элементами A, B, C, D, E, F. Эту же структуру можно описать и, не прибегая к графическому изображению, а просто перечислив пары связанных между собой элементов: (A, B), (A, D), (B, C), (B, E), (B, F), (C, F), (D, E). Таким образом, когда мы отвлекаемся от всех несущественных подробностей, у нас остаются два списка: список элементов и список пар элементов. Вместе они составляют то, что математики называют "графом". Из этого примера видно, что понятие графа само по себе не связано прямо с геометрией или графикой. Тем не менее, возможность нарисовать граф – одна из привлекательных черт теории графов.





Термин "граф" неоднозначен, и это легко обнаружить, сравнивая определения графа, приводимые в разных книгах по теории графов. Однако во всех этих определениях есть и общее. В любом случае граф состоит из двух множеств – множества вершин и множества ребер, причем для каждого ребра указана пара вершин, которые это ребро соединяет. Здесь будут рассматриваться только конечные графы, то есть такие, у которых оба множества конечны. Чтобы получить законченное определение графа того или иного типа, необходимо уточнить еще следующие три момента.

1. Ориентированный или неориентированный?

Прежде всего нужно договориться, считаем ли мы пары (a, b) и (b, a) различными. Если да, то говорят, что рассматриваются упорядоченные пары (порядок элементов в паре важен), если нет – неупорядоченные. Если ребро e соединяет вершину a с вершиной b и пара (a, b) считается GtlBook1_0_7 упорядоченной, то это ребро называется ориентированным, вершина a – его началом, вершина b – концом. Если же эта пара считается неупорядоченной, то ребро называется неориентированным, а обе вершины – его концами. Заметим, что неориентированное ребро, соединяющее a с b, соединяет и b с a, для ориентированного же это неверно. Чаще всего рассматривают графы, в которых все ребра имеют один тип – либо ориентированные, либо неориентированные. В соответствии с этим и весь граф называют ориентированным или неориентированным. На рисунках ориентацию ребра (направление от начала к концу) указывают стрелкой. На рисунке 1.1 показаны неориентированные графы, а на рисунке 1.2 – ориентированные.

2. Кратные ребра.

Следующий пункт, требующий уточнения – могут ли два разных ребра соединять одну и ту же пару вершин? Если да, то говорят, что в графе допускаются кратные ребра. Граф с кратными ребрами называют также мультиграфом. На рисунке 1.2 изображены два графа, левый является ориентированным мультиграфом, а правый – ориентированным графом без кратных ребер.

3. Петли.

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

–  –  –

Комбинируя эти три признака, можно получить разные варианты определения понятия графа.

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

ОПРЕДЕЛЕНИЕ. Обыкновенным графом называется пара G = (V, E), где V – конечное множество, E – множество неупорядоченных пар различных элементов из V. Элементы множества V называются вершинами графа, элементы множества E – его ребрами.

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

–  –  –

Общее определение неориентированного графа (неориентированного мультиграфа с петлями) Неориентированный граф есть тройка G = (V, E, I), где V и Е – множества, I – отображение множества E во множество неупорядоченных пар элементов множества V.

Элементы множества V называются вершинами графа, элементы множества E – ребрами, I – функцией инцидентности. Заметим, что ребра теперь – не пары вершин, а "самостоятельные" объекты.

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

V = {1, 2, 3, 4, 5}, E = {a, b, c, d, e, f} и зададим функцию I таблицей:

–  –  –

Если в приведенном определении заменить слово "неупорядоченных" словом "упорядоченных", получится определение ориентированного мультиграфа.

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

Множество вершин графа G будем обозначать через VG, множество ребер – EG, число вершин – n(G), число ребер – m(G).

Из определения видно, что для задания обыкновенного графа достаточно перечислить его вершины и ребра, причем каждое ребро должно быть парой вершин. Положим, например, VG = {a, b, c, d, e, f }, EG = {(a, c ), (a, f ), (b, c ), (c, d ), (d, f )}. Тем самым задан граф G с n(G ) = 6, m(G ) = 5. Если граф не слишком велик, то более наглядным способом представить его является рисунок, на котором вершины изображаются кружками или иными значками, а ребра – линиями, соединяющими вершины. Заданный выше граф G показан на рисунке 1.4. Мы будем часто пользоваться именно этим способом представления графа, при этом обозначения вершин иногда будут помещаться внутри кружков, изображающих вершины, иногда рядом с ними, а иногда, когда имена вершин не существенны, и вовсе опускаться.

Графы и бинарные отношения Напомним, что бинарным отношением на множестве A называется любое подмножество R A2, состоящего из всевозможных упорядоченных пар элементов множества A.

множества Сравнивая с тем, что говорилось выше об определениях различных типов графов, видим, что понятие бинарного отношения эквивалентно понятию ориентированного графа с петлями. Другие типы графов без кратных ребер – это частные виды бинарных отношений. Отношение R называется рефлексивным, если для любого x A пара (x, x) принадлежит R, и антирефлексивным, если ни одна такая пара не принадлежит R. Оно называется симметричным, если для любых x, y A из

–  –  –

симметричное отношение.

Откуда берутся графы Легко найти примеры графов в самых разных областях науки и практики. Сеть дорог, трубопроводов, электрическая цепь, структурная формула химического соединения, блок-схема программы – в этих случаях графы возникают очень естественно и видны "невооруженным глазом".

При желании графы можно обнаружить практически где угодно. Яркая демонстрация этого содержится в книге [D.E.Knuth, The Stanford GraphBase] – графы извлекаются из романа "Анна Каренина", из картины Леонардо да Винчи, из материалов Бюро Экономического Анализа США и из других источников.

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

–  –  –

Еще один способ образования графов из геометрических объектов иллюстрирует рисунок 1.6. Слева показаны восемь кругов на плоскости, а справа – граф, в котором каждая вершина соответствует одному из этих кругов и две вершины соединены ребром в том и только том случае, когда соответствующие круги пересекаются. Такие графы называют графами пересечений. Можно построить граф пересечений семейства интервалов на прямой, или дуг окружности, или параллелепипедов.

–  –  –

Число графов Возьмем какое-нибудь множество V, состоящее из n элементов, и будем рассматривать всевозможные (обыкновенные!) графы с множеством вершин V. Обозначим число таких графов через gn. Эти графы различаются только множествами ребер, а каждое ребро – это неупорядоченная пара различных элементов из V. В комбинаторике такие пары называются сочетаниями из n по 2, их n n(n 1) число равно =. Каждая пара может быть включена или не включена во множество ребер графа. Применяя правило произведения, приходим к следующему результату.

–  –  –

Смежность, инцидентность, степени Если в графе имеется ребро e = (a, b), то говорят, что вершины a и b смежны в этом графе, ребро e инцидентно каждой из вершин a, b, а каждая из них инцидентна этому ребру.

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

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

–  –  –

Это равенство известно как "лемма о рукопожатиях". Из него следует, что число вершин нечетной степени в любом графе четно.

GtlBook1_0_7 Вершину степени 0 называют изолированной, а вершину степени 1 висячей. Граф называют регулярным степени d, если степень каждой его вершины равна d.

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

Подграф Граф G называется подграфом графа G, если VG VG, EG EG. Всякий подграф может быть получен из графа удалением некоторых вершин и ребер. На рисунке 1.7 изображены граф G и его подграфы G1, G2, G3, G4.

–  –  –

Подграф G графа G называется остовным, если VG = VG. Остовный подграф может быть получен из графа удалением некоторых ребер, вершины же остаются в неприкосновенности. На рисунке 1.7 G1 – остовный подграф графа G, а G2, G3 и G4 не являются остовными подграфами.

Другая важная разновидность подграфов – порожденные подграфы. Пусть задан граф G = (V, E ) и в нем выбрано множество вершин U V. Рассмотрим подграф G = (U, E ), где E состоит из всех тех ребер графа G, у которых оба конца принадлежат U. Говорят, что этот подграф порожден множеством вершин U. Он обозначается через G U. Порожденный подграф может быть получен из графа удалением "лишних" вершин, т.е. вершин, не принадлежащих U, причем при удалении вершины удаляются и все инцидентные ей ребра.

Можно определить также подграф, порожденный множеством ребер F E. Это подграф G = (V, F ), где V состоит из всех вершин, инцидентных ребрам из F.

На рисунке 1.7 G2 – подграф графа G, порожденный множеством вершин {1, 2, 4, 5}, т.е.

G2 = G {,2,4,5}, он же порождается множеством ребер {(1,2), (1,4), (4,5)}; подграф G3 не порождается множеством вершин, но порождается множеством ребер {(1,2), (2,3), (3,4)}; подграф G4 не является ни остовным, ни порожденным в каком-либо смысле.

Некоторые специальные графы Рассмотрим некоторые особенно часто встречающиеся графы.

Пустой граф – граф, не содержащий ни одного ребра. Пустой граф с множеством вершин {1, 2,...,n} обозначается через On.

–  –  –

Полный граф – граф, в котором каждые две вершины смежны. Полный граф с множеством вершин {1, 2,...,n} обозначается через K n. Граф K1, в частности, имеет одну вершину и ни одного ребра.

Мы считаем также, что существует граф K 0, у которого VG = EG =.

Цепь (путь) Pn – граф с множеством вершин {1,2,..., n} и множеством ребер {(1,2 ), (2,3),K, (n 1, n )}.

Цикл Cn – граф, который получается из Pn добавлением ребра (1, n ).

Все эти графы при n = 4 показаны на рисунке 1.8.

–  –  –

Дополнительный граф Дополнительным графом, или дополнением, к обыкновенному графу G называется граф G, у которого множество вершин то же, что у G, и две различные вершины смежны тогда и только тогда, когда они не смежны в G. Например, On = K n. Другой пример показан на рисунке 1.9. Очевидно, всегда G = G.

–  –  –

Изоморфизм На рисунке 1.10 изображены два графа с одним и тем же множеством вершин {a, b, c, d}. При внимательном рассмотрении можно обнаружить, что это разные графы – в левом имеется ребро (a, c), в правом же такого нет. В то же время, если не обращать внимания на наименования вершин, то эти графы явно одинаково устроены: каждый из них – цикл из четырех вершин. Во многих случаях при исследовании строения графов имена или номера вершин не играют роли и такие графы, один из которых получается из другого переименованием вершин, можно считать одинаковыми. Для того чтобы это можно было делать "на законном основании", вводится понятие изоморфизма графов.

ОПРЕДЕЛЕНИЕ. Графы G1 и G2 называются изоморфными, если существует такая биекция f множества VG1 на множество VG2, что (a, b ) EG1 тогда и только тогда, когда ( f (a ), f (b)) EG2.

Отображение f в этом случае называется изоморфизмом G1 в G2.

Тот факт, что графы G1 и G2 изоморфны, записывается так: G1 G2.

Для графов, изображенных на рисунке 1.10, изоморфизмом является, например, отображение, задаваемое таблицей:

–  –  –

Заметим, что в этом примере есть и другие изоморфизмы первого графа во второй.

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

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

В общем случае узнать, изоморфны ли два графа, достаточно сложно. Если буквально следовать определению, то нужно перебрать все биекции множества вершин одного из них во множество вершин другого и для каждой из этих биекций проверить, является ли она изоморфизмом. Для n вершин имеется n! биекций и эта работа становится практически невыполнимой уже при не очень больших n (так, 10! = 3628800, 20! 2 1018 ). Однако для многих конкретных пар графов их неизоморфность устанавливается довольно легко. Рассмотрим, например, графы, изображенные на рисунке 1.11. Так как при изоморфизме пара смежных вершин переходит в пару смежных, а пара несмежных – в пару несмежных, то ясно, что число ребер у двух изоморфных графов должно быть одинаковым. Поэтому сразу можно сказать, что графы G1 и G2, у которых разное количество ребер, неизоморфны. У графов G1 и G3 одинаковое число ребер, но они тоже неизоморфны. Это можно установить, сравнивая степени вершин. Очевидно, при изоморфизме каждая вершина переходит в вершину той же степени. Но если выписать степени всех вершин графа G1 в

–  –  –

неубывающем порядке, то получится последовательность (2, 2, 3, 3, 3, 3), а для графа G3 получится последовательность (2, 2, 2, 3, 3, 4). Из того, что эти последовательности различны, следует неизоморфность двух графов. С графами G1 и G4 дело обстоит немного сложнее – у них и наборы степеней одинаковы. Все же и эти графы неизоморфны: можно заметить, что в G4 есть подграф, являющийся циклом длины 3, а в G1 таких нет. Ясно, что при изоморфизме каждый подграф одного графа переходит в изоморфный ему подграф другого.



–  –  –

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

Графы и матрицы Пусть G – граф с n вершинами, причем VG = {,2,K, n}. Построим квадратную матрицу A порядка n, в которой элемент Аi,j, стоящий на пересечении строки с номером i и столбца с номером j, определяется следующим образом:

–  –  –

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

Обратно, каждой квадратной матрице порядка n, составленной из нулей и единиц и обладающей двумя указанными свойствами, соответствует обыкновенный граф с множеством вершин {,2,K, n}.

Другая матрица, ассоциированная с графом – это матрица инцидентности. Для ее построения занумеруем вершины графа числами от 1 до n, а ребра – числами от 1 до m. Матрица инцидентности I имеет n строк и m столбцов. В неориентируемом случае ее элемент I ij равен 1, если вершина с номером i инцидентна ребру с номером j, в противном случае он равен нулю. На рисунке 1.12 показан граф с занумерованными вершинами и ребрами и его матрицы смежности и инцидентности.

GtlBook1_0_7

–  –  –

–  –  –

Для ориентированного графа матрица инцидентности определяется несколько иначе: ее элемент I ij равен 1, если вершина i является началом ребра j, он равен –1, если она является концом этого ребра, и он равен 0, если эта вершина и это ребро не инцидентны друг другу.

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

Задачи Определите число неориентированных графов с n вершинами, в которых нет кратных ребер, но 1.

могут быть петли.

–  –  –

Определите число ориентированных графов с n вершинами без петель, в которых каждая пара 2.

различных вершин соединена

а) не более чем одним ребром;

–  –  –

РЕШЕНИЕ. Для того чтобы задать такой граф, нужно в случае а) для каждой неупорядоченной пары различных вершин (a, b ) выбрать одну из трех возможностей: 1) ребро (a, b ) включается в граф; 2) ребро (b, a ) включается в граф; 3) ни одно из этих ребер не включается в граф. В случае б) остаются только первые две возможности.

Для любого натурального числа k определим граф Qk следующим образом. Вершинами его 3.

являются всевозможные упорядоченные двоичные наборы длины k. Всего, таким образом, в этом графе 2 k вершин. Вершины x = (x1, K, xk ) и y = ( y1,K, yk ) смежны тогда и только тогда, когда наборы x и y различаются точно в одной координате. Этот граф называется k-мерным кубом. Определите число ребер в графе Qk.

СОВЕТ. Попробуйте воспользоваться леммой о рукопожатиях.

–  –  –

РЕШЕНИЕ. Для каждого двоичного набора длины k имеется ровно k наборов, отличающихся от него в одной координате (чтобы получить набор, отличающийся от данного в одной координате, достаточно указать эту координату, а ее можно выбрать k способами). Следовательно, степень каждой вершины в графе Qk равна k. По лемме о рукопожатиях, число ребер равно половине суммы степеней всех вершин.

Граф перестановок порядка k строится следующим образом. Его вершины соответствуют 4.

всевозможным перестановкам элементов 1, 2,..., k. В этом графе, следовательно, k! вершин. Две вершины смежны тогда и только тогда, когда одна из соответствующих перестановок может быть получена из другой одной транспозицией (перестановкой двух элементов). При k = 3 этот граф показан на рисунке 1.13. Определите число ребер в графе перестановок порядка k.

(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)

–  –  –

c) Проще перечислить дополнительные графы (очевидно, если два графа изоморфны, то их дополнения тоже изоморфны). Так как полный граф с 6 вершинами имеет 15 ребер, то граф, дополнительный к графу с 13 ребрами, будет иметь два ребра. Таких графов всего два (в одном из них два ребра смежны, в другом – несмежны).

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

вершины равна 3.

ОТВЕТ. Их два – см. рисунок 1.16.

–  –  –

ОТВЕТ. При любом четном n 4.

РЕШЕНИЕ. Из леммы о рукопожатиях следует, что сумма степеней вершин любого графа – четное число, поэтому, если каждая степень равна 3, то n должно быть четным. При n = 4 полный граф K 4 удовлетворяет условию задачи. При n = 6 существует два таких графа – см. решение задачи 6. В общем случае, если n делится на 4, то граф с требуемым свойством можно построить так: разбить множество вершин на четверки и на каждой четверке построить полный граф. Если же n не делится на четыре, то можно выбрать шесть вершин, на них построить один из графов из задачи 6, а с остальными вершинами (их число уже делится на 4) поступить как в первом случае.

Сколько имеется различных изоморфизмов G1 в G2 для графов, изображенных на рисунке 1.10?

8.

ОТВЕТ. 8.

Граф, изоморфный своему дополнению, называется самодополнительным.

9.

a) Докажите, что граф C5 – самодополнительный.

b) Найдите все самодополнительные графы с четырьмя вершинами.

c) Существуют ли самодополнительные графы с шестью вершинами?

ОТВЕТ. б) Такой граф один – P4.

–  –  –

ОТВЕТ. G2 G3, остальные графы не изоморфны этим двум и друг другу.

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

GtlBook1_0_7

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

Обратная операция – добавление ребра.

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

Операция стягивания ребра (a, b) преобразует граф следующим образом. Вершины a и b удаляются из графа, к нему добавляется новая вершина c и она соединяется ребром с каждой вершиной, с которой была смежна хотя бы одна из вершин a, b.

Операция подразбиения (подразделения) ребра (a, b) действует следующим образом. Из графа удаляется это ребро, к нему добавляется новая вершина c и два новых ребра (a, c) и (b, c). На рисунке 1.18 изображены исходный граф G, граф G, полученный из него стягиванием ребра (3,4) и G, полученный подразбиением того же ребра. В обоих случаях вновь добавленная вершина обозначена цифрой 7.

–  –  –

Объединение графов с непересекающимися множествами вершин часто называют их суммой и записывают как G1 + G2. Мы будем применять операцию сложения к любым графам, понимая под этим следующее: сначала вершины графов-слагаемых переименовываются так, чтобы множества вершин стали непересекающимися (очевидно, достаточно переименовать вершины одного слагаемого), затем полученные графы объединяются. По существу, речь идет о сложении абстрактных графов. Операция сложения абстрактных графов ассоциативна, то есть (G1 + G2) + G3 = G1 + (G2 + G3) для любых трех графов. Поэтому можно образовывать сумму любого числа графов, не указывая порядок действий с помощью скобок. Если складываются k экземпляров одного и того же графа G, то полученный граф обозначается через kG. Например, On nK1. На рисунке 1.20 изображен граф C4 + 2K2 + 4K1.

Рис. 1.20. Рис. 1.21.

Соединением двух графов G1 и G2 называется граф, получаемый из их суммы добавлением всех ребер, соединяющих вершины первого слагаемого с вершинами второго. Будем записывать эту операцию как G1 G2. На рисунке 1.21 представлен граф P3 O2. Легко видеть, что операции сложения и соединения графов связаны друг с другом следующими простыми соотношениями:

G1 + G2 = G1 o G2, G1 o G2 = G1 + G2.

Введем еще два типа специальных графов, которые легко описываются с помощью операции соединения. Первый – полный двудольный граф Kp, q = Op Oq. В этом графе множество вершин разбито на два подмножества (доли), в одном из которых p вершин, в другом q, и две вершины в нем смежны тогда и только тогда, когда они принадлежат разным подмножествам. Второй – колесо Wn = Cn K1. На рисунке 1.22 показаны графы K 3,4 и W6.

K3, 4 W6 Рис. 1.22.

Произведение G = G1 G2 графов G1 и G2 определяется следующим образом. Множеством вершин графа G является декартово произведение множеств VG1 и VG2, то есть вершины этого графа – упорядоченные пары (x, y), где x – вершина первого сомножителя, y – вершина второго. Вершины (x1, y1) и (x2, y2) в G смежны тогда и только тогда, когда x1 = x2 и y1 смежна с y2 в графе G2, или y1 = y2 и x1 смежна с x2 в графе G1. С помощью операции произведения можно выразить некоторые важные графы через простейшие. Например, произведение двух цепей дает прямоугольную решетку – см.

GtlBook1_0_7

рисунок 1.23.

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

=

–  –  –

Задачи На рисунке 1.25 изображен граф Петерсена. Выясните, можно ли из него получить граф K5 с 1.

помощью операций

a) удаления вершин и ребер и подразбиения ребер;

–  –  –

ОТВЕТ. a) Нельзя, так как при операциях удаления вершин и ребер степени оставшихся вершин не увеличиваются, а при подразбиении ребра вновь добавляемая вершина имеет степень 2. Но в графе Петерсена все вершины имеют степень 3, а в K5 – степень 4.

b) Можно – например, стягиванием ребер (1,6), (2,7), (3,8), (4,9), (5,10).

Проверьте, что каждый граф с 3 вершинами является либо суммой, либо соединением меньших 2.

графов. Верно ли это для графов с 4 вершинами?

ОТВЕТ. Неверно. Единственным графом с 4 вершинами, не разложимым ни в сумму, ни в соединение, является P4.

В графе G1 имеется n1 вершин и m1 ребер, а в графе G2 – n2 вершин и m2 ребер. Сколько ребер 3.

будет в графе G1 G2? В графе G1 G2?

ОТВЕТ. В G1 G2 будет m1 + m2 + n1n2 ребер, а в G1 G2 – n1m2 + n2m1 ребер.

–  –  –

ОТВЕТ. Неверен даже при G1 = G2 = G3 = K1. В левой части "равенства" получается граф с тремя вершинами, а в правой – с четырьмя.

1.3. Маршруты, связность, расстояния Маршруты, пути, циклы Маршрут в графе – это последовательность вершин x1, x2,K, xn, такая, что для каждого i = 1,2,K, n 1 вершины xi и xi +1 соединены ребром. Эти n 1 ребер называются ребрами маршрута, говорят, что маршрут проходит через них, а число n 1 называют длиной маршрута.

Говорят, что маршрут соединяет вершины x1 и xn, они называются соответственно началом и концом маршрута, вершины x 2, K, x n 1 – называются промежуточными. Маршрут называется замкнутым, если x1 = xn.

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

Цикл – это замкнутый путь. Цикл x1, x2,K, xn1, x1 называется простым, если вершины x1, x2,K, xn 1 все попарно различны.

В графе на рисунке 1.26 последовательность вершин 2, 3, 5, 4 – не маршрут;

2, 3, 4, 5, 1, 4, 3 – маршрут, но не путь;

3, 1, 4, 5, 1, 2 – путь, но не простой;

2, 3, 1, 4, 3, 1, 2 – замкнутый маршрут, но не цикл;

GtlBook1_0_7 2, 3, 1, 4, 5, 1, 2 – цикл, но не простой;

2, 3, 4, 5, 1, 2 – простой цикл.

–  –  –

Установим некоторые простые свойства путей и циклов.

ЛЕММА 1.3.

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

Дока за т ельст во. Пусть x1, x2,K, xn – маршрут. Если все его вершины различны, то это уже

–  –  –

x1, x2,K, xi 1, xi, x j +1,K, xn, полученная из этого маршрута удалением отрезка последовательности от xi +1 до x j, тоже является маршрутом. Новый маршрут соединяет те же вершины и имеет меньшую длину. Продолжая действовать таким образом, после конечного числа "спрямлений" получим простой путь, соединяющий x1 и xn.

–  –  –

Дока за т ельст во. Пусть x1, x2,K, xn, x1 – цикл, проходящий через ребро (a, b ). Если это ребро совпадает с ребром (xn, x1 ), то маршрут x1, x2,K, xn соединяет a и b, если же оно совпадает с

–  –  –

ЛЕММА 1.5.

Во всяком цикле, проходящем через некоторое ребро, содержится простой цикл, проходящий через это ребро.

Дока за те ль ст во. Пусть имеется цикл, проходящий через ребро (a, b ). Если удалить это ребро из графа, то по лемме 1.4 в полученном подграфе существует маршрут, соединяющий a и b. По лемме

1.3 существует простой путь x1, x2,K, xn, соединяющий эти вершины, то есть пара (a, b ) совпадает (как неупорядоченная пара) с парой (xn, x1). Но тогда x1, x2,…,xn, x1 – простой цикл в исходном графе, проходящий через ребро (a, b ).

Отметим, что в формулировке леммы 1.5 нельзя заменить слово "цикл" словами "замкнутый маршрут". Действительно, если (a, b ) – ребро графа, то последовательность a, b, a – замкнутый маршрут, проходящий через это ребро, но никакого цикла в нем нет.

ЛЕММА 1.6.

Если в графе степень каждой вершины не меньше 2, то в нем есть цикл.

–  –  –

Дока за т ельст во. Найдем в графе простой путь наибольшей длины (он существует, так как длина простого пути не может превышать n 1 ). Пусть это x1, x2,…,xn. Вершина xn смежна с xn 1, а так как ее степень не меньше двух, то она смежна еще хотя бы с одной вершиной, скажем, y. Если y была бы отлична от всех вершин пути, то последовательность x1, x2,K, xn, y была бы простым путем большей длины. Следовательно, y – это одна из вершин пути, y = xi, причем i n 1. Но тогда xi, xi +1,K, xn, xi – цикл.

Связность и компоненты Граф называется связным, если в нем для любых двух вершин имеется маршрут, соединяющий эти вершины. Заметим, что ввиду леммы 1.3 можно в этом определении заменить слово "маршрут" словами "простой путь".

Для произвольного графа определим на множестве вершин отношение соединимости: вершина a соединима с вершиной b, если существует соединяющий их маршрут. Легко видеть, что это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются областями связности, а порождаемые ими подграфы – компонентами связности графа. В связном графе имеется только одна компонента связности – весь граф. Компоненты связности можно определить также как максимальные по включению связные подграфы данного графа.

У графа на рисунке 1.27 четыре компоненты связности – они порождаются множествами вершин {1, 2, 9}, {3, 10, 11}, {4}, {5, 6, 7, 8, 12, 13, 14, 15}.

–  –  –

Вершина называется шарниром (или точкой сочленения), если при ее удалении число компонент связности увеличивается. У графа на рисунке 1.27 имеется четыре шарнира – это вершины 3, 6, 7, 8.

ЛЕММА 1.7.

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

Дока за т ельст во. Допустим, вершины a и b принадлежат одной компоненте связности и любой соединяющий их путь проходит через c. Тогда после удаления c не останется путей, соединяющих a и b, то есть эти вершины окажутся в разных компонентах связности. Значит, число компонент увеличилось и c – шарнир. Обратно, пусть c – шарнир. После удаления c некоторая компонента связности распадется на несколько компонент. Выберем в одной из этих новых компонент вершину a, а в другой – вершину b. Так как в графе, полученном удалением c, не существует путей, соединяющих a и b, то каждый из таких путей в исходном графе проходил через c.

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

Перешейками графа, изображенного на рисунке 1.27, являются ребра (3,10), (3,11), (6,7), (7,8), (7,13).

ЛЕММА 1.8.

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

Дока за т ельст во. Если через ребро (a,b) проходит цикл, то, по лемме 1.4, после удаления этого ребра вершины a и b останутся соединимыми, значит, число компонент связности не увеличится.

Обратно, если после удаления ребра (a,b) число компонент связности не увеличивается, то вершины a и b останутся в одной компоненте, то есть существует соединяющий их маршрут, не проходящий через это ребро. По лемме 1.3 в нем имеется простой путь x1, x2,…,xn, соединяющий a и b, но тогда x1, x2,…,xn, x1– цикл, проходящий через (a, b).

Метрические характеристики графов Расстоянием между двумя вершинами графа называется длина кратчайшего пути, соединяющего эти вершины. Расстояние между вершинами a и b обозначается через d (a, b ). Если в графе нет пути, соединяющего a и b, то есть эти вершины принадлежат разным компонентам связности, то расстояние между ними считается бесконечным. Легко видеть, что функция d (x, y ) обладает свойствами:

–  –  –

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

Расстояние от данной вершины a до наиболее удаленной от нее вершины называется эксцентриситетом вершины a и обозначается через e(a ). Таким образом,

–  –  –

Вершину с наименьшим эксцентриситетом называют центральной, а вершину с наибольшим – периферийной. Множество всех центральных вершин называется центром графа. Сама величина наименьшего эксцентриситета называется радиусом графа и обозначается через rad (G ), а величина наибольшего – диаметром и обозначается diam(G ). Иначе говоря,

–  –  –

Наименьший диаметр имеет полный граф – его диаметр равен 1. Среди связных графов с n вершинами наибольший диаметр, равный n 1, имеет цепь Pn.

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

Для графа, изображенного на рисунке 1.28, эксцентриситеты вершин приведены в таблице:

–  –  –

Центр этого графа составляют вершины 4, 6, 7; периферийные вершины – 1, 5 и 9; радиус его равен 3, а диаметр 5. Одна из диаметральных цепей порождается множеством вершин {1, 3, 6, 7, 8, 9}.

–  –  –

Маршруты и связность в орграфах Для ориентированного графа можно определить два типа маршрутов. Неориентированный маршрут (или просто маршрут) – это последовательность вершин x1, x2,K, xn, такая, что для

–  –  –

x1, x2,K, xn ведет из x1 в xn.

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

GtlBook1_0_7

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

Очевидно, разные области сильной связности не могут иметь общих вершин, так что множество вершин каждого орграфа разбивается на области сильной связности. Областями сильной связности орграфа на рисунке 1.29 являются множества {1, 2, 5}, {3, 4, 6, 7, 8}, {9}.

–  –  –

2. Сколько имеется в графе Qn путей длины n, соединяющих вершину (0, 0,...,0) с вершиной (1, 1,...,1)?

ОТВЕТ. n!

3. Какое наибольшее число шарниров может быть в графе с n вершинами?

ОТВЕТ. n – 2.

РЕШЕНИЕ. В графе Pn ровно n – 2 шарнира. Чтобы доказать, что ни в каком графе их не может быть больше, рассмотрим диаметральную цепь в произвольном графе. Пусть a и b – концевые вершины этой цепи. Допустим, что a – шарнир. Тогда при удалении вершины a число компонент связности увеличивается, причем оставшаяся часть цепи целиком лежит в одной из "новых" компонент связности. Возьмем вершину x, смежную с a и принадлежащую другой "новой" компоненте. Тогда любой путь из x в b в исходном графе проходит через a. Отсюда следует, что d (x, b ) = d (a, b ) + 1, а это противоречит тому, что d (a, b ) – диаметр графа. Следовательно, концы диаметральной цепи не могут быть шарнирами, то есть в графе имеется не более n – 2 шарниров.

–  –  –

1.4. Деревья Определение и элементарные свойства Деревом называется связный граф, не имеющий циклов. В графе без циклов, таким образом, каждая компонента связности является деревом. Такой граф называют лесом.

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

ЛЕММА 1.9.

В дереве для любых двух вершин существует единственный соединяющий их простой путь.

Дока за т ельст во. Существование пути следует из связности дерева. Допустим, что в некотором дереве существуют два различных простых пути, соединяющих вершины a и b. Начальные отрезки этих путей совпадают (оба пути начинаются в одной и той же вершине a) Пусть x – последняя вершина этого совпадающего начала, а после x в одном пути следует вершина y1, а в другом – y2.

Рассмотрим ребро (x, y1 ). Если его удалить из графа, то в оставшемся подграфе вершины y1 и x будут соединимыми – соединяющий их маршрут можно построить так: взять отрезок первого пути от y1 до a и к нему присоединить отрезок второго от x до a, взятый в обратном порядке. Но это означает, что ребро (x, y1 ) не является перешейком. Однако из леммы 1.8 следует, что в дереве каждое ребро является перешейком.

Из леммы 1.6 следует, что во всяком дереве, в котором не меньше двух вершин, имеется вершина степени 1.

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

ЛЕММА 1.10. Вершина дерева является шарниром тогда и только тогда, когда она не лист.

Дока за т ельст во. Если вершина a не является листом, то она смежна по крайней мере с двумя другими вершинами, b1 и b2. Их соединяет путь b1, a, b2, проходящий через a, а по лемме 6 этот путь

– единственный. Значит, после удаления a вершины b1 и b2 окажутся в разных компонентах связности, то есть a – точка сочленения. Если же вершина a – лист, то она не может принадлежать никакому пути, кроме такого, который начинается или оканчивается в a (всякая промежуточная вершина пути инцидентна двум различным ребрам пути). Значит, при удалении a все пути, соединяющие остальные вершины, останутся в неприкосновенности, то есть a не является точкой сочленения.

ТЕОРЕМА 1.11.

Граф с n вершинами и m ребрами является деревом тогда и только тогда, когда он удовлетворяет любым двум из следующих трех условий:

–  –  –

2) не имеет циклов;

Дока за т ельст во. Первые два условия вместе составляют определение дерева. Покажем, что выполнение любых двух из условий (1) – (3) влечет выполнение третьего.

(1) и (2) (3). Индукция по числу вершин. При n = 1 утверждение очевидно. При n 2 в дереве имеется хотя бы один лист. Если из дерева удалить лист, то снова получится дерево, так как циклов не появится, а связность сохранится (по лемме 1.10 лист не является шарниром). В этом новом дереве n – 1 вершина и, по предположению индукции, n – 2 ребра. Следовательно, в исходном дереве было n – 1 ребро.

–  –  –

k = 1 и граф связен.

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

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

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

ЛЕММА 1.12.

В дереве для каждой вершины a имеется не более одной смежной с ней вершины b такой, что e(b ) e(a ).

Дока за т ельст во. Пусть x – вершина, наиболее удаленная от a, то есть e(a ) = d (a, x ).

Единственный путь из a в x проходит через одну из вершин, смежных с a, пусть это вершина b. Если c – другая вершина, смежная с a, то единственный путь из c в x проходит через b и его длина на единицу больше длины пути из a в x. Следовательно, e(c ) d (c, x ) d (a, x ) = e(a ).

ТЕОРЕМА 1.13.

Центр дерева состоит из одной вершины или двух смежных вершин.

Дока за т ельст во. Допустим, что в некотором дереве существуют две несмежные центральные вершины a и b. Рассмотрим путь, соединяющий эти вершины, и найдем на этом пути

–  –  –

промежуточную вершину x с максимальным эксцентриситетом. Так как a и b – вершины с наименьшим эксцентриситетом в дереве, то эксцентриситет x также не меньше эксцентриситета этих вершин. Но тогда оказывается, что e( x ) не меньше эксцентриситетов двух смежных с ней вершин – предшествующей ей и следующей за ней на пути, а это противоречит лемме 1.12.

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



Pages:   || 2 | 3 |
Похожие работы:

«ПРОЕКТ УЧЕБНО-МЕТОДИЧЕСККОГО КОМПЛЕКТА ТИПОВОЙ ПРОГРАММЫ ПОДГОТОВКИ ПРЕДСТАВИТЕЛЕЙ ЭКСПЕРТНЫХ ОРГАНИЗАЦИЙ ДЛЯ ВКЛЮЧЕНИЯ В РЕЕСТР ЭКСПЕРТОВ И ЭКСПЕРТНЫХ ОРГАНИЗАЦИЙ, ПРИВЛЕКАЕМЫХ ДЛЯ ОЦЕНКИ КАЧЕСТВА ОБРАЗОВАНИЯ И СЕРТИФИКАЦИИ ПРОФЕССИОНАЛЬНЫХ КВАЛИФИКАЦИЙ Содержание ВВЕДЕНИЕ 1 НАИМЕНОВАНИЕ 2 ОБЛАСТЬ ПРИМЕНЕНИЯ 3 НОРМАТИВНЫЕ ССЫЛКИ 4 ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ 5 ЦЕЛИ И ЗАДАЧИ 6 СОДЕРЖАНИЕ И УСЛОВИЯ РЕАЛИЗАЦИИ 6.1 Структура программы 6.2 Содержание программы 6.3 Результаты освоения программы 6.4...»

«Содержание 6.1 Пояснительная записка. Введение.Особенности дисциплины..9. Цель и задачи дисциплины.. Место дисциплины в учебном процессе.10 Требования к знаниям, умениям и навыкам.10 6.2. Перечень и содержание разделов дисциплины.12 6.3 Примерный перечень семинарских, практических занятий.1 6.4 Перечень самостоятельной работы студента.2 6.5. Контроль результативности учебного процесса.27 6.6. Требования к ресурсам..2 6.7. Учебно-методические материалы по дисциплине.28 Приложение 1 Вопросы...»

«ФЕДЕРАЛЬНАЯ СИСТЕМА ВНЕШНЕЙ ОЦЕНКИ КАЧЕСТВА КЛИНИЧЕСКИХ ЛАБОРАТОРНЫХ ИССЛЕДОВАНИЙ НП «ЦЕНТР ВНЕШНЕГО КОНТРОЛЯ КАЧЕСТВА КЛИНИЧЕСКИХ ЛАБОРАТОРНЫХ ИССЛЕДОВАНИЙ» КАТАЛОГ ФСВОК-2015 КРАТКИЕ СВЕДЕНИЯ О ФСВОК КРАТКИЕ СВЕДЕНИЯ О ФЕДЕРАЛЬНОЙ ФСВОК КРАТКИЕ СВЕДЕНИЯ О СИСТЕМЕ ВНЕШНЕЙ ОЦЕНКИ КАЧЕСТВА КЛИНИЧЕСКИХ ЛАБОРАТОРНЫХ ИССЛЕДОВАНИЙ (ФСВОК) 1. Внешняя оценка качества исследований, выполняемых в клиникодиагностических лабораториях (КДЛ), является одной из важнейших составляющих обеспечения их...»

«П рав ител ьство Уд мурт Эл ькун Уд муртс кой Рес публ ики Кив ал тэт 426007, г. Ижевск, Дом Правительства От 28.03.2011 г. № 1-422/184 На № от Руководителям территориальных органов федеральных органов исполнительной власти, исполнительных органов государственной власти Удмуртской Республики Главам муниципальных образований в Удмуртской Республике Начальнику Главного управления Министерства Российской Федерации по делам гражданской обороны, чрезвычайным ситуациям и ликвидации последствий...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Кемеровский государственный университет» Прокопьевский филиал (Наименование факультета (филиала), где реализуется данная дисциплина) Рабочая программа дисциплины (модуля) Б3.В.ДВ.7.2Религиоведение (Наименование дисциплины (модуля)) Направление подготовки 39.03.02 /040400.62 Социальная работа (шифр, название направления) Направленность...»

«Сайт Лаборатории «Универсальный решатель» www.trizway.com Ссылка на сайт и автора при полной или частичной перепечатке данного материала обязательна Гин С. И. Мир фантазии МЕТОДИЧЕСКОЕ ПОСОБИЕ ДЛЯ УЧИТЕЛЯ НАЧАЛЬНОЙ ШКОЛЫ Москва Издательство «Вита-Пресс» Курс «Мир фантазии» ставит своей задачей обучить детей навыкам творческого мышления и управляемого воображения. Методологическую основу курса составляют приемы развития творческого воображения из теории решения изобретательских задач (ТРИЗ)....»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ НЕФТИ И ГАЗА ИМЕНИ И.М. ГУБКИНА АННОТАЦИЯ ОСНОВНАЯ ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА ВЫСШЕГО ОБРАЗОВАНИЯ Направление подготовки 21.04.01 НЕФТЕГАЗОВОЕ ДЕЛО Программа подготовки МОДЕЛИРОВАНИЕ РАЗРАБОТКИ НЕФТЯНЫХ МЕСТОРОЖДЕНИЙ Квалификация выпускника МАГИСТР Нормативный срок обучения 2 ГОДА Форма обучения ОЧНАЯ г. Москва 201 Назначение ООП ВО ООП ВО представляет собой систему документов, разработанную и...»

«СОДЕРЖАНИЕ 1. ОБЩИЕ ПОЛОЖЕНИЯ 1.1 Нормативные документы для разработки ООП по направлению подготовки.....4 1.2 Общая характеристика ООП 1.3 Миссия, цели и задачи ООП ВПО 1.4 Требования к абитуриенту 2. ХАРАКТЕРИСТИКА ПРОФЕССИОНАЛЬНОЙ ДЕЯТЕЛЬНОСТИ ВЫПУСКНИКА ПО НАПРАВЛЕНИЮ ПОДГОТОВКИ 2.1 Область профессиональной деятельности выпускника 2.2 Объекты профессиональной деятельности выпускника 2.3 Виды профессиональной деятельности выпускника 2.4 Задачи профессиональной деятельности выпускника 3....»

«ЧОУ ВПО «НЕВСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ И ДИЗАЙНА» УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ЦВЕТОВЕДЕНИЕ И КОЛОРИСТИКА 070601.65 Дизайн Цветоведение и колористика МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ ДЛЯ СТУДЕНТОВ Специальность 070601.65 Дизайн Санкт-Петербург МУЗАОЦветоведениеКолористикаА5.doc 1. Организационно-методический раздел Дисциплина «Цветоведение и колористика» предназначена для студентов, специализирующихся в области дизайнерской деятельности, и имеет не только общеобразовательную, но и...»

««Ученые заметки ТОГУ» Том 6, № 1, 2015 ISSN 2079-8490 Электронное научное издание «Ученые заметки ТОГУ» 2015, Том 6, № 1, С. 57 – 63 Свидетельство Эл № ФС 77-39676 от 05.05.2010 http://pnu.edu.ru/ru/ejournal/about/ ejournal@pnu.edu.ru УДК 54.062 © 2015 г. Л. П. Майорова, д-р хим. наук, Л. А. Соболевская (Тихоокеанский государственный университет, Хабаровск) СОВЕРШЕНСТВОВАНИЕ МЕТОДИК ОПРЕДЕЛЕНИЯ АЦЕТОНА И МЕТАНОЛА В ПРОБАХ ПРИРОДНЫХ И СТОЧНЫХ ВОД В статье рассмотрены актуальность...»

«Содержание Раздел 1. Перечень планируемых результатов обучения по дисциплине» История»...4 Раздел 2. Место дисциплины в структуре образовательной программы.5 Раздел 3. Объем дисциплины в зачетных единицах с указанием количества академических часов, выделенных на контактную работу обучающихся с преподавателем (по видам учебных занятий) и на самостоятельную работу обучающихся...5 Раздел 4. Содержание дисциплины, структурированное по темам (разделам) с указанием отведенного на них количества...»

«РАБОЧАЯ ПРОГРАММА по математике 6 класс учебник А. Г. Мерзляк., В. Б. Полонский 2014-2015 учебный год Составила Михайлова О.В. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Нормативными документами для составления программы являются: Федеральный компонент государственного образовательного стандарта начального общего, основного общего и среднего (полного) общего образования. Математика. в соответствии с авторской программой А.Г. Мерзляк, В.Б. Полонский, М.С. Якир, Е.В. Буцко (Математика: программы : 5–9 классы А.Г....»

«Отчёт о проведении мероприятий за период с 07.09.2015 г. по 11.09.2015 г.В отчетный период МУ ДПО «Воскресенский научно-методический центр» были проведены следующие мероприятия: 07 сентября 2015 года МУ ДПО «ВНМЦ» было организовано и проведено РМО учителей английского языка на тему «Основные задачи и направления работы РМО учителей английского языка в 2015–2016 учебном году. Утверждение плана работы на новый учебный год», на котором присутствовало 42 учителя английского языка...»

«Содержание ПОЯСНИТЕЛЬНАЯ ЗАПИСКА..3 ЦЕЛИ И ЗАДАЧИ ОСВОЕНИЯ ДИСЦИПЛИНЫ 1. МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП ВПО.3 2. ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ СОДЕРЖАНИЯ 3. ДИСЦИПЛИНЫ..3 СОДЕРЖАНИЕ И СТРУКТУРА ДИСЦИПЛИНЫ..5 4.4.1. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ..5 4.2. СТРУКТУРА ДИСЦИПЛИНЫ..6 4.3.ЛЕКЦИИ...6 4.4. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ (СЕМИНАРЫ)..7 4.5 ЛАБОРАТОРНЫЕ РАБОТЫ..7 4.6 КУРСОВЫЕ РАБОТЫ..7 САМОСТОЯТЕЛЬНОЕ ИЗУЧЕНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ.7 4.7 ОБРАЗОВАТЕЛЬНЫЕ ТЕХНОЛОГИИ.12 5. 5.1. ОБРАЗОВАТЕЛЬНЫЕ...»

«РОСЖЕЛДОР Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Ростовский государственный университет путей сообщения» (ФГБОУ ВПО РГУПС) Rostov State Transport University ТРУДЫ МЕЖДУНАРОДНОЙ НАУЧНО-ПРАКТИЧЕСКОЙ ИНТЕРНЕТ-КОНФЕРЕНЦИИ «ПРЕПОДАВАТЕЛЬ ВЫСШЕЙ ШКОЛЫ В ХХI ВЕКЕ» International Scientific-Practical INTERNET Conference “THE TEACHER OF A HIGHER SCHOOL IN THE 21-ST CENTURY” Сборник 1 Volume Ростов-на-Дону ББК 74.58 + 0 Труды 12-й...»

«ТОР-103. Учебное направление «Вибродиагностика» Артикул 103-10.Комплект пластиковых учебно-методических плакатов в тубусе: «Основы вибрационной диагностики» (вибрация и колебания, колебательные силы, тренды, методы вибродиагностики, виды приборов и систем, ГОСТ 10816, виды неуравновешенности роторов, оборудование для вибродиагностики).Описание: Комплект учебных плакатов предназначен как визуальное наглядное пособие для специалистов отделов вибродиагностики, ремонтных служб промышленных...»

«СОДЕРЖАНИЕ 1.Общие положения 1.1 Основная профессиональная образовательная программа (определение). 4 1.2 Нормативные документы для разработки ОПОП. 4 1.3 Общая характеристика основной профессиональной образовательной программы ВО.. 5 1.3.1. Цель (миссия) ОПОП бакалавриата. 1.3.2. Срок получения образования.. 1.3.3 Объем основной профессиональной образовательной программы. 1.4 Требования к уровню подготовки, необходимому для освоения ОПОП бакалавриата.. 5 2.Характеристика профессиональной...»

«\ql Приказ Минприроды России от 16.12.2013 N Об утверждении Методических указаний по заполнению формы плана тушения лесных пожаров (Зарегистрировано в Минюсте России 21.03.2014 N 31675) Документ предоставлен КонсультантПлюс www.consultant.ru Дата сохранения: 04.02.2015 Приказ Минприроды России от 16.12.2013 N 591 Документ предоставлен КонсультантПлюс Об утверждении Методических указаний по заполнению формы плана Дата сохранения: 04.02.2015 тушения лес. Зарегистрировано в Минюсте России 21 марта...»

«I. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Рабочая программа по русскому языку для 4 класса составлена на основе Федерального государственного образовательного стандарта начального общего образования,программы для четырехлетней начальной школы образовательной системы Д.Б. Эльконина В.В. Давыдова. Программа рассчитана на 4 класс по системе 14 с учётом типа учебного заведения. Вся программа по русскому языку рассчитана на прохождение учебного материала с учётом годового календарно-учебного графика гимназии....»

«О. Т. ПОГЛАЗОВА Методические рекомендации к учебнику для 4 класса общеобразовательных организаций Пособие для учителя Смоленск Ассоциация XXI век УДК 373.167.1:502+502(075.2) ББК 20.1я. П Поглазова О. Т. П43 Окружающий мир: методические рекомендации к учебнику для 4 класса общеобразовательных организаций / О. Т. Поглазова. – Смоленск: Ассоциация XXI век, 2014. – 368 с. – ISBN 978-5-418-00763-6 Данное пособие написано специально для учителей, ведущих (или предполагающих вести) уроки по предмету...»







 
2016 www.metodichka.x-pdf.ru - «Бесплатная электронная библиотека - Методички, методические указания, пособия»

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