На цій сторінці ви знайдете готові приклади з теорії графів (розділу дискретної математики). Теорія графів бере свій початок ще в 18 столітті, коли Ейлер написав свою знамениту статтю про Кёнігсберскіх мостах (див. Рішення на алгоритм Ейлера). Зараз досягнення теорії графів застосовуються в будівництві, програмуванні, електротехніці, соціології, економіці, біохімії, телекомунікації та плануванні транспортних комунікацій, психології і т.д.
Які види завдань вирішуються студентами?
Завдання, які вирішуються в рамках теорії графів, можна умовно поділити на кілька груп:
- Визначення графа і його властивості. Завдання на побудову графа по заданому числу вершин і ребер, побудова матриці суміжності і інцидентності, обчислення основних характеристик графа (зв'язність, простота, ейлерову, повнота, дводольні, регулярність графа і т.п.). Перевірка планарності і изоморфности графів.
- Дії з графами. Додавання і видалення вершин і ребер, компонент зв'язності, злиття вершин, об'єднання, перетин, з'єднання і декартовій твір графів. Побудова доповнення графа.
- Маршрути, ланцюги і цикли, контури. Ейлерова ланцюг і гамільтонів цикл і перевірка графа на виконання цих властивостей.
- Обчислення характеристик графа. Відстані: діаметр графа, центр графа, радіус графа. Обчислення цикломатическая і хроматичного числа.
- Завдання на графах. Задача про найкоротший шлях (алгоритм Дейкстри, Беллмана, побудова дерева шляхів). Завдання на побудову мінімального остовного дерева (алгоритм Краскала). Завдання про максимальний потік в мережі (алгоритм Форда-Фолкерсона). Завдання про розфарбовування графа.
- Вивчення дерев (спеціальних видів графів без циклів). Дерева застосовуються в шифруванні, програмуванні та багатьох інших прикладних областях.
Завдання по графам з рішенням онлайн
Завдання 1. Побудувати граф відносини "x + y ≤7" на безлічі М =. Визначте його властивості.
Завдання 2. Знайти найкоротші шляхи в орграфе від першої вершини до всіх інших, використовуючи алгоритм Дейкстри. Побудуйте дерево найкоротших шляхів.
Завдання 3. Знайти максимальний потік і мінімальний розріз в транспортній мережі, використовуючи алгоритм Форда-Фалкерсона (алгоритм розстановки позначок) Побудувати граф збільшень. Перевірити виконання умови максимальності побудованого повного потоку. Джерело - вершина 1, стік - вершина 8.
Завдання 4. Побудувати кістяк мінімальної ваги, використовуючи алгоритми Прима та Краскала. За допомогою матриці Кірхгоффа знайдіть кількість (неізоморфних) остовних дерев, використовуючи пакети комп'ютерної математики (наприклад, MathCAD, Mathematica, MatLab).
Завдання 5. Потрібно скласти структурну матрицю для даного орграфа (або графа) і, методами булевої алгебри, знайти всі шляхи $ P_ $ з вершини $ i $ в вершину $ j $, потім знайти всі перетину $ S_ $ між цими вершинами. В даному завданні (щоб виключити можливі неясності графічного малюнка) вказуються всі орієнтовані ребра, причому запис (2-4) означає, що 2 вершина пов'язана з 4-й, а зворотного зв'язку немає. Нагадаємо, що для знаходження шляхів з вершини $ i $ в вершину $ j $ потрібно розкривати мінор структурної матриці $ М_ $ (викреслювати з структурної матриці рядок з номером $ j $ і стовпець з номером $ i $). Перетину же знаходяться запереченням шляхів (сполучення змінюється на диз'юнкцію і навпаки).
Завдання 6. Для графа $ G = (X, U) $ виконати наступне:
1.1. побудувати:
- матрицю суміжності,
- матрицю інцидентності.
1.2. Визначити ступеня для всіх вершин $$ даного графа.
Завдання 7. Знайти всі найкоротші шляхи в орграфе, використовуючи алгоритм Флойда.
Завдання 8. Задано $ G (X, ГX) $
$ X = $,
ГХ:
Гx1 =, Гx2 =, Гx3 =, Гx4 =, Гx5 =.
Визначити хроматичної і цикломатичне число даного графа.
Завдання 9. Вважаючи даний граф неорієнтованим, позначити його вершини і ребра різними символами і визначити.
3.1. Локальні ступеня і оточення кожної вершини у вигляді структури суміжності;
3.2. Побудувати матриці інцидентності і суміжності;
3.3. Розглянути частини графа. Привести приклади суграфом, що накриває суграфом. Показати підграф, що складається з трьох вершин. Скільки таких подграфов можна знайти в даному графі? Показати приклади перетину і об'єднання частин графа;
3.4. Привести приклади циклічного маршруту, ланцюги, простий ланцюга. Спробувати знайти Ейлеров цикл;
3.5. Визначити центр, діаметр та радіус графа.
Вважаючи граф орієнтованим, визначити
3.6. ступені вершин
3.7. Матриці інцидентності і суміжності.
3.8. Привести приклади шляху, орієнтованої ланцюга, простий ланцюга, контуру, циклу і простого циклу.
Рішення теорії графів на замовлення
Виконуємо рішення задач, контрольних і практичних робіт по будь-яким розділах теорії графів. Детальний оформлення, таблиці, креслення, пояснення, можливо написання програм на мовах програмування (для алгоритмів на графах) або використання спеціальних програм. Рішення економічних задач, пов'язаних з теорією графів.
Вартість прикладу від 100 рублів. оформлення проводиться в Word, термін від 2 днів. Також надаємо допомогу в складанні тестів по графам.
Замовити розв'язання задач з теорії графів легко