Are all MST minimum spanning trees reachable by Kruskal and Prim? Computer Science

---

Are all MST minimum spanning trees reachable by Kruskal and Prim? Posted: 05 May 2018 05:01 PM PDT I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for Prim's algorithm? EDIT: To be more precise, I want to know if given an MST for a connected, undirected, weighted graph, is it guaranteed that there is a sequence of steps using Kruskal or Prim which generates this MST. E.g. There are different choices for Kruskal when there are multiple edges with the same weight. Similarly for Prim. EDIT2: Thank you everyone for your help. I am only interested in the theoretical result of whether it is true or not and not in any algorithm to generate all the actual MSTs. I found the following result helpful in proving the case for Kruskal: https://cs.stackexchange.com/questions/2204/do-the-minimum-spanning-trees-of-a-weighted-graph-have-the-same-number-of-edges I am now thinking about the case for Prim. submitted by /u/domoremath [link] [comments]

Using clingo to see all possible rectangles inside an n by n grid. Posted: 05 May 2018 08:00 PM PDT I'm having a lot of trouble with predicate logic. I'm trying to use clingo to see all possible rectangles inside an n by n grid but the output does not yield only rectangles. Here's what I've written: % Define rows and columns row(1..n). col(1..n). % Define exactly 4 vertices 4 {vertex(I, J) : row(I), col(J)} 4. % Here is where I think my problem is % I want to say: % if exists vertex(A, C), vertex(B, C), vertex(A, D), vertex(B, D) % Point A is not equal to point B. Point C is not equal to point D. :- vertex(A, C), vertex(B, C), vertex(A, D), vertex(B, D), A != B, C != D. % Show only the values for vertices. #show vertex/2. I'm unsure of where I am going wrong. submitted by /u/grep-recursive [link] [comments]

You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now.	Email delivery powered by Google
Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States