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

Прадрево - ориентированное дерево.

Корень прадерева - вершина у которой Р+(х)=0.

Глава 2. Максимальные полные подграфы (клики)

Максимальный полный подграф (клика) графа G есть порожденный подграф, построенный на подмножестве S вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа G, построенный на множестве вершин H, содержащих S, не является полным. Следовательно, в клике все вершины попарно смежны. Возможно также определить кликовое число графа (известное также как густота или плотность) - это максимальное число вершин в кликах данного графа.

Часть 2. Практическая реализация курсового проекта

Задание

В неориентированном графе заданном матрицей смежностей выделить клики. Написать программу выполняющую это действие.

Решение

Мой алгоритм нахождения клик в графе

Пусть задан неориентированный граф  G1 матрицей смежностей M1 (рис 3.1)

Рис 3.1

Замечаем следующее:

1) Что матрица М1 симметрична относительно главной диагонали, так как вершины неориентированного графа попарно смежны.

2) Если выделить клику из данного графа и представить ее в виде матрицы смежностей то получим матрицу вида:

01111  Тоесть тоже симметричную относительно главной диагонали и в верхнем 

10111   и нижнем треугольниках ее будут находится 1 а на главной диагонали 0,            

11011  так   получается  потому,  что   все  вершины  попарно смежны (см опред.

11101   клики.

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

Шаг 1.

Идем по матрице как показано на рисунке 3.2 а и ищем первую попавшуюся единичку (рис 3.2 б) запоминаем ее координаты (R,C) .

Шаг 2.

Ищем следующую 1 по адресу (R,C1)

Шаг 3.

Начинаем спускаться по столбцу (С1) в поисках 1 , причем ищем ее по адресу (С,С1), так как в исходной матрице столбцы попарно смежных вершин не обязательно соседствуют. Запоминаем строку каждой найденной таким образом 1 для поиска в следующих столбцах. Увеличиваем длину множества вершин на 1.

Количество повторений шага  3 равно текущему размеру множества вершин.

Рекомендуем скачать другие рефераты по теме: рассказы, древняя греция реферат.



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

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