Рішення задач із застосуванням теорії графів
Зміст
Введення
Завдання № 1
Завдання № 2
Завдання № 3
Завдання № 4
Завдання № 5
Висновок
Список використаних джерел
Введення
граф дискретна математика
Теорія графів - розділ дискретної математики, що вивчає властивості графів. У загальному значенні граф представляється як безліч вершин (вузлів), з'єднаних ребрами. У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якого рахункового безлічі, а E - підмножина V Г— V.
Останнім часом теорія графів стала простим, доступним і потужним засобом вирішення питань, що відносяться до широкого кола проблем. Це проблеми проектування інтегральних схем і схем управління, дослідження логічних ланцюгів, блок-схем програм, економіки та статистики, хімії та біології, теорії розкладів і дискретної математики. p align="justify"> Метою даної роботи є практичне закріплення науково-теоретичних матеріалів теорії графів та отримання навичок застосування отриманих знань для вирішення конкретних завдань.
1 Завдання № 1
Формулювання завдання
Дана матриця суміжності для графа G. На основі аналітичних виразів для прямого і зворотного транзитивних замикань знайти всі компоненти зв'язності для даного графа. Результати обчислень перевірити шляхом безпосередніх перетворень матриць суміжності. У звіті про виконане завдання привести два малюнки: графічне зображення вихідного графа, коли його вершини в порядку зростання номерів розташовані по колу, на зразок циферблата, і цього ж графа, але розкладені на сильно пов'язані підграфи. p align="justify"> Матриця суміжності представлена ​​на малюнку 1.1.
В
Малюнок 1.1 - Матриця суміжності вихідного графа
Рішення
Для початку наведемо графічне зображення вихідного графа, розташувавши його вершини по колу в порядку зростання номерів. Одержаний граф, представлений на малюнку 1.2. <В
Малюнок 1.2 - Графічне зображення вихідного графа
Ступені оператора прямого транзитивного замикання для першої вершини:
G 0 (1) = {1};
G 1 (1) = {1, 2, 8, 18};
G 2 (1) = {1, ...
