Реферат: Поиск клик в графах

⚡ 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Курсовой проект студента Шеломанова Р.Б.

Кафедра общей теории систем и системного анализа

Московский государственный университет экономики, статистики и информатики

Для иллюстраций условий и решений многих задач люди пользуются графиками. По своей сути графики являются набором из множества точек и отрезков прямых соединяющих эти точки. Возникает вопрос: подчиняются ли графики каким-либо законам и обладают ли они какими-нибудь свойствами? Этот вопрос был поставлен Д. Кенигом, который впервые объединил все схематические изображения, состоящие из совокупности точек и линий, общим термином “граф” и рассмотрел граф как самостоятельный математический объект. Теория графов нашла свое применение в решении целого ряда задач. В моем курсовом проекте будет рассмотрен раздел теории графов посвященный максимальным полным подграфам, тоесть кликам. Целью проекта является написание программы на языке программирования, которая из заданного графа выделяла бы клику с заданным числом вершин.
Допустим задан граф G=(Х,Г). Довольно часто возникает задача поиска таких подмножеств множества вершин Х графа G, которые обладают определенным, наперед заданным свойством. Например, какова максимально возможная мощность такого подмножества S Í Х, для которого порожденный подграф S является полным? Ответ на этот вопрос дает кликовое число графа G. Это число и связанное с ним подмножество вершин описывает важные струтурные свойства графа и имеет непосредственные приложения при проведение проектного планирования исследовательских работ, в кластерном анализе и численных методах таксономии, паралельных вычмслениях на ЭВМ, при размещении предприятий обслуживания, а также источников и потребителей в энергосистемах.
Часть 1. Теоретическая часть к курсовому проекту
Графом G(X,U)
называется совокупность двух объектов некоторого множества X
и отображения этого множества в себя Г
.
При геометрическом представлении графа элементы множества Х
изображаются точками плоскости и называются вершинами графа. Линии, соединяющие любые пары точек x
и y
, из которых у
является отображением х
, называются дугами графа. Дуги графа имеют направление, обозначаемое стрелкой, которая направлена острием от элемента х
к его отображению у
.
Две вершины А
и В
являются граничными вершинами дуги, если А
- начало дуги, а В
ее конец.
Смежными называются различные дуги, имеющие общую граничную точку. Две вершины х
и у
смежны, если они различны и существует дуга, идущая от одной из них к другой .
Вершина называется изолированной, если она не соединена дугами с другими вершинами графа.
Если дуга U
исходит из вершины х
или заходит в х
, то дуга U
называется инцидентной вершине х
, а вершины х
инцидентной дуге U
. Общее число дуг, инцидентной вершине х
, являются степенью вершины х Р(х)
. Вершины, степень которых Р(х)>2
, называются узлом, а со степенью Р(х)<2
- антиузлом.
Полустепень захода Р +
(х)
вершины х
- количество дуг, заходящих в данную вершину. Полустепень исхода Р -
(х)
- количество дуг, исходящих из данной вершины.
Путь - последовательность дуг ( U 1
, U 2
, ...U n

), в которой конец каждой предыдущей дуги совпадает с началом последующей. Путь может быть конечным и бесконечным.
Путь называется простым, если в нем никакая дуга не встречается дважды, и составным, если любая из дуг встречается более одного раза.
Путь, в котором ни одна из вершин не встречается более одного раза, называется элементарным путем.
Гамильтонов путь - путь проходящий через все вершины, но только по одному разу,
Эллеров путь - путь содержащий все дуги графа, при этом только по одному разу.
Длинна пути - число дуг последовательности ( U 1
, U 2
, ...U n

).
Ветвь - путь, в котором начальная и конечная вершины являются узлами. Дуга (x,y)
называется замыкающей, если удаление ее не приводит к аннулированию пути из x
в y.

Контур - конечный путь, начинающийся и заканчивающийся в одной и той же вершине. Контур единичной длинны называется петлей.
Ориентированный граф - граф, у которого вершины соединяются направляющими стрелками.
Графы можно рассматривать с учетом или без учета ориентации его дуг.
Нуль-граф - граф (X,U)
, состоящий только из изолированных вершин.
Однородный граф - если степени всех вершин графа одинаковы и P +
(x)=P -
(x) =0.
Симметрический граф - граф, в котором две любые смежные вершины соединены только двумя противоположно ориентированными дугами.
Антисимметрический - граф, в котором каждая пара смежных вершин соединена только в одном направлении.
Полный - граф, в котором любая пара вершин соединена одинаковым числом дуг.
Мультиграф - граф, в котором хотя бы две смежные вершины соединены более чем одной дугой. Наибольшее число дуг, соединяющих смежные вершины графа называется кратностью.
Подграфом графа G(X,U)
называется граф G(A,U A
)
, определяемый следующим образом:
1. Вершинами A
подграфа G(A,U A
)
является некоторое подмножество вершин графа G(X,U);

2. Отображением каждой вершины подграфа является пересечение отображения той же вершины в графе G(X,U)
со всем подмножеством вершин A подграфа G(A,U A
).

