Генерируем точки случайным образом в заданном квадрате

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

И.В.Дикий

Краснодар 2014

СОДЕРЖАНИЕ

Введение

1. 
   Обзор графов и их свойств
   

   1. Геометрические графы и их применение

Теория графов - раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств. G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

Геометрический граф  -- это совокупность , где   -- непустое множество точек пространства, а  -- множество простых кривых (возможно, направленных), удовлетворяющих следующим условиям:

1) каждая замкнутая кривая множества  содержит только одну точку множества ;

2) каждая незамкнутая кривая множества  содержит ровно две точки множества , которые являются ее граничными точками;

3) кривые множества  не имеют общих точек, за исключением точек из множества .

Элементы множества  называют вершинами графа, а само это множество – носителем графа; элементы множества  называются ребрами графа, а само  -- его сигнатурой.

          Таким образом, геометрический граф есть просто геометрическая конфигурация или структура в пространстве, состоящая из множества точек, взаимосвязанных множеством простых (не имеющих точек самопересечения) кривых.

Хотя многие графы, представляющие реальные объекты, являются геометрическими графами, с точки зрения теории графов их единственная структурная особенность состоит в том, что с каждым геометрическим ребром связаны две (возможно, совпадающие) геометрические вершины. Теория графов построена с учетом именно этой особенности и не учитывает реальной природы вершин и ребер. Таким образом, нумерация вершин и ребер с фиксацией вершин концов каждого ребра и указанием его ориентации (в тех случаях, когда это необходимо) содержит всю информацию, достаточную для описания и геометрического графа, и абстрактного графа. Геометрические графы применяются в области моделирования компьютерных сетей, логистике и других областях…

2. 
   Мини-код
   

3. 
   Радиус графа
   

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

2. Проектирование и постановка задачи

   1. Постановка задачи

В ходе исследования нам необходимо генерировать геометрические графы в квадрате [0, 1]*[0, 1] с различными радиусами R, определять мини-код для каждого сгенерированного графа, и подсчитывать количество появлений одного и того же мини-кода, например, на 10000000 сгенерированных графов (при одном и том же R). Отношение этого количества к 10 миллионам определяет частоту графа (мини-кода). Эта частота заносится в БД как свойство соответствующего графа. Для разных графов частоты будут очень отличаться. Некоторые частоты будут значительно меньше средней частоты, некоторые графы не появятся вообще. Выявление таких графов будет целью нашего исследования.

Объемы генерации графов должны быть очень большими, чтобы получить статистически устойчивые оценки для частот. Например, 6-вершинных графов всего 154, поэтому 10 миллионов генераций в среднем достаточно. Но уже при 9 вершинах имеется более 300 тысяч графов, т.е. в среднем 30 генераций дадут один и тот же граф, а редкие графы могут вообще не появиться. Поэтому в этом случае объем генераций может быть до 1 млрд. Здесь, конечно, место распараллеливанию или CUDA-вычислениям.

2. Проектирование приложения

• 
  Мы уже давно с ним знакомы и его использование не должно вызвать лишних проблем.
  
• 
  Для этого языка реализованы все необходимые для нашей работы библиотеки, поддерживающие работу с динамическими массивами, строками и вывод графических изображений графов в консоль на этапе разработки.
  
• 
  CUDA SDK, который потребуется для параллельных вычислений использует синтаксис схожий с С++.
  

2. Разработанные алгоритмы

Алгоритм выполнения задачи заключается в следующем:

• Генерируем точки случайным образом в заданном квадрате.

• Проверяем расстояние между каждой парой точек. Если оно окажется не больше удвоенного радиуса, то между этими точками строим ребро.

• Строим матрицу смежности для данного графа

• По матрице получаем код графа

• Возвращаемся к шагу 3 и делаем соответствующую перестановку строк и столбцов

• Выполнив всевозможные перестановки и получив коды графов, выбираем минимальный

• Полученный мини-код заносим в таблицу или временное хранилище

• Повторяем шаги с 1 по 7 необходимое число раз

• Делим количество появлений каждого мини-кода на общее количество повторений цикла. Таким образом получаем частоты мини-кодов.

1. Построение представления в программе

Класс Node -- представляет вершину геометрического графа. Он состоит из координат вершины, имени вершины, и списка смежности(вектор указателей на экземпляры этого же класса).

Функция Distance -- возвращает расстояние между двумя вершинами.

Функция CreateVector() -- генерирует случайным образом вершины графа в квадрате [0,1]*[0,1] и возвращать помещать их в вектор и возвращать это вектор как результат.

Процедура CreateGraph(nodes, radius) -- проверяет все вершины вектора nodes и если их радиусы(radius) пересекаются, то в списки смежности этих вершин добавляются указатели друг на друга.

Процедура Generate(nodes, matrix, int, minicode) – является главной в нашей программе она берет граф nodes, пустую матрицу matrix и minicode – хранящую значение мини-кода для того, чтоб сгенерировать всевозможные перестановки вершин и определить мини-код. Процедура рекурсивная и параметры matrix и int введены для реализации рекурсии.

Процедура execute_generate_graph(int count_of_generations, HPEN Pen1, HDC hDC, float radius, int *mass_of_periodicity) -- осуществляется вызов всех вышеперечисленных процедур в цикле столько раз, сколько графов нам необходимо сгенерировать.

Процедура drawGraphic(hDC, Pen1, periodicity) – выводит в консоль график частот графов. Параметр periodicity – это массив, коэффициенты которого – значения мини-кодов, а значения элементов – количество появлений данного мини-кода.

В блоке main() задаются и инициализируются переменные, и вызывается функция execute_generate_graph для генерации графов, а так же функция для построения графика частот.

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

Ниже приведено описание структуры узлов графа на языке C++;

struct coordinates {

float x;

float y;

coordinates() { x = 0, y = 0; };

coordinates(float X, float Y) { x = X, y = Y; };

};
class Node {

public:

vector spis;

int name;

Процедура создания ребер между вершинами (заполнение списков смежностей).

//процедура создает ребра графа с соответствии с радиусом

for (int i = 0; i

for (int j = i + 1; j

if ((Distance(V[i]->getCoord(), V[j]->getCoord())

V[i]->spis.push_back(V[j]);//->name);

V[j]->spis.push_back(V[i]);// ->name);

}

}

2. 
   Результаты исследований
   

Рисунок 4.1 Распределение мини-кодов при радиусе 0.26

Рисунок 4.2 Распределение мини-кодов при радиусе 0.35

Рисунок 4.3 Распределение мини-кодов при радиусе 0.46

Заключение

Так же для графов с 6-ю вершинами были вычислены частоты появлений мини-кодов, и аналогично с 3-х вершинными графами зависимость частоты от радиуса пропорциональна.

Список использованных источников

1. 
   А.С. ГЕЙДА Моделирование при исследовании технических систем: использование некоторых расширений теории графов // Труды СПИИРАН. 2011. Вып. 2(17). ISSN 2078-9181 (печ.),
   
2. 
   Интернет ресурс - http://vuz.exponenta.ru/PDF/L11.html
   
3. 
   Носов В.А. Комбинаторика и теория графов, М.1999