Минимальный проверяющий тест
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?ков в.
Пусть в состав проверяющего теста входит проверка некоторой вершины орграфа , не входящей ни в один сток факторграфа . В случае отказа соответствующего элемента исходом проверки будет 1. Но тогда значение 1 дает и проверка любого представителя того стока в , который достижим из (граф не содержит контуров, и, значит, из каждой его вершины имеется путь, приводящий к некоторому стоку). Таким образом, проверка вершины оказывается излишней.
Предположим, наконец, что в состав проверяющего теста входят две вершины из одного стока: . Вершины и взаимно достижимы в орграфе , и, следовательно, исходы их проверок будут совпадать, так что одну из проверок можно не проводить.
. Алгоритм построения минимального проверяющего теста
Опираясь на описанную выше теорему, можно предложить следующую схему построения минимального проверяющего теста.
По исходному графу построим факторграф .
Найдем все стоки данного факторграфа .
Все возможные минимальные проверяющие тесты данной системы будут состоять из проверок элементов, взятых по одному из каждого стока.
Рассмотрим данный алгоритм, реализованный на объектно-ориентированном языке программирования Java (см. приложение). Алгоритм реализует вышеописанную схему, входные параметры - количество вершин и матрица смежности графа. В результате его выполнения мы получаем все возможные варианты минимального проверяющего теста системы, представленной исходным графом.
Рассмотрим работу программы, выполняющую данный алгоритм. В качестве примера рассмотрим исходный граф, изображенный на рис. 1.
Рис. 1
Рис. 2
Его факторграф изображен на рис. 2. Стоками данного факторграфа являются: и , поэтому возможные минимальные проверяющие тесты будут состоять из проверок элементов или .
На вход программе подадим количество вершин исходного графа и его матрицу смежности. Содержимое 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.
Рис. 3
Рис. 4
Факторграфом данного графа является граф, изображенный на рис. 4. Стоком факторграфа будет вершина . Минимальным проверяющим тестом будет состоять в проверке элемента .
Решим данный пример с помощью программы.
Входные данные (файл 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}.
Таким образом, программа по исходной матрице смежности графа выводит всевозможные минимальные проверяющие тесты системы, представленной этим графом.
Заключение
В данной работе было рассмотрено такое понятие как проверяющий тест некоторой системы, приведен критерий минимальности такого проверяющего теста, а так же был рассмотрен и реализован алгоритм построения минимального проверяющего теста.
граф тест проверяющий теорема алгоритм
Список используемых источников
1. Богомолов А.М., Салий В.Н. Алгебраические основы дискретных систем. - М.: Наука. Физматлит, 1997. - 368 с.
. Абросимов М.Б., Долгов А.А. Практические задания по графам, 2-е издание: Учеб.пособие. - Саратов: Изд-во Научная книга, 2009. - 76 с.
Приложение
Класс ru.sgu.csit.tokbik.coursework.Matrix
ans=newArrayList();static void main(String[] args) {
Scanner scanner = null;
Map();
,List();f;{= new Scanner(new File("input.txt"));= scanner.nextInt();[][] adjacencyMatrix = new int[topCount][topCount];(inti = 0; i<topCount; i++) {(int j = 0; j <topCount; j++) {[i][j] = scanner.nextInt();
}
());(intj=0;j());(int j = 0; j <topCount; j++) {(reachabilityMatrix[i][j] == 1) {.get(i + 1).add(j + 1);
}
}
}(inti = 0; i<componentsReachability.size(); i++) {
f = false;
key=componentsReachability.get(i+1);(List list : reachabilityBySCC.keySet()) {(list.equals(key)) {
f = true;;
}
}(f) {.get(key).add(i + 1);
} else {
List();.add(i + 1);.put(key, list);
}
,List entry : reachabilityBySCC.entrySet()) {(entry.getKey().equals(entry.getValue())) {.add(entry.getKey());
}
}= new PrintWriter(new File("output.txt"));
pw.println("Начальная матрица смежности :");
Matrix.printMatrix(adjacencyMatrix, topCount, pw);.println("Матрицадостижимости :");.printMatrix(reachabilityMatrix, topCount, pw);(stocks.size() == 1 &&stocks.get(0).size() == 1) {
pw.println("Минимальный проверяющий тест : ");
} else {.println("Возможные вариа