Тема 3.6. Раскраска графов

Тема 3.5. Плоские и неплоские графы

Тема 3.4. Деревья и обходы графов

Тема 3.3. Разбиения и расстояния в графах

Тема 3.2. Матричные представления графов

Тема 3.1. Основные понятия теории графов, типы графов

Практическое (семинарское) занятие № 9:

Изучение основных классов графов.

1. Изучение типов и классов графов. Различимость графов.

2. Построение производных графов.

3. Установление графичности степенной последовательности.

Вопросы самоконтроля:

а) Что такое изоморфизм графов?

б) Как определяется дополнение графа?

в) Как строится реберный граф?

г) Могут ли все вершины графа иметь разные степени?

д) Когда граф является связным?

Практическое (семинарское) занятие № 10:

Изучение матричных представлений графов.

1. Построение матриц для ориентированных графов.

2. Построение матриц для неориентированных графов.

Вопросы самоконтроля:

а) Что такое матрица смежности графа?

б) Однозначно ли задается граф матрицей инциденций?

в) Могут ли быть разные матрицы смежностей у изоморфных графов?

г) Могут ли совпадать матрицы смежностей у неизоморфных графов?

Практическое (семинарское) занятие № 11:

Исследование метрических свойств графов.

1. Изучение метрических инвариантов графов.

2. Построение кратчайших расстояний методом Дейкстры.

Вопросы самоконтроля:

а) Что такое радиус и диаметр графа?

б) Однозначно ли задается граф матрицей расстояний?

в) Могут ли совпадать метрические инварианты у неизоморфных графов?

г) Чему равен радиус простой цепи?

Практическое (семинарское) занятие № 12:

Исследование ациклических структур.

1. Изучение свойств деревьев.

2. Нахождение каркасов наименьшего веса.

Вопросы самоконтроля:

а) Какой величины может быть центр дерева?

г) Чему равно цикломатическое число графа?

в) Чем отличаются алгоритмы Прима и Краскала?

Практическое (семинарское) занятие № 13:

Изучение обходов ребер и вершин графов.

1. Характеризация эйлеровых и гамильтоновых циклов графа.

Вопросы самоконтроля:

а) Может ли граф быть эйлеровым и гамильтоновым?

б) Полный граф всегда имеет эйлеров цикл?

г) Может ли гамильтонов граф иметь мосты?

Практическое (семинарское) занятие № 14:

Исследование расположения графа на плоскости.

1. Исследование свойств плоских графов

Вопросы самоконтроля:

а) Чем отличаются плоский и планарный графы?

б) Полный граф всегда имеет эйлеров цикл?

в) Является ли полный граф на 6 вершинах планарным?

г) Чему равна сумма размеров граней плоского графа?

д) Когда двойственный граф будет мультиграфом?

Практическое (семинарское) занятие № 15:

Изучение раскрасок абстрактных и плоских графов.

1. Исследование раскрасок графов общего вида

2. Исследование раскрасок плоских графов

Вопросы самоконтроля:

а) Чему равно хроматическое число деревьев?

б) В каких графах хроматический индекс равен 2?

в) Чему равно хроматическое число реберного графа звезды?

г) В каких графах хроматическое число равно числу вершин?

Раздел 4. Булевы функции и логические исчисления

Дата добавления: 2014-01-05