Самый большой пустой подграф неориентированного графа в SWI Prolog

Дан неориентированный граф. Найдите номер внутренней устойчивости графа. Это означает определение степени наибольшего пустого подграфа. (Пустой подграф - это такой подграф, вершины которого не соединены непосредственно ребрами).

Я задаю ребра и вершины. И я показываю список вершин, не связанных ребрами.

Что я должен делать дальше?

reb(a,1,2).   % (* 1 ---a--- 2 ---b--- 3 ---d--- 4 ---e--- 6  *)
reb(b,2,3).   % (*  \_________c_______/                   /   *)
reb(c,1,3).   % (*                      7 ---g--- 5 ---f-*    *)
reb(d,3,4).                             
reb(e,4,6).
reb(f,5,6).
reb(g,5,7).

ver(1).   % (* empty subgraphs here are                   *)
ver(2).   % (*  145, 146, 147, 245, 246, 247, 35, 36, ... *)
ver(3).   % (* the length of the largest of them is 3     *)
ver(4).   
ver(5).
ver(6).
ver(7).

edge(A, B) :- reb(_,A,B) ; reb(_,B,A).

nonadjacency(A, B) :-
    ver(A), ver(B), \+(edge(A,B)).

do(L) :-
    findall( (A,B), nonadjacency (A,B), L), write(L), nl.

dfs(From, To, _, [edge(From, To)]) :-
    edge(From, To).

dfs(From, To, VisitedNodes, [(From, X) | TailPath]) :- 
    edge(From, X), 
    not(member(X, VisitedNode)),
    dfs(X, To, [From | VisitedNodes], TailPath).

graph undirected-graph prolog
person Anastasia Selikova    schedule 09.11.2020    source источник
comment
Я изменил большинство на самый большой, надеюсь, что все в порядке. (наверняка вам переводили с какого-то русского термина). ---- в вашем графе нет несвязанного подграфа, все 7 вершин связаны - если мы рассматриваем связность как симметричное транзитивное замыкание отношения reb/3. то есть 1-2-3-4-6-5-7. или это не так? не могли бы вы просто показать нам несвязанный подграф в вашем случае? просто результат, а не код.   -  person Will Ness    schedule 11.11.2020
comment
здесь пустые подграфы 145, 146, 147, 245, 246, 247, 35, 36, 37. длина самого большого из них - 3   -  person Anastasia Selikova    schedule 12.11.2020
comment
почему не 167? не будет ли это тоже считаться пустым подграфом? Можно ли определить пустой подграф как набор вершин исходного графа, при котором в исходном графе нет ребер, непосредственно соединяющих любую из вершин в этом наборе? (просто пытаюсь понять вопрос)   -  person Will Ness    schedule 12.11.2020
comment
Да, 167, тоже пустой подграф   -  person Anastasia Selikova    schedule 12.11.2020
comment
Мой SWI-Prolog сообщает о синтаксической ошибке в строке 23 из-за недопустимого пробела в nonadjacency (A,B) и серьезном предупреждении об одноэлементной переменной из-за опечатки VisitedNode в строке 30. Пожалуйста, обновите вопрос.   -  person Isabelle Newbie    schedule 12.11.2020

Ответы (1)


arrow_upward
1
arrow_downward

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

empty_subgraph(       E, M ) :-
    findall( X, ver(X), Vertices),
    subset( Vertices, E ),
    \+ is_connected(  E ),
    length(           E, M ).

is_connected(  E ) :-
    select( A, E, N ), 
    select( B,    N, _),
    \+ \+ ( reb(_,A,B) ; reb(_,B,A) ).   % an edge exists

Использование select/3.

Все, что осталось, - это перечислить подмножества Vertices, от наибольшего к наименьшему.

Простой код не справится:

subset( S, S).
subset( S, X) :- select(_, S, N), subset( N, X).

Вы понимаете почему?

. . .

. . .

Ответ - стратегия поиска в глубину Prolog. Чтобы получить более крупные подмножества перед более короткими, нам нужен поиск в ширину. Придется кодировать сами:

subset( S, X) :- XS = [S|T], bfs_subsets(XS,T), member(X,XS).

bfs_subsets( [[] | _], []  ) :- !.
bfs_subsets( [[_]| _], [[]]) :- !.
bfs_subsets( [S  | T],   Q ) :-
    findall( N, select(_, S, N), NS ),
    append( NS,       Z, Q ),
    bfs_subsets(   T, Z ).

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

70 ?- empty_subgraph( E, M ).
E = [3, 6, 7],
M = 3 ;
E = [3, 6, 7],
M = 3 ;
E = [2, 6, 7],
M = 3 ;
E = [2, 6, 7],
M = 3 ;
E = [2, 4, 7],
M = 3 ;
.......

Вы можете найти способ избавиться от дубликатов или, что еще лучше, вообще не создавать их.

person Will Ness    schedule 12.11.2020