Answer to Question #274995 in Discrete Mathematics for V.kathiravan

Question

Define spanning trees in a weighted graph, with an example

Answer 1

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.