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

Кафедра общей теории систем и системного анализа Курсовой проект по курсу Общая теория систем по теме Поиск клик в графах Группа ДИ 102 Студент Шеломанов Р.Б. Руководитель Кацман В.Е. Москва 1998 Содеражание Введение 3 Часть 1 Теоретическая часть к курсовому проекту 3 Глава 1 Теория графов 3 Глава 2 Максимальные полные подграфыклики 8 Часть 2 Практическая реализация курсового проекта 8 Задание 8 Решение 8 Заключение 12 Список литературы 13 Введение Для иллюстраций условий и решений многих задач люди пользуются графиками. По своей сути графики являются набором из множества точек и отрезков прямых соединяющих эти точки. Возникает вопрос подчиняются ли графики каким-либо законам и обладают ли они какими-нибудь свойствами Этот вопрос был поставлен Д. Кенигом, который впервые объединил все схематические изображения, состоящие из совокупности точек и линий, общим термином граф и рассмотрел граф как самостоятельный математический объект.

Теория графов нашла свое применение в решении целого ряда задач.

В моем курсовом проекте будет рассмотрен раздел теории графов посвященный максимальным полным подграфам, тоесть кликам. Целью проекта является написание программы на языке программирования, которая из заданного графа выделяла бы клику с заданным числом вершин.

Допустим задан граф GХ,Г. Довольно часто возникает задача поиска таких подмножеств множества вершин Х графа G, которые обладают определенным, наперед заданным свойством. Например, какова максимально возможная мощность такого подмножества S Х, для которого порожденный подграф S является полным Ответ на этот вопрос дает кликовое число графа G. Это число и связанное с ним подмножество вершин описывает важные струтурные свойства графа и имеет непосредственные приложения при проведение проектного планирования исследовательских работ, в кластерном анализе и численных методах таксономии, паралельных вычмслениях на ЭВМ, при размещении предприятий обслуживания, а также источников и потребителей в энергосистемах. Часть 1

Теоретическая часть к курсовому проекту

Путь может быть конечным и бесконечным. Расширение графа. Расширение графа - это превращение, линии, соединяющ... Сжатие графа. 9. Деревья и прадеревья Деревом называется неориентированный связный граф...

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

Практическая реализация курсового проекта. Решение Мой алгоритм нахождения клик в графе Пусть задан неориентирова... Повторяем Шаг 1 для всех 1 в строке. size размер матрицы смежностей. Результат работы программы выводится в виде таблицы по количеству верш...

Заключение

Заключение Программная реализация на ЭВМ поиска максимальных полных подграфовклик значительно облегчает работу с графами, как представлением каких либо систем, в смысле исследования этих систем.

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

Список литературы

Список литературы Ковалева Л.Ф. Математическая логика и теория графов МЭСИ 1977 А Кристофидес Теория графов.

Алгоритмический подход.