$G$ is a graph whose vertices are all $3$ element subsets of $\lbrace{1,2,3,4,5,6}\rbrace$. Sets A and B are considered adjacent vertices of G if they have exactly one number in common and that number is the cost of the edge AB. Find a cheapest spanning tree of G.

My solution: Graph $G$ is to be taken and the $3$ element subsets are chosen from $\binom{6}{3} = 20$, so there are $20$ subsets taken from the array. {$1,2,3$}, {$1,3,4$}, {$1,4,5$}, {$1,5,6$},{$2,3,4$},{$2,4,5$},{$2,5,6$} and so on..

I assume that we have to take subsets with a common element and mark it as a vertex, once chosen I would apply Kruskal's algorithm to find the cheapest cost based on the Edge's weight, and the weight determined by the common element between two vertices.

There are $10$ edges between the vertices.

I'm not sure how to put it in a formal proof? could anyone show me how to do so?

  • $\begingroup$ Could you please define your metric for "cheaper"? Is it the average cost to reach nodes/vertices? If so, then I think you really need to define a reference vertex from which reachability towards the other vertices is optimized. E.g. in networking, the Spanning Tree Protocol finds a spanning tree that is optimized for shortest path towards the "root bridge". $\endgroup$ – caveman Sep 13 '17 at 22:17
  • $\begingroup$ @caveman by cheapest path I mean the shortest route and the weight of the edge is determined by the common subset element, you can take a reference vertex probably from ${1,2,3}$ $\endgroup$ – Prathik Gurudatt Sep 13 '17 at 22:19
  • $\begingroup$ Yes, thought so. I don't think that all graphs will have a "universal shortest path for everyone". You will probably find graphs where the shortest path varies depending on the reference node you measure from. $\endgroup$ – caveman Sep 13 '17 at 22:22
  • $\begingroup$ @caveman from what I tried I listen down all the vertices with cost '1', then '2' then '3', though the method was slower, it did give me an insight as to how the graph might look like, but I'm not sure if that is a legal proof. $\endgroup$ – Prathik Gurudatt Sep 13 '17 at 22:25

The vertex $ \{ 1,2,3 \}$ is joined to the $9$ verticies of the form $ \{ a, B,C \}$ where $ a \in \{ 1,2,3 \}$ and $B , C \in \{4,5,6 \} $. The next layer consists $9$ verticies is of the form $ \{a,b,C \}$ where $ a,b \in \{ 1,2,3 \}$ and $ C \in \{4,5,6 \} $. There is then a final layer consisting of the $1$ vertex $ \{ 4,5,6 \}$.

There $10$ verticies are of the form $ \{ 1, x,y \}$ where $x,y>1$; There $6$ verticies are of the form $ \{ 2, x,y \}$ where $x,y>2$; There $3$ verticies are of the form $ \{ 3, x,y \}$ where $x,y>3$; There is $1$ vertex are of the form $ \{ 4, x,y \}$ where $x,y>4$; and this is the full list of $20$ verticies.

The cheapest spanning tree will be obtained by joining each set by its smallest element. Such a tree can formed as follows ...

Join $ \{1,2,3 \}$ to its $9$ nearest neighbours. Join each of the $3$ sets $ \{ 1, A,B \} $ to the $2$ sets of the form $ \{1,a,C \}$ where $A,B,C \in \{4,5,6 \}$ and $a=2$ or $3$. Join each of the $3$ sets $ \{ 2, A,B \} $ to the $2$ se sets of the form $ \{2,3,C \}$ where $A,B,C \in \{4,5,6 \}$. Finally join the vertex $ \{4,5,6 \}$ to $ \{ 1,2,4 \}$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.