Курсовая: Поиск клик в графах - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

Поиск клик в графах

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 221 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

13 Кафедра общей теории систем и системного анализа Курсовой проект по курсу : “Общая теория систем” по теме : “Поиск клик в графах” Группа : ДИ 102 Студент : Шеломанов Р.Б. Руководитель : Кацман В.Е. Москва 1998 Содеражание Введение 3 Часть 1 Теоретическая часть к курсовому проекту 3 Глава 1 Теория графов 3 Глава 2 Максимальные полные подграфы (клики ) 8 Часть 2 Практическая реализация курсового проекта 8 Задание 8 Решение 8 Заключение 12 Список литератур ы 13 Введение Для иллюстраций условий и решений многих задач люди пользуются графиками . По своей сути графики являются набором из множества точек и отрезков прямых соединяющих эти точки . Возникает вопрос : подчиняются ли гра фики каким-либо законам и обладают ли они какими-нибудь свойствами ? Этот вопрос был поставлен Д . Кенигом , который впервые объединил все схематические изображения , состоящие из совокупности точек и линий , общим термином “граф” и рассмотрел граф как самос т оятельный математический объект . Теория графов нашла свое применение в решении целого ряда задач . В моем курсовом проекте будет рассмотрен раздел теории графов посвященный максимальным полным подграфам , тоесть кликам . Целью проекта является написание п р ограммы на языке программирования , которая из заданного графа выделяла бы клику с заданным числом вершин. Допустим задан граф G=(Х,Г ). Довольно часто возникает задача поиска таких подмножеств множества вершин Х графа G, которые обладают определенным , напер ед заданным свойством . Например , какова максимально возможная мощность такого подмножества S Х , для которого порожденный подграф S является полным ? Ответ на этот вопрос дает кликовое число графа G. Это число и связанное с ни м подмножество вершин описывает важные струтурные свойства графа и имеет непосредственные приложения при проведение проектного планирования исследовательских работ , в кластерном анализе и численных методах таксономии , паралельных вычмслениях на ЭВМ , при р а змещении предприятий обслуживания , а также источников и потребителей в энергосистемах . Часть 1 Теоретическая часть к курсовому проекту Глава 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 - компонентами связности . Граф называется связным , когда каждую его вершину можно соединить с любой другой его вершиной неко торой цепью. Операции над графами 1. Объединение графов 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 Пример (Рис 1.1). Рис 1.1 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 Пример (рис 1.2). Рис 1.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 Пример . (рис 2.3) G 1 (X,Гх )=G 1 (X 1 ,Гх 1 ) G 2 (Y,Г y)= G 2 (X 2 ,Гх 2 ) X= x 1 x 2 x 3 Y= y 1 y 2 Гх 1 =0 Гу 1 = y 1 y 1 Гх 2 = x 1 x 3 Гу 2 = y 1 Гх 3 =0 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 Z= z 1 z 2 z 3 z 4 z 5 z 6 Рис 2.3 7. Расширение графа. Расширение графа - это превращение , линии , соединяющей любые две вершины графа в элементарный путь введением новых промежуточных вершин на этой линии. 8. Сжатие графа. Сжатие графа - это превращение элементарного пути , соединяющего две любые вершины графа , в линию . 9. Стягивание графа. Если граф содержит вершины Х 1 и Y 1 , то операцией стягивания называется исключение всех дуг между вершинами Х 1 и Y 1 и превращение всех вершин в одну об щую вершину Х. Некоторые числа теории графов Пусть существует мультиграф с b вершинами , p ребрами , и R компонентами связности , тогда цикломатическое число мультиграфа определяется равенством : V = p - b + R Матрицы для графов Матрицей смежности графа G(X,Гх ) , содержащего n вершин называется квадратная бинарная матрица А (G) n x n , c нулями на диагонали . Число единиц в строке равно степени соответствующей вершины . Матрицей инциденций ориентированного графа G(X,U) называется прямоугольная матрица порядка [m x n] n - мощность множества Х, m - мощность множества U. Каждый элемент которой определяется следующим образом : 1, если х i - начало дуги U j a ij = -1, если х i - конец дуги U j 0, если х i - не инцидентна дуге U j Пример. Построим матрицы смежности (М 1) и инциденций (М 2) для графа G(X,U) (рис 2.1). Рис 2.1 Дополнительная матрица графа G(X,U) представляет собой квадратную матрицу А 1 , которая получается из матрицы смежности этог о графа путем замены всех нулей единицами и наоборот. Деревья и прадеревья Деревом называется неориентированный связный граф с числом вершин не менее двух , не содержащий петель и циклов . Вершины , инцидентные только одной дуге дерева , называются висячими. Прадрево - ориентированное дерево. Корень прадерева - вершина у которой Р + (х )=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. Если размер множества вершин образующих клику больше 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 ; Выше представлена процедура нахождения клик в графе. Описание переменных : StolbecSravn: номер сравниваемого столбца . StringSravn: номер текущей строки. Num , i 1, 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. 1 5 6 8 10 1 1 1 51 0 1 1 61 1 0 1 81 1 1 0 Работа с программой Программа позволяет найти клики в неориентированном графе размером не более 10 вершин . Граф вводится в ЭВМ матрицей смежностей . Данную матрицу можно взять из вшитого в программу файла . Программа позволяет удобно реда ктировать заданную матрицу , для выхода из редактирования нажать Esc. Результат работы программы выводится в виде таблицы по количеству вершин клик и номеров самих вершин составляющих клики. Программа реализована на языке программирования Turbo Pascal 7.0. Заключение Программная реализация на ЭВМ поиска максимальных полных подграфов (клик ) значительно облегчает работу с графами , как представлением каких либо систем , в смысле исследования этих систем . Мой алгоритм позволяет найти клики в графе любой разме рности , но для наглядности я реализовал алгоритм только для графов чья мощность не превышает 10. Так же мой алгоритм за добавлением одного условия будет искать клики и в ориентированном графе . Но моей целью не было создание профессиональной часто использ у емой программы , а скорее я хотел показать возможность решения данной задачи на ЭВМ. Список литературы Ковалева Л.Ф . “Математическая логика и теория графов” МЭСИ 1977 А Кристофидес “Теория графов . Алгоритмический подход”
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
В ухрюпинском супермаркете поставили урны для сортировки мусора: пластик, стекло, бумага. Перед закрытием пришли уборщицы и сложили всё в один мешок.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, курсовая по математике "Поиск клик в графах", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru