Графоаналізатор - візуальне середовище для роботи з графами. Графоаналізатор не тільки надає можливість створювати і обробляти графи, але візуально відображати результати роботи алгоритмів. Середовище підтримує роботу з орієнтованими і простими графами, навантаженими і ненавантаженими. Програма реалізує безліч алгоритмів для обробки графів. починаючи від пошуку шляху і закінчуючи перевіркою на планарність. Графоаналізато р - це н езаменімий помічник для вирішення завдань за допомогою графів.
Візуалізація графів і алгоритмів.
Процес створення і зміни графа інтуїтивно зрозумілий. Візуальне уявлення графа є дуже зрозумілою формою ін едставленія графа. також можна побачити результат роботи алгоритму у візуальній формі. Візуальне уявлення можна зберегти у файлі зображення. Для більшої наочності ви можете додавати підписи до елементів граф, змінювати фон, налаштовувати зовнішній вигляд елементів графа.
інтерфейс програми
Головна форма програми представлена нижче:
1 - головне меню програми;
2 - робоча область;
3 - вікно матриці суміжності;
4 - поле виведення результату ра боти;
5 - кнопки швидкого доступу.
Малюнок 3.1 - Головне вікно програми
Опис інших діалогових вікон знаходиться у відповідних розділах.
решта функцій
типові завдання
Програму Графоаналізатор 1.2 можна використовувати для вирішення безлічі завдань, які можна звести до математичної моделі графів. Нижче наведено список типових завдань:
Приклад вирішення завдань: Пошук мінімального шляху проїзду, Пошук мінімальних витрат при наймі співробітників, Пошук мінімальних витрат на прокладку проводки або комп'ютерної мережі.
Рішення всіх заду ч зводиться до пої ську мінімального маршруту в навантаженому графі.
Пошук мінімального шляху проїзду
Нам необхідно проїхати від будинку до магазину, причому шлях повинен бути мінімальний. Припустимо, ми маємо карту вулиць.
Рисунок 3.2 - Карта міста
Для початку завантажуємо карту вулиць як задній фон для робочої області.
Малюнок 3.3 - Завантажений задній фон
Потім встановлюємо масштаб (скільки метрів в 10 пікселях карти)
Малюнок 3.4 - Завдання масштабу
Потім креслимо граф на основі карти.
Малюнок 3.5 - Граф на основі карти
А тепер знаходимо найкоротший шлях. використовуючи один з методів (Форда-Беллмана, Дейкстри або Флойда). Після пошуку найкоротшого шляху ми побачимо оптимальний шлях.
Малюнок 3.6 - Граф з знайденим мінімальним шляхом
Як ми бачимо, найкоротший шлях дорівнює 460.
Пошук мінімальних витрат на прокладку проводки або комп'ютерної мережі
Завдання вирішується подібно до тієї, що була розглянута вище, тільки необхідно використовувати кар ту всіх віз мужніх методів прокладки мережі.
Пошук мінімальних витрат при наймі співробітників
Завдання про наймання співробітник ів зводиться до н ахожденію мінімального шляху.
З 8 до 10 - 200 рублів.
З 14 до 18 - 500 рублів
З 19 до 20 - 50 рублів
Як видно з діаграми, альтернатив н Айма кілька, хоча їх кількість не велика, але це тільки приклад, в реальному житті може бути все складніше.
Тепер на основі цих даних будуємо граф. Вершинами графа будуть тимчасові мітки через до аждий годину, а дугами, варіанти оплати різних працівників.
Малюнок 3.7 - Граф на основі графіка роботи
Тепер, знайшовши найкоротший шлях з першої вершини в останню, ми визначимо мінімальні витрати і метод найму.
Малюнок 3.8 - Знайдений мінімальний маршрут
В результаті правильним рішенням буде наступне, виділене зеленим кольором:
Приклад вирішення завдань: Розподіл роботи між декількома працівниками; Розрахунок пропускної здатності комп'ютерної або дорожньої мережі
Рішення обох завдань зводиться до знаходження максимального потоку. Тільки завдання про розподіл роботи між декількома працівниками необхідно звести до неї.
Розрахунок пропускної здатності комп'ютерної або дорожньої мережі
Припустимо, у нас є ділянка мережі доріг, представлений на малюнку нижче.
Малюнок 3.9 - Карта доріг
Нам необхідно прорахувати пропускну здатність сет і доріг в од ном з напрямків. Наприклад, зліва на право. Ми будуємо орієнтований граф, і задаємо ваги дуг рівні пропускної способн ості. Всі праві і ліві дороги з'єднуємо з витоком і стоком. В результаті отримаємо граф:
Малюнок 3.10 - Граф на основі карти доріг
Залишилося тільки прорахувати пропускну здатність. В результаті отримуємо такий розподіл потоку.
Малюнок 3.11 - Максимальна пропускна здатність доріг
Розподіл роботи між декількома працівниками
Розподіл робіт між працівниками теж зводиться до пошуку пропускної здатності. Нехай ми маємо список працівників:
робити урокі.Как ми бачимо, різні види робіт можуть виконувати різні працівники, і за умовою одна робота може виконуватися одним працівником.
Нам необхідно розподілити працівників так, що б максимальна кількість робіт виконувалося. Зробити це вручну трудомістке завдання, якщо число працівників велике.
Для вирішення представимо нашу задачу у вигляді графа. Лівий стовпчик вершин графа - це працівники, правий - це типи робіт. Також ми додали стік і джерело.
Тепер з'єднаємо кожного працівника з тим типом робіт, який він може виконувати. Вага дуги граф а рівні 1.
Малюнок 3.12 - Граф на основі працівників і видів робіт
Після з'єднуємо витік з усіма працівниками, а стік з'єднуємо з видами робіт. Вага так само дорівнює 1.
Малюнок 3.13 - Граф на основі працівників і видів робіт
Тепер шукаємо пропускну здатність.
Малюнок 3.14 - Спосіб розподілу працівників
Пропускна здатність нам показала, який працівник повинен виконувати яку роботу. Наприклад, Петров повинен витрачати гроші, Дядя Петя повинен копати.
Приклад вирішення завдань: Пошук найдешевшого варіанту прокладки проводки. Пошук найдешевшого варіанту з'єднання доріг.
При будівництві доріг або в разі прокладання кабелю може існувати кілька шляхів сполучення міста або комп'ютера, але необхідно це зробити одним певним способо м. Причому, бажано, щоб обраний спосіб був найбільш економічним з точки зору часових або грошових затрат.
Нехай ми маємо кілька міст і віз можне спосіб з'єднання їх.
Нам необхідно з'єднати всі міста і затратити н а це на іменьшіе кількість грошей. Перетворимо нашу карту в граф.
Малюнок 3.15 - Карта міст
Малюнок 3.16 - Мінімальна вартість споруди доріг
В результаті ми витратимо всього 73 умовні одиниці.
Приклад вирішення завдань: Перевірка можливості з оедіненія електронних елементів на платі
При з'єднанні елементів на електронно й платі, необхідно щоб з'єднання не перетиналися. Для цього еклектичну ланцюг необхідно представити у вигляді графа. Якщо граф є планарним, то можна з'єднати всі елементи ланцюга без перетинів.
Приклад вирішення завдань: Пошук методу розмальовки карти мінімальним числом фарби
Якщо існує карта, на якій знаходяться країни, і необхідно знайти такий метод розфарб скі щоб дві сусідні стр ани мали різні кольори.
Нехай є карта:
Малюнок 3.17 - Карта країн
Для подання карти в вигляді графа, країни будуть вершинами графа, а кордони ду гами. Тоді граф буде виглядати так:
Малюнок 3.18 - Граф на основі карти країн
Після шукаємо хроматичної число графа. і отримуємо такий результат:
Малюнок 3.19 - Спосіб розмальовки графа
Приклад вирішення завдань: Рішення завдання комівояжера
Припустимо, у фірми або кур'єра, або комівояжера є клієнти, і необхідно відвідати всіх клієнтів тільки один раз.
Уявімо наших клієнтів у вигляді графа.
Малюнок 3.20 - Карта розташування клієнтів
Для пошуку необхідного шляху, вибираємо алгоритм пошуку гамільтонових ланцюга.
Малюнок 3.21 - Маршрут обходу клієнтів
Перша операція, яку необхідно виконай ть - пов про задати граф, з яким ви будете працювати. Про АГАЛЬНІ етапи завдання графа:
створення графа
Для створення графа спочатку необхідно вибрати його тип. На малюнку 4.1 приведена форма створення графа.
Малюнок 4.1 - Форма створення графа
Якщо встановити галочку «Орграф», тоді граф буде орієнтованим. Якщо встановити галочку «навантажуючи ний граф», граф буде навантаженим.
Для того, що б створити граф необхідно викликати меню «Створити».
Малюнок 4.2 - Меню програми «Граф»
збереження графа
Для збереження графа з метою його подальшого використання необхідно вибрати пункт меню «Фа йл» - «Зберегти граф».
Малюнок 4.3 - Зображення меню «Файл»
В результаті, в файлі буде збережений граф, його тип, позиція вершин, позиції і значення написів. Також в меню зберігаються послідовність файли графа, з якими ви працювали.
Збереження візуального представлення
Для збереження візуального представлення графа, необхідно вибрати пункт меню «Граф» - «Зберегти зображення». В результаті в файлі буде збережено, то що ви ведіть в робочій області.
Завантаження графа
Для відновлення роботи з раніше збереженим графом необхідно завантажити граф, використовуючи меню «Файл» - «Завантажити граф».
Малюнок 4.4 - Зображення меню «Файл»
Все дан ні про графа, які раніше були використані, будуть втрачені.
Додавання вершини
Додавання вершини можна пр оізвесті декількома методами:
І спользовать гарячу клавішу «F3».
Кнопку на панелі.
І спользовать пункт з меню Граф.
Варто відзначити, що вершина буде додана в випадкову позицію робочої області. Якщо у вигляді нумерації вершин обрана нумерація, що задається користувачем, то також буде необхідно ввести назву вершини.
Додавання дуги
Додавання дуги можна зробити декількома методами:
І спользоват ь пункт меню з меню «Граф». Після необхідно ввести номер вершини, з якої буде йти дуга і в яку. Також можна використовув ати гарячу клавішу «F4».
В
Редагувати матрицю суміжності, введенням значення в відповідну клітку.
Додавання тексту
Д ля створення пояснювальних написів існує можливість додавання тексту. Для додавання тексту необхідно вибрати відповідний пункт з меню «Граф» або натиснути кнопку на панелі швидкого доступу. Після цього необхідно вибрати місце для розташування написи, а потім ввести текст напису.
видалення об'єкта
Д ля видалення об'єктів (вершин графа, дуг або написів) необхідно їх виділити, клікнувши на них правою кнопкою мишки, а потім вибрати пункт з меню «Граф» або натиснути кнопку на панелі.
переміщення об'єктів
Для переміщення об'єктів (вершин графа, дуг або написів) необхідно натиснути на об'єкт лівої кнопк ой мишки, і не відпускаючи її, зробити п еремещеніе миші.
перейменування об'єктів
Для перейменування вершин, зміни ваги дуг і перейменування написів, необхідно вибрати потрібний елемент. Зайти в пункт меню Змінити і вибрати один з пунктів:
- для редагування назва вершини, в режимі назв, що задаються користувачем.
- для редагування ваги дуг, для навантажених графів.
- для зміни тексту напису.
Редагування матриці суміжності
Редагування матриці суміжно сти можна здійснити 2 різними методами.
Перший метод полягає в використанні панелі матр учениці суміжності для редагування ваг дуг.
Малюнок 4.5 - Вікно редагування матриці суміжності
При редагуванні неорграфа друге значення буде додано автоматично. При введенні некоректних значень, буде виведено повідомлення.
В
Режими обробки миші
Режим обробки миші визначає обробку правого кліка мишки. Існує 2 режиму обробки мишки: