ові спостережень приходимо до висновку, що для відшукання клік в неорієнтованому графі потрібно виділити в вихідній матриці смежностей підматриці зазначеного вище виду, безлічі вершин утворюють ці матриці і будуть вершинами кліки. Але за визначенням кліки нам підійдуть не всі такі множини, а лише оригінальні що не містять в собі інших множин вершин. Так що друге завдання буде зводиться до виділення з отриманих множин оригінальних, що не містять в собі інших підмножині. Те що вихідна матриця смежностей симетрична щодо головної діагоналі дозволять нам здійснювати пошук підматриць тільки в її верхньому або нижньому трикутнику. br/>
Крок 1. p> Йдемо по матриці як показано на малюнку 3.2 а і шукаємо першу-ліпшу одиничку (рис 3.2 б) запам'ятовуємо її координати (R, C).
В
Крок 2.
Шукаємо наступну 1 за адресою (R, C1)
Крок 3.
Починаємо спускатися по стовпці (С1) у пошуках 1, причому шукаємо її за адресою (С, С1), так як у вихідній матриці стовпці попарно суміжних вершин не обов'язково сусідять. Запам'ятовуємо рядок кожної знайденої таким чином 1 для пошуку в наступних стовпцях. Збільшуємо довжину безлічі вершин на 1.
Кількість повторень кроку 3 одно поточному розміру безлічі вершин.
Якщо за вказаною адресою ми не зустрічаємо 1 то значить даний стовпець не утворює підматрицю смежностей кліки - пропускаємо його. Починаємо Крок 2. p> Якщо розмір безлічі вершин утворюють кліку більше 2 то запам'ятовуємо це безліч.
Так до кінця рядка.
Повторюємо Крок 1 для всіх 1 в рядку.
Таким чином проходимо всю матрицю. На виході отримуємо кілька множин вершин, відбираємо серед них тільки оригінальні, не містять в собі інших підмножин. p> Відібрані підмножини і є кліки заданого графа.
Програмна реалізація
В
procedure MakeKliks;
var StolbecSravn, StringSravn, Num, size, i1, i, lenStolb,
Stolbec, RetStolb: byte;
Kstring: klik;
f1: file of byte;
klika: tKlik;
begin
assign (FileKlics, 'klics.ots');
rewrite (fileKlics);
assign (f1, 'matrica.ots');
reset (f1);
read (f1, size);
for I: = 1 to size do
begin
for stolbecsravn: = 1 to size do
begin
read (f1, smezh [i, stolbecsravn]);
end;
end;
for i: = 1 to size do
begin {початок пpохода по стpоку}
KString [1]: = i;
for stolbec: = i +1 to size do
begin {пеpебіpаем в стpоке всі можливі місця початку кліки}
If Smezh [i, stolbec] = 1 then
begin
lenStolb: = 1;
for StolbecSravn: = Stolbec to size do
begin {з знайденого місця пpовеpяем всі можливі ваpиант}
StringSravn: = i;
Num: = 1;
while (Smezh [KString [num], StolbecSravn] = 1) and (num <= LenStolb) do
