графы

[Mfcer__]

Каким образом по изветсному количеству вершин и ребер
построить планарный граф?

То есть мне нужно получить матрицу смежности случайно сгенерированного планарного графа...

информации по этому не нашел...

спасибо.

[Alf]

Я бы поступил следующим образом.

1. Зная количество вершин и ребер, определил количество граней плоского графа по формуле Эйлера.
2. Определил среднее количество вершин на одну грань, округлив до целого вниз (предположим, это число n).
3. Построил первую грань графа в виде многоугольника с n вершинами.
4. Добавлял грани по одной к внешней границе графа, каждый раз выбирая количество вершин на очередной грани исходя из формулы Эйлера (это должно быть либо n, либо n+1).

По-моему, должно работать.

[Mfcer__]

v − e + f = 2
где v - число вершин
e - число ребер
f - число граней

на примере

v = 6
e = 7
-> f = 2 + 7 - 6 = 3

а как определить среднее количество вершин на грань?

[Alf]

Пожалуй, предложеннй мной вариант слишком примитивен, чтобы быть верным. Тем более что он не учитывает факт, что вершины и ребра принадлежат более чем одной грани.

Прикинул другой вариант алгоритма. Возьмем предложенный пример, 6 вершин и 7 ребер. Итак, имеем:

Для начала строим треугольник из трех вершин и трех ребер:

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

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

Добавляем еще одну вершину аналогичным образом:

(продолжение следует, ибо в одно сообщение больше четырех картинок не влазит).

[Alf]

(продолжение)

Нам осталось присоединить еще одну вершину. Но, увы, кончился запас ребер. Придется позаимствовать их из числа внутренних ребер, не входящих во внешний контур. Таких ребер как раз два: 1-3 и 3-4. Изымаем их и присоединяем последнюю вершину:

Итак, в общем виде предлагаемый алгоритм таков.

1. Строим первый контур в виде треугольника.
2. Поочередно заменяем каждое ребро внешнего контура графа на дугу, состоящую из новой вершины и двух новых ребер, присоединяя ее к вершинам, которые соединены с данным ребром (надеюсь, смысл понятен, несмотря на витиеватость?). При этом дуга заменяет ребро во внешнем контуре графа.
3. Если для присоединения очередной вершины не хватает пары ребер, заимствуем их из числа ребер, не входящих во внешний контур. При этом следим, чтобы не возникало вершин со степенью меньше 2, т.е. забираем те ребра, которые соединяют вершины со степенью не менее 3.
4. Если вершины закончились, а ребра еще остались, то соединяем "лишними" ребрами вершины на внешнем контуре. Если допустимы криволинейные дуги, то можно соединять соседние вершины, если нет - то через одну. Разумеется, после каждого добавления не забываем корректировать внешний контур, чтобы гарантированно избежать самопересечений.

Умозрительно кажется, что должно работать. Если кто увидел дыру в алгоритме, давайте обсуждать.

[Mfcer__]

А что значит
"Разумеется, после каждого добавления не забываем корректировать внешний контур, чтобы гарантированно избежать самопересечений."
?

как коректировать?

[Alf]

Ну вот, например, сначала у нас был треугольник с вершинами 1, 2, 3 и ребрами 1-2, 2-3 и 1-3. Это и был внешний контур нашего графа.

Потом добавляем вершину 4. Для этого выбрали пару вершин на внешнем контуре, в нашем примере 1 и 3. Соединяем их ребрами с вершиной 4. После этого корректируем внешний контур. Убираем из него ребро 1-3 (оно теперь стало внутренним) и добавляем ребра 1-4 и 4-3. Итак, внешний контур был таким: 1-2-3-1, стал 1-2-3-4-1.

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

Потом, если остались "лишние" ребра, берем пару вершин через одну на внешнем контуре и соединяем их ребром. В нашем примере, скажем, выберем вершины 2 и 6, соединяем их ребром и корректируем внешний контур: убираем вершину 3 (она теперь становится внутренней) и примыкающие к ней ребра 2-3 и 3-6, добавляем ребро 2-6. То есть получаем внешний контур 1-2-6-5-4-1. Опять же, поскольку каждый раз мы добавляем ребро снаружи, это гарантирует нам, что оно не пересекается с другими ребрами. Опять же граф остается плоским.

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

[Alf]

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

Итак, пускай у нас n вершин и m ребер. Поскольку в нашем графе не должно быть вершин степени меньше 2, очевидно, что m >= n.

Начинаем построение с того, что располагаем n вершин по кольцу и соединяем их n ребрами. Эта конструкция и образует наш начальный внешний контур.

Если m = n, то задача решена. Если нет, начинаем распределять оставшиеся m-n ребер.

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

1. Выбираем какую-либо вершину k на внешнем контуре.
2. Соединяем ребром вершины k-1 и k+1.
3. Выбрасываем вершину k из внешнего контура.
4. Повторяем шаги 1-3 до тех пор, пока не закончатся "лишние" ребра.

По-моему, этот алгоритм должен приводит к тому же результату, что и предложенный ранее, но быстрее и не требует перераспределения ранее задействованных ребер.

Господа графоманы, кто видит изъяны в таком алгоритме?

[Mfcer__]

Спасибо, действительно просто, однако вопрос

3. Выбрасываем вершину k из внешнего контура.

что значит выбрасываем?
вообще?
или просто ее в дальнейшем не будем принимать при расчете?

[Mfcer__]

попробовал по этому алгоритму построить граф
взял 7 вершин
соединил по алгоритму ребрами получилось
7 вершин
11 ребер
5 faces

v - e + f = 2

7 - 11 + 5 =1

должно быть 2....

если взять ребер больше 11, то останется треугольник, где уже все соединено..

[Alf]

...
v - e + f = 2

7 - 11 + 5 =1

должно быть 2....

На самом деле для общности плоский граф проецируется на сферу, и добавляется еще одна грань - внешняя по отношению к графу. Можешь проверить на примере треугольника, где v = 3, e = 3, тогда

f = 2 + e - v = 2

Первая грань - внутренняя область треугольника, вторая - внешняя. На плоскости кажется нелепо, а нарисуй треугольник на поверхности сферы - все становится на свои места, и отпадает такая неприятная вещь, как бесконечность.

если взять ребер больше 11, то останется треугольник, где уже все соединено..

В принципе, если допустимы криволинейные дуги (а обычно они допустимы), то можно проводить несколько дуг между парой точек. Но тогда граф становится неинтересным - лепи себе дуги к одной паре точек и все. Лучше кратные оставить напоследок, когда ничего больше не остается.

[Alf]

Спасибо, действительно просто, однако вопрос

3. Выбрасываем вершину k из внешнего контура.

что значит выбрасываем?
вообще?
или просто ее в дальнейшем не будем принимать при расчете?

На графе вершина остается, конечно. Просто нужно вести упорядоченный список вершин, лежащих на внешнем контуре. После того как ты провел ребро от вершины k-1 к вершине k+1, у тебя вершина k изолируется от внешней области, и новые ребра к ней присоединять уже нельзя (иначе возможны пересечения с уже имеющимися ребрами, и граф перестанет быть плоским). Чтобы не заниматься тягомотной проверкой на пересечения, я просто выбрасываю эту вершину из списка доступных для присоединения новых ребер (такие вершины всегда лежат на внешнем контуре, это гарантирует, что есть свободное место для очередного ребра, т.к. за пределами внешнего контура в принципе нет ребер, и пересечься просто не с чем).

[Mfcer__]

спасибо все работает