![]()
|
|||||||||||||
ДОМАШНЄ ЗАВДАННЯ. ЛІТЕРАТУРА. ПРАКТИЧНЕ ЗАНЯТТЯ №6ДОМАШНЄ ЗАВДАННЯ 1.
2.
3. Робота з індивідуальним завданням.
ЛІТЕРАТУРА
1. Алферова З. В. Математическое обеспечение экономических расчетов с помощью графов. – М.: Статистика, 1994. – С. 18-23. 2. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974. – С. 30-34, 136-143. 3. Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. – М.: Высшая школа, 1976. – С. 43-59. 4. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984. – С. 39-40, 105-108. ДИСКРЕТНА МАТЕМАТИКА” ПРАКТИЧНЕ ЗАНЯТТЯ №6
Тема. “РОЗРІЗИ ГРАФА. РОЗФАРБУВАННЯ ГРАФА”.
ПЛАН 1. Розрізи і розділяючі множини графа. 2. Матриця розрізів. 3. Розфарбування графа. 4. Хроматичне число. Хроматичний поліном.
Завдання 1. Для заданого графа
Завдання 2. Якою мінімальною кількістю фарб і скількома способами можна розфарбувати дерево? Вивести формулу для знаходження
Завдання 3. Якою мінімальною кількістю фарб можна вершинно розфарбувати парний цикл? Непарний цикл? Скількома способами можна це зробити? Вивести формулу для знаходження
Завдання 4. Правильно вершинно розфарбувати мінімальною кількістю фарб даний граф G. Скількома способами можна це зробити?
|
|||||||||||||
|