Рефотека.ру / Математика

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

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

Курсовой проект студента Шеломанова Р.Б.

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

Московский государственный университет экономики, статистики и информатики

Москва 1998

Введение

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

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

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

Глава1. Теория графов

Понятие графа

Графом G(X,U)  называется совокупность двух объектов некоторого множества X и отображения этого множества в себя Г.

При геометрическом представлении графа элементы множества Х изображаются точками плоскости и называются вершинами графа. Линии, соединяющие любые пары точек x и y, из которых у является отображением х, называются дугами графа. Дуги графа имеют направление, обозначаемое стрелкой, которая направлена острием от элемента х к его отображению у.

Вершины и линии графа

Две вершины А и В являются граничными вершинами дуги, если А- начало  дуги, а В ее конец.

Смежными называются различные дуги, имеющие общую граничную точку. Две вершины х и у смежны, если они различны и существует дуга, идущая от одной из них к другой . 

Вершина называется изолированной, если она не соединена дугами с другими вершинами графа.

Если дуга U исходит из вершины х или заходит в х, то дуга U называется инцидентной вершине х, а вершины х инцидентной дуге U. Общее число дуг, инцидентной вершине х, являются  степенью вершины х Р(х). Вершины, степень которых Р(х)>2, называются узлом, а со степенью Р(х)

Похожие работы:

  1. • Поиск клик в графах
  2. • Поиск клик в графах
  3. •  ... нахождения всех полных подграфов (клик) данного графа
  4. • Модификация алгоритма определения клик графа с параметрической ...
  5. • Поиск в ширину на графах
  6. • Поиск оптимального пути в графе
  7. • Психология политических клик
  8. • Алгоритмы сортировки, поиска кратчайшего пути в графе ...
  9. • Методы решения задач
  10. • Алгоритмы на графах. Независимые и доминирующие ...
  11. • Алгоритм раскраски графа (точный)
  12. • Алгоритмы сортировки, поиска длиннейшего пути во ...
  13. • Алгоритмы на графах. Кратчайшие расстояния на графах
  14. • Разработка программ с использованием динамической ...
  15. • Эйлеровы и гамильтоновы графы
  16. • Определение связности графа на Лиспе
  17. • Графы и их представление на ЭВМ
  18. • Динамическое программирование, алгоритмы на графах
  19. • 1С : Торговля + склад
Смотреть все похожие работы
Рефотека ру refoteka@gmail.com