Поиск клик в графах — страница 5

  • Просмотров 2646
  • Скачиваний 422
  • Размер файла 188
    Кб

1 а на главной диагонали 0, 11011 так получается потому, что все вершины попарно смежны (см опред. 11101 клики. На основе наблюдений приходим к выводу, что для отыскания клик в неориентированном графе нужно выделить в исходной матрице смежностей подматрицы указанного выше вида, множества вершин образующие эти матрицы и будут вершинами клики. Но по определению клики нам подойдут не все такие множества, а лишь оригинальные не содержащих

в себе других множеств вершин. Так что вторая задача будет сводится к выделению из полученных множеств оригинальных, не содержащих в себе других подмножестве. То что исходная матрица смежностей симметрична относительно главной диагонали позволят нам осуществлять поиск подматриц только в ее верхнем или нижнем треугольнике. Шаг 1. Идем по матрице как показано на рисунке 3.2 а и ищем первую попавшуюся единичку (рис 3.2 б) запоминаем

ее координаты (R,C) . Шаг 2. Ищем следующую 1 по адресу (R,C1) Шаг 3. Начинаем спускаться по столбцу (С1) в поисках 1 , причем ищем ее по адресу (С,С1), так как в исходной матрице столбцы попарно смежных вершин не обязательно соседствуют. Запоминаем строку каждой найденной таким образом 1 для поиска в следующих столбцах. Увеличиваем длину множества вершин на 1. Количество повторений шага 3 равно текущему размеру множества вершин. Если по

указанному адресу мы не встречаем 1 то значит данный столбец не образует подматрицу смежностей клики - пропускаем его. Начинаем Шаг 2. Если размер множества вершин образующих клику больше 2 то запоминаем это множество. Так до конца строки. Повторяем Шаг 1 для всех 1 в строке. Таким образом проходим всю матрицу. На выходе получаем несколько множеств вершин, отбираем среди них только оригинальные, не содержащие в себе других

подмножеств. Отобранные подмножества и есть клики заданного графа. Программная реализация 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 begin StringSravn:=KString[num]; num:=num+1; end; If num-1=LenStolb then begin lenStolb:=lenStolb+1; Kstring[lenStolb]:=StolbecSravn; end; end; {конец пpовеpки ваpиантов} if lenstolb>2 then begin 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; Выше представлена процедура нахождения