ВВЕДЕНИЕ 3
РАЗДЕЛ I ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ И ЕЕ ПРАКТИЧЕСКОЕ ПРИЛОЖЕНИЕ 4
РАЗДЕЛ II РАЗРАБОТКА АЛГОРИТМА НАХОЖДЕНИЯ КЛИКИ 10
РАЗДЕЛ III ПРОВЕДЕНИЕ ЭКСПЕРИМЕНТОВ 12
ЗАКЛЮЧЕНИЕ 17
ИСТОЧНИКИ И ЛИТЕРАТУРА 18
Читать дальше
Таким образом, выполнение поставленных исследовательских задач позволило получить следующие основные результаты исследования:
1. Рассмотрены основные понятия теории графов. Для исключения неоднозначного толкования определено, что такое граф, дуга, ребро, матрица смежности, инцидентности, цикл, клика.
2. Проанализированы существующие алгоритмы нахождения клики в графе. Определены их недостатки. Несмотря на большое распространение задачи нахождения клики до сих пор не разработано единого универсального быстрого алгоритма, определяющего клику в графе. Эта задача остается акуальной.
3. Разработан и программно реализован алгоритм нахождения клики на основе алгоритма Брона-Кербоша. В программе, реализованной на языке Паскаль, используется алгоритм, на первом шаге которого вводится граф в виде матрицы инцидентности, полученный граф отображается, затем по введенному кликовому числу происходит поиск клики, о результатах поиска выводится сообщение.
4. Проведены эксперименты, демонстрирующие работу программы. Выполнен поиск клики для заданного графа.
Перспективы исследования данной проблемы состоят в дальнейшей разработке и совершенствовании существующих методов поиска по временным параметрам.
Читать дальше
Источики:
1. Алгоритм Брона-Кербоша (для нахождения клик) // интернет-источник - http://lmatrix.ru/news/theory/algoritm-brona-kerbosha-dlya-nakhozhdeniya-klik_125.html.
Литература:
2. Paul Erd?s, George Szekeres A combinatorial problem in geometry // Compositio Math. - 1935. - Т. 2. - С. 463 - 470.
3. Luce R. Duncan, Albert D. Perry A method of matrix analysis of group structure // Psychometrika. - 1949. - Т. 2, вып. 14. - С. 95 - 116
Moon, J. W., Leo Moser On cliques in graphs // Israel J. Math. - 1965. - Т. 3. - С. 23 – 28.
4. Ronald Graham, B. Rothschild, Joel Spencer Ramsey Theory. - New York: John Wiley and Sons, 1990.
5. Richard M. Karp Complexity of Computer Computations / R. E. Miller, J. W. Thatcher. - New York: Plenum, 1972. - С. 85 – 103/
Читать дальше