Частичным графом для графа G(X,U)
называется граф G(X,U)
, в котором содержатся все вершины и некоторое подмножество дуг исходного графа.
Частичный подграф - это частичный граф от подграфа.
Фактором графа G(X,U)
называется частичный граф G(X,U)
, в котором каждая вершина обладает полустепенями исхода и захода, равными единице, имеются одна заходящая и одна исходящая дуги.
Базисным графом называется ориентированный частичный граф, образованный из исходного удалением петель и замыкающих дуг.
В общем случае граф может быть представлен несколькими отдельными графами, не имеющими общих дуг. Тогда граф G(X,U)
называется несвязным, а каждый из составляющих его графов G 1
, G 2
,...G n
- компонентами связности. Граф называется связным, когда каждую его вершину можно соединить с любой другой его вершиной некоторой цепью.
G 3
(X 3
,Гх 3
) = G 1
(X 1
,Г1х 1
)
È G 2
(X 2
,Г2х 2
)
, где X 3
=X 1

È
X 2
, а Гx 3
=Г1x 1

È
Г2x 2


G 3
(X 3
,Гх 3
) = G 1
(X 1
,Г1х 1
)
Ç G 2
(X 2
,Г2х 2
)
, где X 3
=X 1

Ç
X 2
, а Гx
3
=Г1x 1

Ç
Г2x 2


4. Прямое (декартово) произведение графов.
Прямым произведением множеств Х{x 1
.......x n
} и Y называется множество Z, элементами которого являются всевозможные пары вида x i
, y j
, где x i
ÎX, y j
ÎY. Обозначают: Z=X
x Y.

G 3
(X 3
,Гх 3
) = G 1
(X 1
,Г1х 1
)
Ç G 2
(X 2
,Г2х 2
)
, где X 3
=X1
Ç
X2, а Гx 3
=Г1х1
Ç
Г2х2

G 1
(X,Гх)=G 1
(X 1
,Гх 1
) G 2
(Y,Гy)= G 2
(X 2
,Гх 2
)

Z=X
x Y={x
1
y 1
, x 1
y 2
, x 2
y 1
, x 2
y 2
, x 3
y 1
, x 3
y 2
}

Расширение графа - это превращение, линии, соединяющей любые две вершины графа в элементарный путь введением новых промежуточных вершин на этой линии.
Сжатие графа - это превращение элементарного пути, соединяющего две любые вершины графа, в линию.
Если граф содержит вершины Х 1
и Y 1
, то операцией стягивания называется исключение всех дуг между вершинами Х 1
и Y 1
и превращение всех вершин в одну общую вершину Х.
Пусть существует мультиграф с b вершинами, p ребрами, и R компонентами связности, тогда цикломатическое число мультиграфа определяется равенством:
Матрицей смежности графа G(X,Гх)
, содержащего n
вершин называется квадратная бинарная матрица А(G) n
x n
, c нулями на диагонали. Число единиц в строке равно степени соответствующей вершины.
Матрицей инциденций ориентированного графа G(X,U)
называется прямоугольная матрица порядка [m
x n] n
- мощность множества Х,
m
- мощность множества U.
Каждый элемент которой определяется следующим образом:
a ij
= -1, если х i

- конец дуги U j


0, если х i

- не инцидентна дуге U j


Построим матрицы смежности (М1) и инциденций (М2) для графа G(X,U) (рис 2.1).
Дополнительная матрица графа G(X,U)
представляет собой квадратную матрицу А 1
, которая получается из матрицы смежности этого графа путем замены всех нулей единицами и наоборот.
Деревом называется неориентированный связный граф с числом вершин не менее двух, не содержащий петель и циклов. Вершины, инцидентные только одной дуге дерева, называются висячими.
Корень прадерева - вершина у которой Р +
(х)=0
.
Глава 2. Максимальные полные подграфы (клики)

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

