Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: 6312
Последний выпуск: 19.06.2015

Процедурная генерация графов

398
22 июля 2014 года
KIV
432 / / 20.01.2009
Мне нужно сделать процедурную генерацию графов. То есть есть функция, которой на вход подаётся номер графа, а на выходе получается список координат точек и список дорог, их соединяющих (точнее процедура будет вызывать по мере необходимости две подпрограммы - add_point и add_way, первая из которых принимает две координаты, а вторая номера точек). Чем больше номер графа, тем больше в нём будет точек и рёбер (ну эту зависимость не сложно придумать, тут я могу сам справиться). При этом пересечений должно быть поменьше, а циклов побольше. Как такое можно сделать?
445
22 июля 2014 года
Meander
487 / / 04.09.2011
Могу посоветовать литературу:
-----------------------------------------------------------------
Судоплатов С.В. Элементы дискретной математики. 2002
Элементы теории графов стр. 108
Маршруты. Достижимость. Связность стр. 119
Обходы графов стр. 131
Планарные графы стр. 154
-----------------------------------------------------------------
Уилсон Р. Введение в теорию графов. 1977
-----------------------------------------------------------------
Оре О. Теория графов. 1980
-----------------------------------------------------------------
Основной вывод таков:
Чем больше ребер будет при каждой вершине, тем больше там будет циклов. Число ребер должно превосходить число вершин.
Что касается пересечений, то тут больше сложностей. Граф без пересечений (на плоскости) или планарный граф можно нарисовать так, что ребра будут пересекаться. Придется перемещать вершины, чтобы убрать пересечения. Но предложенных книг достаточно, чтобы синтезировать требуемый алгоритм.

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

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог