Федеральне агентство з освіти Російської Федерації
Волгоградський державний технічний університет
Контрольна робота
з дискретної математики
Варіант №21
Виконав: студент групи
АУЗ - 161с Тюляева І.А.
Перевірив: Акулов Л.Г.
Волгоград +2010
Дано варіант №21:
Завдання 1
Задати граф наступними способами: перерахуванням, матрицями суміжності і інцидентності.
Рішення:
Спосіб перерахування:
Безліч вершин:
={x1, x2, x3, x4, x5}
Безліч зв'язків:
={ lt; x1 x2 gt ;, lt; x1 x3 gt ;, lt; x2 x4 gt ;, lt; x3 x4 gt ;, lt; x3 x5 gt;}
Безліч ізольованих вершин: пусто.
Матриця інцидентності:
V1V2V3V4V5X111000X2-10001X30-1110X4000-1-1X500-100
Матриця суміжності:
X1X2X3X4X5X101100X200010X300011X400000X500000
Завдання 2
Визначити наступні основні характеристики графа:
- число ребер і дуг;
- число вершин;
коефіцієнт зв'язності графа;
ступеня усіх вершин;
цикломатичне число графа.
Рішення:
Число ребер - 0. Число дуг - 5.
Кількість вершин - 5.
Коефіцієнт зв'язності графа - 1.
Ступені всіх вершин:
Х1Х2Х3Х4Х5Полустепень ісхода21200Полустепень захода01121Степень22320
Цикломатичне число графа=(число зв'язків - число вершин) + коефіцієнт зв'язності.
Таким чином
5-5 + 1=1;
цикломатичне число дорівнює 1.
Завдання №3
Визначити, чи є даний граф:
- планарним або плоским графом (обгрунтувати відповідь і виконати зворотне перетворення);
- дводольним графом (обгрунтувати відповідь і, якщо необхідно, то добудувати до двудольного графа);
деревом (обгрунтувати відповідь і, у разі циклічного графа, привести один з варіантів основного дерева);
псевдографом або мультиграфом, або простим графом (обгрунтувати відповідь і виконати необхідні перетворення).
Рішення:
Даний граф є плоским, тому всі його зв'язки перетинаються тільки у вершинах. Перетворимо даний граф в планарний граф:
Даний граф не є дводольним, тому має цикли непарної довжини. Перетворимо даний граф в двочастковий шляхом додавання нової вершини X6, нової зв'язку V6 і перенесенням зв'язку V4 в інше положення:
Даний граф не є деревом, оскільки він містить цикли. Перетворимо даний граф в дерево шляхом виключення дуги V4:
Даний граф є простим, тому як не містить петель і кратні зв'язки.
Перетворимо даний граф в мультіграф:
Перетворимо даний граф в псевдографів:
Завдання 4
Привести приклад подграфа, часткового графа і часткового подграфа.
Рішення:
Подграф:
Частковий подграф:
Частковий граф:
Завдання 5
Провести реберну і вершинну розмальовки графа з визначенням вершинного і реберного хроматичного числа.
Рішення:
Необхідно виходити з того, що граф називається правильно розфарбованим, якщо його суміжні вершини (зв'язку) розфарбовані в різні кольори.
Примітка: Позначимо кольору через числа натурального ряду. Номер поряд з кожною вершиною (зв'язком) позначає певний колір.
Вершинна розфарбування:
Хроматичні число дорівнює 2
Реброва розфарбування:
Хроматичні число дорівнює 3
