допомогою хвильового алгоритму можна розрахувати основні метричні характеристики графа - діаметр і радіус.
Відстань від даної вершини a до найбільш віддаленої від неї вершини називається ексцентриситетом вершини a і позначається через ecc (a). p align="justify"> Величина найменшого ексцентриситету називається радіусом графа і позначається через rad (G), а величина найбільшого - діаметром і позначається diam (G).
Найменший діаметр має повний граф - його діаметр дорівнює 1. Серед зв'язкових графів з n вершинами найбільший діаметр, рівний n-1, має ланцюг P n .
Разметив граф хвильовим алгоритмом почергово від кожної вершини, можна визначити її ексцентриситет, а з безлічі всіх ексцентриситетів графа встановити його радіус і діаметр.
.2 Огляд аналогів
В якості аналогів були обрані візуалізатори з дискретної математики, представлені на сайті кафедри комп'ютерних техгологію СПбДУ ІТМО. p align="justify"> До недоліків ресурсу можна віднести:
В· відсутність якої б то не було документації;
В· незручний інтерфейс.
До плюсів:
В· охоплення широкого спектру алгоритмів в області дискретної математики і комбінаторики.
2. Сценарій роботи користувача
.1 Прецеденти використання
При розробці діаграми прецедентів розглядалися наступні актори:
В· студент, головний актор, його мета - знаходження найкоротшого шляху в заданому графі та визначення його метричних характеристик; для реалізації цих завдань він взаємодіє з апплетом;
В· аплет, другорядний актор; мета аплету - отримати відповідь користувача і відправити його на перевірку на сервер;
Далі слід визначити можливі сценарії взаємодії акторів з системою і між собою (див. малюнок 1)
Як видно зі схеми, головна роль відводиться студенту - аплет ж реагує на його дії: отрісовиваєт інтерфейс, виробляє розмальовку графа, а по закінченні роботи відправляє відповідь на сервер.
В
Рисунок 1 - Діаграма прецедентів використання
2.2 Сценарій роботи користувача
1. Отрісовка графа, описаного в завданні матрицею суміжності:
1.1. Установка кількості вершин.
1.2. Вказівка ​​вершин початку і кінця шляху.
2. Пошук мі...
