Logo GenDocs.ru

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

Загрузка...

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


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

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

ЛЕКЦИЯ 10_раскраски,планарность.doc43kb.22.11.2005 21:28скачать
ЛЕКЦИЯ 11_ПФ.doc43kb.11.12.2005 00:59скачать
ЛЕКЦИЯ 12_ДНФ,КНФ.doc67kb.07.12.2005 00:32скачать
ЛЕКЦИЯ 13_ФПС.doc42kb.14.12.2005 01:41скачать
ЛЕКЦИЯ 14_замкнутость_систем.doc20kb.22.09.2004 21:53скачать
ЛЕКЦИЯ 1_множества.rtf51kb.26.09.2007 22:21скачать
ЛЕКЦИЯ 2_подмножества.doc358kb.04.11.2006 15:18скачать
ЛЕКЦИЯ 3_отношения.rtf45kb.12.09.2007 02:32скачать
ЛЕКЦИЯ 4_эквивалентность,порядок.doc43kb.12.09.2006 01:01скачать
ЛЕКЦИЯ 5_функции,морфизмы.doc43kb.19.09.2007 02:11скачать
ЛЕКЦИЯ 6_основы_графов.doc32kb.24.10.2005 16:16скачать
ЛЕКЦИЯ 7_части_графа,связность.doc36kb.19.11.2005 02:21скачать
ЛЕКЦИЯ 8_деревья.doc30kb.08.11.2005 02:19скачать
ЛЕКЦИЯ 9_циклы.doc31kb.15.11.2005 03:58скачать
Формы представления булевых функций.doc116kb.29.12.2005 12:24скачать

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

Если æ(G).=2, то =s(G).

При этом в графе существует паросочетание, охватывающее все вершины наибольшей степени.

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

Граф внешнепланарен, если он предполагает такую укладку, при которой все вершины лежат на краю одной (внешней) грани.
^ КРИТЕРИИ ПЛАНАРНОСТИ ГРАФОВ.

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

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

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

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

  2. Понтрягина – Куратовского. Граф планарен, если он не содержит частей,

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



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

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

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