Реферат: Поиск клик в графах

10 1 1 1

51 0 1 1

61 1 0 1

81 1 1 0

Работа с программой

Программа позволяет найти клики в неориентированном графе размером не более 10 вершин. Граф вводится в ЭВМ матрицей смежностей. Данную матрицу можно взять из вшитого в программу файла. Программа позволяет удобно редактировать заданную матрицу, для выхода из редактирования нажать Esc. Результат работы программы выводится в виде таблицы по количеству вершин клик и номеров самих вершин составляющих клики.

Программа реализована на языке программирования Turbo Pascal 7.0.

Заключение

Программная реализация на ЭВМ поиска максимальных полных подграфов(клик) значительно облегчает работу с графами, как представлением каких либо систем, в смысле исследования этих систем. Мой алгоритм позволяет найти клики в графе любой размерности, но для наглядности я реализовал алгоритм только для графов чья мощность не превышает 10. Так же мой алгоритм за добавлением одного условия будет искать клики и в ориентированном графе. Но моей целью не было создание профессиональной часто используемой программы, а скорее я хотел показать возможность решения данной задачи на ЭВМ.

Список литературы

Ковалева Л.Ф. “Математическая логика и теория графов” МЭСИ 1977

А Кристофидес “Теория графов. Алгоритмический подход”