#algorithm #graph-theory #bipartite
#алгоритм #теория графов #двудольный
Вопрос:
Я работаю над проблемой, которая требует удаления транзитивных узлов в графе. Более конкретно, мне нужно уменьшить количество ребер, удалив узлы с пути между двумя наборами узлов.
На картинке написано тысячу слов, так что вот что я пытаюсь сделать
Граф содержит 3 типа узлов (Ai, Bi, Ci). Я хотел бы уменьшить график, удалив все узлы Bi на пути между узлами Ai и Ci, сохраняя при этом достижимость между узлами Ai, Ci.
Это действительно трехсторонний график, и мне интересно, существует ли эффективный алгоритм, который может уменьшить его в соответствии с описанием, показанным на прилагаемом рисунке.
Комментарии:
1. Почему граф трехсторонний?
2. Поскольку вам нужно удалить все узлы B, и вам нужно добавить ребро A-C для каждой пары ребер A-B-C, боюсь, вы не можете сделать лучше, чем перебирать все B-узлы и для каждого B-узла перебирать все его A-соседи и все его C-соседи.
3. @Stef да, это своего рода мой текущий подход, но мне интересно, есть ли более эффективный алгоритм. Мне кажется, что должен быть один, но, возможно, я ошибаюсь.
4. Как вы храните этот график, какую структуру данных? Можем ли мы четко определить, является ли узел типом A, B и C, или нам нужно его разбить?
Ответ №1:
Если мы позволим A обозначить матрицу смежности между As и Bs и B обозначим матрицу смежности между Bs и Cs, то матрица смежности результирующего графа является булевым матричным произведением AB . Теоретически применяются алгоритмы быстрого умножения матриц (если у вас плотные матрицы), но на практике я сомневаюсь, что они сильно помогут.