Рефераты по теме Математика

Реферат Поиск клик в графах скачать бесплатно

Скачать реферат бесплатно ↓ [192.64 KB]

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

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


Курсовой проект
по курсу:
“Общая теория систем”

по теме:

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



Группа: ДИ 102
Студент: Шеломанов Р.Б.



Руководитель: Кацман В.Е.




Москва 1998



Содеражание

Введение-------------------------------------------------------------- ------------- 3
Часть 1 Теоретическая часть к курсовому проекту------------------- 3
Глава 1 Теория графов----------------------------------------------------- 3
Глава 2 Максимальные полные подграфы(клики)---------------------- 8
Часть 2  Практическая реализация курсового проекта--------------- 8
Задание--------------------------------------------------------------- ------ 8
Решение--------------------------------------------------------------- ----- 8
Заключение------------------------------------------------------------ ----------- 12
Список литературы ------------------------------------------------------------ 13































Введение

Для иллюстраций условий и решений многих задач люди пользуются графиками. По своей сути графики являются набором из множества точек и отрезков прямых соединяющих эти точки. Возникает вопрос: подчиняются ли графики каким-либо законам и обладают ли они какими-нибудь свойствами?  Этот вопрос был поставлен Д.  Кенигом, который впервые объединил все схематические изображения, состоящие из совокупности точек и линий, общим термином “граф” и рассмотрел граф как самостоятельный математический объект. Теория графов нашла свое применение  в решении целого ряда задач. В моем курсовом проекте будет рассмотрен раздел   теории графов посвященный максимальным полным подграфам, тоесть кликам. Целью проекта является написание программы на языке программирования, которая из заданного графа выделяла бы клику с заданным числом вершин.
Допустим задан граф G=(Х,Г). Довольно часто возникает задача поиска таких подмножеств множества вершин Х графа G, которые обладают определенным, наперед заданным свойством. Например, какова максимально возможная мощность такого подмножества S Í Х, для которого порожденный подграф S является полным? Ответ на этот вопрос дает кликовое число графа G. Это число и связанное с ним подмножество вершин описывает важные струтурные свойства графа и имеет непосредственные приложения при проведение проектного планирования исследовательских работ, в кластерном анализе и численных методах таксономии, паралельных