распределение узлов графа в ведра - PullRequest
Новая
       14

распределение узлов графа в ведра

0 голосов
/ 14 сентября 2018

У меня есть матрица смежности n x n. Каждый узел графа имеет m исходящих ребер, и я хочу распределить эти узлы по b сегментам. Каждое ведро должно содержать минимум l и максимум u узлов (u x b> = n). Каждый узел внутри сегмента должен иметь хотя бы один исходящий край к другому узлу внутри сегмента.

Я чувствую, что мне не хватает лучшего угла для решения этой проблемы. Как бы вы подошли к этому?

1 Ответ

0 голосов
/ 17 сентября 2018

Начните с разделения графика на связанные компоненты, это можно сделать за время O (n) и в памяти, выполнив поиск по глубине или по ширине.

Если какие-либо узлы не подключены к другому узлутогда решение невозможно.

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

      o   o
     / \  |
o   o   o o     |    |    |    |    |    |
|  / \ /  |     |    |    |    |    |    |
o o   o   o     |    |    |    |    |    |
 \ \ /   /      |____|    |____|    |____|
  --o----      Bucket 1  Bucket 2  Bucket 3

Удалить 2 узла из левого листа. 

      o   o
     / \  |
a   o   o o     |a   |    |    |    |    |
|  / \ /  |     ||   |    |    |    |    |
a o   o   o     |a   |    |    |    |    |
 \ \ /   /      |____|    |____|    |____|
  --o----      Bucket 1  Bucket 2  Bucket 3

Удалить 2 узлас правого листа. 

      o   b
     / \  |
    o   o b     |a   |    |b   |    |    |
   / \ /  |     ||   |    ||   |    |    |
  o   o   o     |a   |    |b   |    |    |
   \ /   /      |____|    |____|    |____|
    o----      Bucket 1  Bucket 2  Bucket 3

Затем удалите последнюю вершину степени 1 и ее соседа: 

      o    
     / \   
    o   o       |a   |    |b   |    |c   |
   / \ /        ||   |    ||   |    ||   |
  o   o   c     |a   |    |b   |    |c   |
   \ /   /      |____|    |____|    |____|
    c----      Bucket 1  Bucket 2  Bucket 3

Это создаст новую вершину степени 1 в оставшемся подграфе, поэтому удалите ееи смежная с ним вершина: 

      o    
     / \   
    d   o       |a d |    |b   |    |c   |
   / \ /        || | |    ||   |    ||   |
  d   o         |a d |    |b   |    |c   |
                |____|    |____|    |____|
               Bucket 1  Bucket 2  Bucket 3

Осталось только 3 вершины, если она уместится в ведро, затем поместите его в ведро - в противном случае переместите пару из ведра с наименьшим количеством элементов введро со следующим наименьшим количеством предметов и добавьте триплет на его место. 

      e    
       \   
        e       |a d |    |e e |    |c b |
       /        || | |    |\ / |    || | |
      e         |a d |    | e  |    |c b |
                |____|    |____|    |____|
               Bucket 1  Bucket 2  Bucket 3

Единственная проблема будет, когда вы получите звездообразные подключенные компоненты 

  o   o
   \ /
 o--o--o
   / \
  o   o

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

...