es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Árboles de expansión en la programación de conjuntos de respuestas

18 Jul, 2023 Programación

Para el grafo no dirigido descrito a continuación, estoy intentando obtener sus árboles de expansión y luego separar sus hojas de los nodos internos. ¿Podrías ayudarme con mi código?

Lo que espero ver después de ejecutar el código es algo como:

Respuesta 1: spanTree(1,2), spanTree(2,3), spanTree(3,4), leaf(1), leaf(4), internal(2), internal(3).

Respuesta 2: spanTree(1,2), spanTree(1,3), spanTree(3,4), leaf(2), leaf(4), internal(1), internal(3).

% grafo no dirigido
edge(1,2).
edge(2,3).
edge(1,3).
edge(3,4).
vertex(X):- edge(X,Y).
vertex(X):- edge(Y,X).

% encontrar árboles de expansión
spanTree(X,Y):- edge(X,Y).
spanTree(X,Y):- edge(Y,X).

start(1).

reached(X):-start(X).
reached(X):-reached(Y), spanTree(Y,X).

:-spanTree(X,Y), start(Y).
:-spanTree(X,Y), spanTree(X1,Y), X != X1.
:-vertex(X), not reached(X).

% grado de un vértice
degree(X,D) :- vertex(X),D=#count {Y :spanTree(X,Y)}.

% hojas y vértices internos
{leaf(X):- spanTree(X,_),degree(X,D), D=1}:- vertex(X).
{internal(X):- spanTree(X,_),degree(X,D), D>1}:- vertex(X).
Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para separar las hojas de los nodos internos en el grafo no dirigido, se puede utilizar el siguiente código:

    % encontrar todos los árboles de expansión
allSpanTrees(Trees) :-
    setof(Tree, spanTree(Tree), Trees).

% separar hojas y nodos internos
separateNodes :-
    allSpanTrees(Trees),
    getLeaves(Trees, Leaves),
    getInternals(Trees, Internals),
    printResults(Trees, Leaves, Internals).

% obtener todas las hojas en los árboles de expansión
getLeaves(Trees, Leaves) :-
    findall(Leaf, (member(Tree, Trees), leaf(Tree, Leaf)), AllLeaves),
    sort(AllLeaves, Leaves).

% obtener todos los nodos internos en los árboles de expansión
getInternals(Trees, Internals) :-
    findall(Internal, (member(Tree, Trees), internal(Tree, Internal)), AllInternals),
    sort(AllInternals, Internals).

% imprimir los resultados
printResults(Trees, Leaves, Internals) :-
    write('Árboles de expansión: '), write(Trees), nl,
    write('Hojas: '), write(Leaves), nl,
    write('Nodos internos: '), write(Internals), nl.

% ejecutar el programa
:- separateNodes.

    El código anterior define un predicado allSpanTrees/1 que encuentra todos los árboles de expansión posibles en el grafo utilizando spanTree/2, un predicado getLeaves/2 que extrae todas las hojas de los árboles de expansión encontrados, un predicado getInternals/2 que extrae todos los nodos internos de los árboles de expansión encontrados, y un predicado printResults/3 que imprime los resultados.

    Luego, se define el predicado separateNodes/0 que utiliza los predicados auxiliares anteriores para encontrar todos los árboles de expansión, separar sus hojas y nodos internos, e imprimir los resultados finales.

    Tenga en cuenta que los predicados leaf/2 e internal/2 no se muestran aquí, ya que se asume que están implementados correctamente según el código original proporcionado.

Comments are closed.