Федеральное агентство по образованию
ГОУ ВПО "ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ"
Кафедра «Автоматизированные системы обработки информации и управления»
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОМУ ПРОЕКТУ
по дисциплине «Дискретная математика»
ДВУМЕРНАЯ КЛАСТЕРИЗАЦИЯ ПО ПРЕДЕЛЬНОМУ РАССТОЯНИЮ
Омск – XXX
Реферат
Отчёт 14с., 1ч., 12рис., 0табл., 3источника, 0прил.
ГРАФ, КЛАСТЕР, МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО.
Предметом курсового проекта является кластеризация.
Цель работы – разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера.
В ходе работы был разработан алгоритм кластеризации.
В результате работы было написан алгоритм, решающий данные задачи.
Введение
Часто бывает полезно и наглядно изображать некоторую ситуацию в виде рисунка, состоящего из точек (вершин) и линий (рёбер), соединяющих некоторые вершины. Такие изображения получили названия графа.
Теория графов получила широкое применение на практике. Она применяется в гражданском строительстве, электротехнике, социологии и экономике и в других областях.
Одной из задач теории графов является кластеризация и построение минимального остовного дерева. Эти задачи часто возникают на практике: при группировке результатов поиска, проектировании компьютерных систем, соединении городов, составлении электрических цепей.
Целью данной работы является разработка алгоритма, выполняющего данные задачи.
Отчет содержит четыре раздела:
- постановка задачи курсового проектирования – это раздел, в котором описывается задача курсового проекта;
- схемы алгоритмов – это раздел, в котором описывается алгоритм и его схема;
- теоретический анализ – теория, необходимая для выполнения поставленной задачи;
- результаты тестирования – это раздел, в котором описываются результаты тестирований на правильность работы разработанного алгоритма.
1 Постановка задачи курсового проектирования
Реализовать алгоритм кластеризации заданного набора точек по предельному расстоянию d. После кластеризации граф каждого кластера редуцировать до минимального остовного дерева.
2 Теоретический анализ
Граф G - это математический объект, состоящий из множества вершин X = {x1, x2,..., xn} и множества ребер A = {a1, a2,..., ak}.
Связный граф — такой граф, в котором между любой парой вершин существует по крайней мере один путь.
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некоторое значение (вес ребра).
Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно вес — вещественное число и его можно интерпретировать как «длину» ребра.
Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).
Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. ............