• ? programming math graph algo Никак не могу понять, как искать максимальную (по количеству рёбер) общую связную подструктуру двух графов поиском с возвратом. Объясните кто-нибудь, пожалуйста.
    На всякий случай поясню — под подструктурой я понимаю какой-то подграф, возможно без некоторых рёбер.

Replies (4)

  • @Drino, не понял проблемы.
    1. общий подграф можно получить как покомпонентное произведение матриц смежности c[i][j] = a[i][j]*b[i][j] (O(n^2))
    2. найти все компоненты связности поиском в глубину или ширину (O(n^2))
    3. посчитать ребра во всех компонентах связности
    for(component in connected_components)
    for( (i,j) in component) // компонента — это список вершин, который надо строить в процессе поиска в ширину/глубину
    vertexs += c[i][j];
    (O(n^2))
    4. ну и выбрать максимум.
    З.Ы. сомневаюсь, что это можно сделать быстрее, чем за n^2
  • @anton0xf, vertexes*
  • @anton0xf, Естественно
    а) графы могут быть разных размеров
    б) нас интересует любое отображение вершин первого графа в вершины второго графа.
    То есть для использования данного способа нужно перебрать все перестановки вершин одного из графов.
  • @Drino, То есть для использования данного способа
    нужно перебрать все
    однозначные отображения произвольной части
    вершин одного из графов на вершины второго.
    угу.
    т.е. никакого соответствия между графами нет? круто) что-то мне подсказывает, что тогда от такого перебора полностью не избавиться..
    так действительно получается довольно неэффективное решение (хотя существование асимптотически более эффективного решения не очевидно). но совсем отказываться от него тем не менее не стоит. как минимум, его можно использовать для тестирования более изощренных подходов.