рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Работа сделанна в 1998 году

Практическая реализация курсового проекта - Курсовой Проект, раздел Математика, - 1998 год - Поиск клик в графах Практическая Реализация Курсового Проекта. Задание В Неориентированном Графе ...

Практическая реализация курсового проекта. Задание В неориентированном графе заданном матрицей смежностей выделить клики.

Написать программу выполняющую это действие. Решение Мой алгоритм нахождения клик в графе Пусть задан неориентированный граф 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, l enStolb, Stolbec,RetStolbbyte Kstringklik f1file of byte klikatKlik begin assignFileKlics, klics.ots rewritefileKlics assignf1,matrica.ots resetf1 readf1,size for I1 to size do begin for stolbecsravn1 to size do begin readf1,smezhi, stolbecsravn end end for i1 to size do begin начало пpохода по стpокам KString1i for stolbeci1 to size do begin пеpебиpаем в стpоке все возможные места начала клики If Smezhi, stolbec1 then begin lenStolb1 for StolbecSravnStolbec to size do begin с найденного места пpовеpяем все возможные ваpианты StringSravni Num1 while SmezhKStringnum,StolbecSravn1andnum LenStolb do begin StringSravnKStringnum numnum1 end If num-1LenStolb then begin lenStolblenStolb1 KstringlenStolbStolbecSravn end end конец пpовеpки ваpиантов if lenstolb 2 then begin klika.lenmasslenstolb for i11 to lenstolb do klika. Klikmassi1Kstringi1 writefileKlics, klika end end end конец пеpебоpа возможных мест в стpоке end конец пpохода по стpокам closefileklics end Выше представлена процедура нахождения клик в графе.

Описание переменных StolbecSravn номер сравниваемого столбца.

StringSravn номер текущей строки.

Num, i1,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.

– Конец работы –

Эта тема принадлежит разделу:

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

Теория графов нашла свое применение в решении целого ряда задач. В моем курсовом проекте будет рассмотрен раздел теории графов посвященный… Допустим задан граф GХ,Г. Довольно часто возникает задача поиска таких подмножеств множества вершин Х графа G, которые…

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Практическая реализация курсового проекта

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Теоретическая часть к курсовому проекту
Теоретическая часть к курсовому проекту. Глава1 Теория графов Понятие графа Графом GX,U называется совокупность двух объектов некоторого множества X и отображения этого множества в себя Г. При геом

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги