Теория Графов. Как найти наибольшее независимое множество, используя алгоритм Мальгранжа?

Question

[max_addington]

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

Comments

[sim3x]

Напишите алгоритм словами
Напишите алгоритм в блоках
Реализуйте на любом яп

Answer 1

[longclaps]

Если за неделю ты не понял, что граф на рисунке не является ортографом (или же что все его дуги - двунаправленые) - брось это безнадёжное занятие.

Comments

[max_addington]

у меня нет выбора, дан граф по нему необходимо сдавать курсовую...

[longclaps]

max_addington, выход есть - пойти к учителю и сказать, что вы чего-то в задании не понимаете.
Например, не находите стрелочек на рёбрах.

[max_addington]

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

[longclaps]

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

[max_addington]

longclaps, вы знайте Алгоритм Мальгранжа, для поиска наибольшего независимого множества?

[max_addington]

longclaps, меня интересует только получение наибольшего независимого множества, основываясь на алгоритме Мальгранжа. (я не прошу помощи с кодом, помогите понять, как он действует, код я в состоянии написать и сам)

[longclaps]

max_addington, вы что, не втыкаете: вот вики, тут ясно сказано, что речь идёт об ортографе. Может, есть другой алгоритм Мальгранжа - но я другого не нашел.

[max_addington]

longclaps, да я во что угодно уже воткнуться готов :D, я понимаю что речь может идти об орграфе, но именно данный алгоритм необходимо применить к данному неорграфу, и вот ничего его не волнует. НАДО

[longclaps]

max_addington, вот тебе решение для рисунка из вики

vertexes = set('abcdefgh')
childs = {'a': 'b', 'b': 'cef', 'c': 'dg', 'd': 'ch',
          'e': 'af', 'f': 'g', 'g': 'f', 'h': 'dg'}
parents = {v: [] for v in vertexes}
for v, uu in childs.items():
    for u in uu:
        parents[u].append(v)
res = []
while vertexes:
    seed = vertexes.pop()
    tplus, tminus = {seed}, {seed}
    for t, links in zip([tplus, tminus], [childs, parents]):
        nxt = t
        visited = set()
        while nxt:
            cur, nxt = nxt, set()
            for v in cur:
                if v in visited:
                    continue
                visited.add(v)
                for u in links[v]:
                    nxt.add(u)
            t.update(nxt)
    tplus &= tminus
    res.append(''.join(sorted(tplus)))
    vertexes -= tplus
print(res)