Solution to Define spanning trees in a weighted graph, with an example - Sikademy
Author Image

Archangel Macsika

Define spanning trees in a weighted graph, with an example

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

Let G=(V,E,\phi) be the weighted unordered connected graph where V=\{v_1,...,v_n\} is a set of vertices ,E=\{e_1,...,e_m\} the set of edges of the graph, where e_j=\{v^{(j)}_1,v^{(j)}_2\},v^{(j)}_1,v^{(j)}_2 \in V,j=1,...,m each edge is pair of distinct vertices of the graph and \phi:E\rarr R is a function of weight of the graph so \forall (e\in E)\phi(e)\in R ia a real weight of the edge e. Connected aciclic subgraph T=(V,E_1,\phi) of the given graph G=(V,E,\phi) with the same set V of the vertex and weight function \phi:E_1\rarr R but having subset of all edges E_1\subset E such that |E_1|=|V|-1 thus T contains minimal set of edges from G to connect all vertices of G but there are many spanning subtrees T . Very important characterictics of a spanning tree T is it's weight \phi(T)=\sum_{e\in E(T)} \phi(e) i.e. sum of wiights of all it's edges'. Spanning subtree T_{min} is said to be minimal subtree if it has minimal weight in the set of all spanning subtrees of the given graph and do function of connectivity with minimal total weight, but such minimal spanning subtrees are defined ambiguously in general case.

In the next picture we can see weighted graph G=(V,E,w)

for which V=\{1,2,3,4\} is it.s set of verices. E=\{e_1,e_2,e_3,e_4\} - the set of edges and w(e_1)=1,wi(e_2)=1,w(e_3)=1.w(e_4)=3 - are edges weighes . This graph has 4 spanning subtrees shown in the next picture

One of them- T4 is a minimak spanning subtree.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-656-qpid-541