Предыдущая страница реферата | 1  2  3  4  5  6  7  8

Берем первую строку, находим первую единичку по адресу (1,2).

Запоминаем адрес первой 1 (1,2). Ищем следующую 1 в первой строке. Она находится по адресу (1,5). Проверяем адрес (2,5) на 1. Там ее нет. Пропускаем 5-й столбец. Находим следующую 1 в 6 столбце. Проверяем адрес (2,6) на 1. Там ее нет. так до конца строки. Убеждаемся что в данном цикле сравнений матрица смежностей получаемой клики имеет размерность два. Что означает наличие в клике двух вершин - простейшее сочетание - оно не рассматривается в моей программе. Мы записываем в файл клик клики не меньше третьего порядка.

Выбираем в первой строке следующую 1. Она находится по адресу (1,5) запоминаем этот адрес в массиве строк. Ищем следующую  1 в первой строке. Она находится по адресу (1,6). Спускаемся по 6 столбцу, проверяем адрес (5,6) на 1. Она там есть. Количество найденных 1 в 6 столбце =размеру массива содержащего множества. Тогда увеличиваем длину этого массива на 1 и записываем туда 6. Получаем в массиве [1,5,6]. И т.д.

 В итоге получим клики с номерами вершин: 1 5 6 8; 6 4 8; 1 7 8.

Матрица смежностей клики 1568.

  1 5 6 8

10 1 1 1

51 0 1 1

61 1 0 1

81 1 1 0

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

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

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

Заключение

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

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

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

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

Скачали данный реферат: Молчанов, Щербаков, Ivankov, Jagodich, Jalovegin, Averin.
Последние просмотренные рефераты на тему: шпори на пятках, собрание сочинений, картинки реферат, сообщение об открытии счетов.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8

Поделитесь этой записью или добавьте в закладки