Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по дискретной математике - файл ЛЕКЦИЯ 10_раскраски,планарность.doc


Лекции по дискретной математике
скачать (3853.6 kb.)

Доступные файлы (14):

ЛЕКЦИЯ 10_раскраски,планарность.doc45kb.17.10.2007 21:13скачать
ЛЕКЦИЯ 11_ПФ.doc43kb.10.12.2005 22:59скачать
ЛЕКЦИЯ 12_ДНФ,КНФ.doc67kb.06.12.2005 22:32скачать
ЛЕКЦИЯ 13_ФПС.doc42kb.13.12.2005 23:41скачать
ЛЕКЦИЯ 1_множества.rtf51kb.26.09.2007 20:21скачать
ЛЕКЦИЯ 2_подмножества.doc358kb.04.11.2006 13:18скачать
ЛЕКЦИЯ 3_отношения.rtf45kb.12.09.2007 00:32скачать
ЛЕКЦИЯ 4_эквивалентность,порядок.doc43kb.11.09.2006 23:01скачать
ЛЕКЦИЯ 5_функции,морфизмы.doc43kb.19.09.2007 00:11скачать
ЛЕКЦИЯ 6_основы_графов.doc32kb.24.10.2005 14:16скачать
ЛЕКЦИЯ 7_части_графа,связность.doc36kb.19.11.2005 00:21скачать
ЛЕКЦИЯ 8_деревья.doc30kb.08.11.2005 00:19скачать
ЛЕКЦИЯ 9_циклы.doc31kb.15.11.2005 01:58скачать
планарность графов.pdf3881kb.27.10.2008 13:12скачать

содержание
Загрузка...

ЛЕКЦИЯ 10_раскраски,планарность.doc

Реклама MarketGid:
Загрузка...
ЛЕКЦИЯ 10.

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

Паросочетание – это множество ребер, в котором никакие два не являются смежными.

Паросочетание совершенно, если оно полностью покрывает множество вершин графа.

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

Раскраска графов

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

^ Раскраска графа – это разбиение элементов графа на множества, каждое из которых имеет одну и ту же цветовую нагрузку.

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

^ Правильная раскраска вершин в æ цветов - это разбиение V=V1 V2…Væ так, что = но каждое из Vi не пусто. В этом случае никакие две смежные вершины не раскрашены в один цвет.

Наименьшее из æ при условии правильности раскраски называется хроматическим числом æ(G).

ПРИМЕР: 1). составление расписания – один преподаватель не может быть одновременно на двух лекциях. В построенном графе смежными будут предметы, которые не могут читаться одновременно.

2). æ= 1 у пустого графа

3). æ= n у полного графа

4). æ= 2 у двудольного графа (бихроматичность)
^ Правильная раскраска ребер в  цветов - это разбиение множества ребер Е=Е1 Е2…. Е, где = и каждое Еi образует паросочетание в G.

Наименьшее из  при условии правильности раскраски называется хроматическим индексом (G).

Для хроматического индекса существуют верхняя и нижняя оценки:

.

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

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

Пример: различные раскраски

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

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

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

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

Ровно одну из граней произвольно можно выбрать внешней.

Множество граничных точек грани называется ее краем.

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

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

1). Любой граф, не являющийся деревом, можно представить матрицей циклов и матрицей разрезов.

^ Матрица разрезов получается из матрицы инцидентности заменой петель на 0 и элементарными преобразованиями матриц так, чтобы первые столбцы представляли собой единичную матрицу. По строкам оставшейся части матрицы располагаются простые разрезы.

Из матрицы разрезов можно получить матрицу циклов: ЕСCC/E(CT)E. В такой матрице по строкам располагаются простые циклы графа.

Пример:
2). Граф G*(V*,E*) называется двойственным к G(V,E), если между их ребрами можно установить взаимно-однозначное соответствие, при котором некоторая матрица разрезов графа G в то же время оказалась матрицей циклов графа G* И наоборот: некоторая матрица разрезов графа G* в то же время оказалась матрицей циклов графа G.

Отношение двойственности симметрично. Два графа, двойственные одному и тому же графу могут быть и не изоморфными.

Существуют графы, не имеющие двойственных, например, "3 дома и 3 колодца".

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

Граф максимально планарен, если он планарен, но утрачивает это свойство после операции добавления ребра.

Граф внешнепланарен, если он предполагает такую укладку, при которой все вершины лежат на краю одной (внешней) грани.

3). Дополнительные операции с элементами графа:

а) разбиение ребра вершиной

в) стягивание ребра

с) расщепление вершины

операция а) позволяет задать отношение гомеоморфности графов.
^ КРИТЕРИИ ПЛАНАРНОСТИ ГРАФОВ.

  1. Мак-Лейна. Пусть граф G(V,E) –произвольный, а Gc- его часть, полученная удалением петель, мостов и голых вершин. Граф G планарен, если часть Gc – пуста или множество ее ребер можно разбить на линейно независимую систему разрезов длины хроматического числа æ(Gс), в которых каждое ребро лежит ровно в двух разрезах.

Упрощенная формулировка была дана Эйлером: (^ Характеристика Эйлера).

В связном планарном графе |V|-|E|+i=2, где i – количество граней.

  1. Уитни. Граф планарен, если у него есть двойственный.

  2. Понтрягина – Куратовского. Граф планарен, если он не содержит частей, гомеоморфных полному графу на 5 вершинах или двудольному на 6 вершинах.

  3. ^ Харрари – Татта. Является обобщением Понтрягина-Куратовского. Планарный граф невозможно превратить в граф, гомеоморфный полному графу на 5 вершинах или двудольному на 6 вершинах ("3 дома и 3 колодца").



Скачать файл (3853.6 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации