(граф не містить контурів, і, значить, з кожної його вершини є шлях, що приводить до деякого стоку). Таким чином, перевірка вершини виявляється зайвою. p> Припустимо, нарешті, що до складу перевіряючого тесту входять дві вершини з одного стоку:. Вершини і взаємно досяжні в орграфе, і, отже, наслідки їх перевірок будуть збігатися, так що одну з перевірок можна не проводити. br/>
. Алгоритм побудови мінімального перевіряючого тесту
Спираючись на описану вище теорему, можна запропонувати наступну схему побудови мінімального перевіряючого тесту.
За вихідного графу побудуємо факторграф.
Знайдемо всі стоки даного факторграфа.
Всі можливі мінімальні перевіряючі тести даної системи будуть складатися з перевірок елементів, узятих по одному з кожного стоку.
Розглянемо даний алгоритм, реалізований на об'єктно-орієнтованій мові програмування Java (див. додаток). Алгоритм реалізує вищеописану схему, вхідні параметри - кількість вершин і матриця суміжності графа. У результаті його виконання ми отримуємо всі можливі варіанти мінімального перевіряючого тесту системи, представленої вихідним графом. p> Розглянемо роботу програми, що виконує даний алгоритм. В якості прикладу розглянемо вихідний граф, зображений на рис. 1. <В
Рис. 1
В
Рис. 2
Його факторграф зображений на рис. 2. Стоками даного факторграфа є: і, тому можливі мінімальні перевіряючі тести будуть складатися з перевірок елементів або. p> На вхід програмі подамо кількість вершин вихідного графа і його матрицю суміжності. Вміст input.txt:
1 0 0 1 1
0 0 0 0 0
0 1 1 0 0
0 1 0 1 0
0 0 0 0 1
0 0 0 1 1
У ході свого виконання, програма виведе в файл output.txtвсе можливі варіанти мінімального перевіряючого тесту:
{2, 5}
{2, 6}
Розглянемо інший приклад. Нехай дано граф, зображений на рис. 3. br/>В
Рис. 3
В
Рис. 4
Факторграфом даного графа є граф, зображений на рис. 4. Стоком факторграфа буде вершина. Мінімальним перевіряючим тестом буде полягати в перевірці елемента. p> Вирішимо даний приклад за допомогою програми.
Вхідні дані (файл input.txt):
1 1 0 1 0 0 0
0 1 1 0 0 0 0
1 0 1 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 0 0 1
0 0 1 0 1 1 0
0 0 0 0 0 0 1
0 0 0 0 0 0 1
Після завершення роботи, програма виведе в файлoutput.txt єдиний мінімальний перевіряючий тест - {8}.
Таким чином, програма з вихідній матриці суміжності графа виводить всілякі мінімальні перевіряючі тести системи, представленої цим графом.
Висновок
У даній роботі було розглянуто таке поняття як перевіряючий тест деякої системи, наведено критерій мінімальності такого перевіряючого тесту, а так само був розглянутий і реалізований алгоритм побудови мінімальн...
