Алгоритм генерации случайных графов

Тема в разделе "Свободное общение", создана пользователем UnforgivenII, 7 мар 2007.

Статус темы:
Закрыта.
  1. UnforgivenII

    UnforgivenII Гость

    Привет
    Напишите пожалуйста алгоритм генерации случайных планарных графов на Делфи. Желательно с комментариями.
     
  2. Alliance

    Alliance Гость

    Напомни что такое планарный граф... а то уж несколько лет прошло после изучения =)
     
  3. UnforgivenII

    UnforgivenII Гость

    Планарный граф-это конечное множество вершин, соединенное конечным числом ребер (как-то так). Есть разные способы задание графов, но меня интересует матрица смежности. Она представляет собой массв, симметричный относительно диагонали [i,i], которая заполнена нулями. Проблема в том, что просто задав рандомную симметричную матрицу, граф, который я получаю, может не быть планарным. Планарный граф-это такой граф, вершины которого являются точками плоскости, я ребра-ломанными линиями на этой же плоскости. Точнее, заданный таким способом граф можно представить на плоскости, но в условиях моей задачи ребра не должны пересекаться!
    ЗЫ Задача, которую я разбираю-Проблема четырех красок. (Теорема говорит о том, что любой планарны граф 4-раскрашиваемый). Но из-за того, что у меня граф задается черти как, доходит до такого бреда как 20 цветов, если вершин много, то вообще дохрена... Я, конечно, могу набросать матрицы в txt-файлы и потом открывать их, но для того, чтобы провести исследование 100 графов, например из 30 вершин, слишком долго придумывать правильные матрицы. Именно для этого мне нужен нормальный алгоритм, который будет генерировать планарный граф, ребра которого не будут пересекаться.
     
  4. Alliance

    Alliance Гость

    А в чем смысл задачи? Если только в построении планарного графа, то напиши функцию по проверке графа на планарность.

    Теорема Понкратова-Куратова:
    Граф планарен тогда и только тогда, когда он не содержит частей гомеоморфных графам типа 1 и 2.
    Граф типа 1:
    Посмотреть вложение G1.bmp
    Граф типа 2: полный граф из 5 вершин.


    Что такое гомеоморфеый надеюсь разберешся.
     
  5. Alliance

    Alliance Гость

    После этого все просто:
    1. генерируешь дерево (оно всегда будет планарным)
    2. случайным образом добавляешь ребро и проверяешь граф на планарность
    3. если планарен идем дальше инача удаляем ребро
    4. повторяем пункты 2-3 до определенного условия (например - в графе 20 ребер)
    5. получили планарный граф нужного размера
     
  6. Alliance

    Alliance Гость

    как вариант есть еще одна теорема, но точно не помню... :(
    что типа такого:
    b-цикломатическое число графа
    v-кол-во вершин
    e-кол-во ребер

    b+v-e=const - насколько я помню там стоит двойка :unsure:

    цикломатическое число определяется из обхода графа

    P.S. этот вариант значительно проще но я в нем до конца не уверен... :)
     
  7. UnforgivenII

    UnforgivenII Гость

    Че-нить попробую...


    На счет последнего: ты случайно не про формулу Эйлера? Блин, я чет совсем забыл про то, что она вообще существует...
     
  8. Alliance

    Alliance Гость

    не помню... это было года 2-3 назад
     
  9. Ogion7

    Ogion7 Гость

    Для Alliance: правильно помниш
    взято с http://olddesign.isu.ru/~slava/do/disc/graphs.htm
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей