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

  • Просмотров 2624
  • Скачиваний 421
  • Размер файла 188
    Кб

Кафедра общей теории систем и системного анализа Курсовой проект по курсу: “Общая теория систем” по теме: “Поиск клик в графах” Группа: ДИ 102 Студент: Шеломанов Р.Б. Руководитель: Кацман В.Е. Москва 1998 Содеражание Введение--------------------------------------------------------------------------- 3 Часть 1 Теоретическая часть к курсовому проекту------------------- 3 Глава 1 Теория графов----------------------------------------------------- 3 Глава 2 Максимальные полные

подграфы(клики)---------------------- 8 Часть 2 Практическая реализация курсового проекта--------------- 8 Задание--------------------------------------------------------------------- 8 Решение-------------------------------------------------------------------- 8 Заключение----------------------------------------------------------------------- 12 Список литературы ------------------------------------------------------------ 13 Введение Для иллюстраций условий и решений многих задач люди пользуются графиками. По своей сути графики являются набором из множества точек и

отрезков прямых соединяющих эти точки. Возникает вопрос: подчиняются ли графики каким-либо законам и обладают ли они какими-нибудь свойствами? Этот вопрос был поставлен Д. Кенигом, который впервые объединил все схематические изображения, состоящие из совокупности точек и линий, общим термином “граф” и рассмотрел граф как самостоятельный математический объект. Теория графов нашла свое применение в решении целого ряда задач.

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

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