% P92 (***) Von Koch's conjecture % Von Koch's Conjecture: Given a tree with N nodes (and hence N-1 edges). % Find a way to enumerate the nodes from 1 to n and, accordingly, the % edges from 1 to N-1 in such a way, that for each edge K the difference % of its node numbers equals to K. The conjecture is that this is always % possible. % Example: * Solution: 4 Note that the node number % / / differences of adjacent nodes % * -- * 3 -- 1 are just the numbers 1,2,3,4 % | \ | \ which can be used to enumerate % * * 2 5 the edges. :- ensure_loaded(p80). % conversions :- ensure_loaded(p83). % is_tree % vonkoch(G,Enum) :- the nodes of the graph G can be enumerated % as described in Enum. Enum is a list of pairs X/K, where X % is a node and K the corresponding number. vonkoch(Graph,Enum) :- is_tree(Graph), % check before doing too much work! Graph = graph(Ns,_), length(Ns,N), human_gterm(Hs,Graph), vonkoch(Hs,N,Enum). vonkoch([IsolatedNode],1,[IsolatedNode/1|_]). % special case vonkoch(EdgeList,N,Enum) :- range(1,N,NodeNumberList), N1 is N-1,range(1,N1,EdgeNumberList), bind(EdgeList,NodeNumberList,EdgeNumberList,Enum). % The tree is given as an edge list; e.g. [d-a,a-g,b-c,e-f,b-e,a-b]. % Our problem is to find a bijection between the nodes (a,b,c,...) and % the integer numbers 1..N which is compatible with the condition % cited above. In order to construct this bijection, we use an open- % ended list Enum; and we scan the given edge list. bind([],_,_,_) :- !. bind([V1-V2|Es],NodeNumbers,EdgeNumbers,Enum) :- bind_node(V1,K1,NodeNumbers,NodeNumbers1,Enum), bind_node(V2,K2,NodeNumbers1,NodeNumbers2,Enum), D is abs(K1-K2), select(D,EdgeNumbers,EdgeNumbers1), % modif 15-May-2001 bind(Es,NodeNumbers2,EdgeNumbers1,Enum). % bind_node(V,K,NodeNumsIn,NodeNumsOut,Enum) :- % V/K is an element of the list Enum, and there is no V1 \= V % such that V1/K is in Enum, and there is no K1 \= K such that % V =:= K1 is in Enum. In the case V gets a new number, it is % selected from the set NodeNumsIn; what remains is NodeNumsOut. % (node,integer,integer-list,integer-list,enumeration) (+,?,+,-,?) bind_node(V,K,NodeNumbers,NodeNumbers,Enum) :- memberchk(V/K1,Enum), number(K1), !, K = K1. bind_node(V,K,NodeNumbers,NodeNumbers1,Enum) :- select(K,NodeNumbers,NodeNumbers1), memberchk(V/K,Enum). % range(A,B,L) :- L is the list of numbers A..B range(B,B,[B]) :- !. range(A,B,[A|L]) :- A < B, A1 is A+1, range(A1,B,L). % test suite ------------------------------------------------------------ test(K) :- test_tree(K,TH), write(TH), nl, human_gterm(TH,T), vonkoch(T,Enum), write(Enum). test_tree(1,[a-b,b-c,c-d,c-e]). test_tree(2,[d-a,a-g,b-c,e-f,b-e,a-b]). test_tree(3,[g-a,i-a,a-h,b-a,k-d,c-d,m-q,p-n,q-n,e-q,e-c,f-c,c-a]). test_tree(4,[a]). % Solution for the tree given in the problem statement (picture p92b.gif): % % ?- test(3). % [g-a, i-a, a-h, b-a, k-d, c-d, m-q, p-n, q-n, e-q, e-c, f-c, c-a] % [a/1, b/2, c/12, g/11, h/13, i/14, d/3, e/4, f/5, k/8, q/10, m/6, n/7, p/9|_] % % Remark: In most cases, there are many different solutions.