В неориентированном графе заданном матрицей смежностей выделить клики. Написать программу выполняющую это действие.
Мой алгоритм нахождения клик в графе
Пусть задан неориентированный граф G1 матрицей смежностей M1 (рис 3.1)
1) Что матрица М1 симметрична относительно главной диагонали, так как вершины неориентированного графа попарно смежны.
2) Если выделить клику из данного графа и представить ее в виде матрицы смежностей то получим матрицу вида:
01111 Тоесть тоже симметричную относительно главной диагонали и в верхнем
10111 и нижнем треугольниках ее будут находится 1 а на главной диагонали 0,
11011 так получается потому, что все вершины попарно смежны (см опред.
На основе наблюдений приходим к выводу, что для отыскания клик в неориентированном графе нужно выделить в исходной матрице смежностей подматрицы указанного выше вида, множества вершин образующие эти матрицы и будут вершинами клики. Но по определению клики нам подойдут не все такие множества, а лишь оригинальные не содержащих в себе других множеств вершин. Так что вторая задача будет сводится к выделению из полученных множеств оригинальных, не содержащих в себе других подмножестве. То что исходная матрица смежностей симметрична относительно главной диагонали позволят нам осуществлять поиск подматриц только в ее верхнем или нижнем треугольнике.
Идем по матрице как показано на рисунке 3.2 а и ищем первую попавшуюся единичку (рис 3.2 б) запоминаем ее координаты (R,C) .
Начинаем спускаться по столбцу (С1) в поисках 1 , причем ищем ее по адресу (С,С1), так как в исходной матрице столбцы попарно смежных вершин не обязательно соседствуют. Запоминаем строку каждой найденной таким образом 1 для поиска в следующих столбцах. Увеличиваем длину множества вершин на 1.
Количество повторений шага 3 равно текущему размеру множества вершин.
Если по указанному адресу мы не встречаем 1 то значит данный столбец не образует подматрицу смежностей клики - пропускаем его. Начинаем Шаг 2.
Если размер множества вершин образующих клику больше 2 то запоминаем это множество.
Повторяем Шаг 1 для всех 1 в строке.
Таким образом проходим всю матрицу. На выходе получаем несколько множеств вершин, отбираем среди них только оригинальные, не содержащие в себе других подмножеств.
Отобранные подмножества и есть клики заданного графа.
var StolbecSravn,StringSravn,Num,size,i1,i,lenStolb,
begin {пеpебиpаем в стpоке все возможные места начала клики}
for StolbecSravn:=Stolbec to size do
begin {с найденного места пpовеpяем все возможные ваpианты}
while (Smezh[KString[num],StolbecSravn]=1)and(num<=LenStolb) do
end; {конец пеpебоpа возможных мест в стpоке}
Выше представлена процедура нахождения клик в графе.
StolbecSravn: номер сравниваемого столбца.
lenStolb: размер множества вершин клики.
Stolbec: номер столбца первой единицы в текущем цикле сравнения.
Kstring: вектор хранящий координаты строк для сравнения. По выходе из цикла сравнения этот массив представляет собой множество вершин найденной клики.
Найденные клики сохраняются в файле 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.
Программа позволяет найти клики в неориентированном графе размером не более 10 вершин. Граф вводится в ЭВМ матрицей смежностей. Данную матрицу можно взять из вшитого в программу файла. Программа позволяет удобно редактировать заданную матрицу, для выхода из редактирования нажать Esc. Результат работы программы выводится в виде таблицы по количеству вершин клик и номеров самих вершин составляющих клики.
Программа реализована на языке программирования Turbo Pascal 7.0.
Программная реализация на ЭВМ поиска максимальных полных подграфов(клик) значительно облегчает работу с графами, как представлением каких либо систем, в смысле исследования этих систем. Мой алгоритм позволяет найти клики в графе любой размерности, но для наглядности я реализовал алгоритм только для графов чья мощность не превышает 10. Так же мой алгоритм за добавлением одного условия будет искать клики и в ориентированном графе. Но моей целью не было создание профессиональной часто используемой программы, а скорее я хотел показать возможность решения данной задачи на ЭВМ.
Ковалева Л.Ф. “Математическая логика и теория графов” МЭСИ 1977
А Кристофидес “Теория графов. Алгоритмический подход”

Название: Поиск клик в графах
Раздел: Рефераты по математике
Тип: реферат
Добавлен 06:07:07 23 марта 2008 Похожие работы
Просмотров: 747
Комментариев: 20
Оценило: 3 человек
Средний балл: 4.7
Оценка: неизвестно   Скачать

Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Если Вам нужна помощь с учебными работами, ну или будет нужна в будущем (курсовая, дипломная, отчет по практике, контрольная, РГР, решение задач, онлайн-помощь на экзамене или "любая другая" учебная работа...) - обращайтесь: https://clck.ru/P8YFs - (просто скопируйте этот адрес и вставьте в браузер) Сделаем все качественно и в самые короткие сроки + бесплатные доработки до самой сдачи/защиты! Предоставим все необходимые гарантии.
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Реферат: Поиск клик в графах
Курсовая работа: Проблемы социальной политики Российского государства
Реферат: Суккуленты
Курсовая работа по теме Субъекты права: понятие и классификация
Ндс С Курсовой Разницы У Продавца
Школьные Сочинения На Любую Тему
Сколько Слов Для Итогового Сочинения Егэ
Реферат: Юридична професія в зарубіжних країнах
Мое Отношение К Распаду Ссср Эссе
Реферат Болезни Старения Долгожители
Эссе На Тему Наш Дар Бесценный Речь
Сочинение по теме Историософия Б. Пильняка
Курсовая работа: Аудіювання на середньому етапі навчання
Реферат по теме Анализ и методика обучения броска через спину с колен
Реферат по теме Труднощі періоду адаптації п'ятикласників до нових умов навчання
Реферат На Тему Ссср В Период Перестройки (1985-1991 Гг.)
Курсовая работа по теме Архивное делопроизводство в Индии и России
Ответ на вопрос по теме Шпоры-сочинения (Шпаргалка)
Реферат: Кустанайский областной комитет КП Казахстана
Реферат по теме Лечебная физкультура при пиелонефрите
Дипломная работа по теме Развитие товарооборота на предприятии торговли и оценка эффективности его хозяйственной деятельности
Реферат: Перспективные технологии в энергетике
Реферат: Контрольное задание по социологии
Реферат: Виргиния