Реферат: Поиск клик в графах
klika.lenmass:=lenstolb;
for i1:=1 to lenstolb do
klika.Klikmass[i1]:=Kstring[i1];
write(fileKlics,klika);
end;
end;
end; {конец пеpебоpа возможных мест в стpоке}
end; {конец пpохода по стpокам}
close(fileklics);
end;
Выше представлена процедура нахождения клик в графе.
Описание переменных:
StolbecSravn: номер сравниваемого столбца.
StringSravn: номер текущей строки.
Num ,i1,i: счетчики.
lenStolb: размер множества вершин клики.
Stolbec: номер столбца первой единицы в текущем цикле сравнения.
size: размер матрицы смежностей.
Kstring: вектор хранящий координаты строк для сравнения. По выходе из цикла сравнения этот массив представляет собой множество вершин найденной клики.
Smezh: Матрица смежностей;
Найденные клики сохраняются в файле klics.ots. Потом из него удаляются все клики несоответствующие вышеприведенным условиям. На выходе получаем файл клик задаваемого графа.
Пример
Задаем граф G1 его матрицей смежности М1.
Берем первую строку, находим первую единичку по адресу (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.