ГЕНЕРУВАННЯ ТЕСТОВИХ НЕОРIЄНТОВАНИХ ГРАФIВ ФIКСОВАНОГО СТЕПЕНЯ ВЕРШИН

Анотація

Розв'язування задач аналiзу i конструювання графiв приводить до будови нових алгоритмiв i програмної реалiзацiї. Для перевiрки алгоритму потрiбно будувати тестовi данi такого виду, щоб мати наперед заданi значення параметрiв тестiв. Для випадку тестування алгоритмiв на графах такими параметрами є: кiлькiсть вершин графа; степенi вершин; зв'язнiсть графа; допустимiсть кратних ребер i петель; вага ребер. Якщо тестовий граф має вiдомi значення параметрiв, тодi можна обчислювати теоретичнi результати побудованого алгоритму i коректно зiставляти з реально отриманими. Викладено алгоритм i елементи програмної реалiзацiї задачi генерування скiнчених неорiєнтованих графiв, параметрами яких є кiлькiсть вершин n i степенi вершин k = const i якi вiдповiдають додатковим умовам коректностi. Загальна схема алгоритму така. Створюємо два списки вершин L1 i L2. Список L1 початково пустий, в списку L2 всi вершини графа вiд 1 до n. Беремо найпершу за номером вершину в L2, будуємо до неї всi k ребер i переносимо в список L1. Повторюємо описану операцiю для кожної наступної вершини списку L2, крiм останньої. Останню вершину L2 просто переносимо в L1. Алгоритм зразу будує матрицю сумiжностi, моделюючи операцiї зi списками L1 i L2. Вiдповiдно до алгоритму матриця сумiжностi завжди буде однаковою для фiксованих n, k при повторному виконаннi алгоритму. Щоб отримати рiзнi матрицi, використаємо правило iзоморфiзму графа: виконаємо перестановки рядкiв i стовпцiв отриманої матрицi.