Алгоритм построения простого графа

Question

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

Answer 1

Это слишком долго для комментария. Извините, предоставляя ответ.

Ваш вопрос мне неясен. Является ли график плоским, зависит от самого графика, а не от того, как он нарисован. "В теории графов плоский граф - это граф, который может быть встроен в плоскость, т. Е. Его можно нарисовать на плоскости таким образом, чтобы его ребра пересекались только в своих конечных точках". с http://en.wikipedia.org/wiki/Planar_graph).

Нужно ли работать / проверять, является ли график плоским?

Вы должны нарисовать это в плоской форме?

В приведенном вами примере почему второй рисунок почему-то более правильный, чем первый рисунок? Только потому, что у них нет пересекающихся ребер?

Предполагая, что вам нужно сделать это с другими графиками, какое правило используется для определения, является ли какое-то представление лучше, чем другое, как ваша диаграмма обобщается на другие графики?

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

Answer 2

Существует теорема Эйлера, которая применима к любому плоскому графу.

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

Теорема Эйлера: V-E+F=2, где:

1. - V - количество вершин,
2. - E - количество ребер,
3. - F - количество граней

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

Например, поскольку у нас есть теорема Эйлера, которая применяется к каждому плоскому графу, вам нужно найти способ применить эту теорему к существующему непланарному графу, а затем проверить ее.

Шаги: (возможно, для некоторых из них потребуются координаты)

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