АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Хроматическое число

Нахождение хроматического числа в графе

ЦЕЛЬ РАБОТЫ

1.1.1 Изучить теоретические сведения по характеристике графов.

1.1.2 Получить практические навыки по нахождению хроматического числа в графе.

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

1.2.1 Методические указания по выполнению практической работы.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1.3.1 Изучить методические указания к практической работе.

1.3.2 Выберите граф согласно варианту и выполните раскраску данного графа. Найдите хроматическое число в графе.

СОДЕРЖАНИЕ ОТЧЕТА

1.4.1 Цель работы

1.4.2 Методические рекомендации

1.4.3 Порядок выполнения работы

1.4.4 Ответы на контрольные вопросы

1.4.5 Выводы

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.5.1 Алгоритм раскрашивания графов?

1.5.2 Что такое хроматическое число? Как его найти?

1.5.3 Теорема о пяти красках?

1.5.4 Какой граф называется планарным?

1.5.5 Что такое одноцветный класс?

1.5.6 Какой граф называется пространственным?

ПРИЛОЖЕНИЕ 1

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

РАСКРАСКА ГРАФОВ

Хроматическое число

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

Наименьшее возможное число цветов в раскраске называется хроматическим числом.

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

Планарность

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

Плоский граф – это граф, уже уложенный на плоскости.

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

Если в пересечении ребер точки нет, то граф пространственный.

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

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

Дата добавления: 2015-09-27 | Просмотры: 464 | Нарушение авторских прав