search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
1 vote
10 views
Every graph having minimum one spanning tree

1. True

2.False

 

Which is correct?

My doubt is spanning tree is possible for any type of graph??
in Algorithms 9 points 10 views

1 Answer

0 votes

Spanning tree is usually defined for Connected Undirected Graphs only. This is due to the definition of “Tree”, as tree is a Connected Acyclic Undirected Graph.

For EVERY Connected Undirected Graph we have a spanning tree.

https://math.stackexchange.com/questions/136249/how-to-show-that-every-connected-graph-has-a-spanning-tree-working-from-the-gra

For Disconnected Undirected Graphs, we can define “Spanning Forest”.

https://cs.stackexchange.com/questions/109581/spanning-trees-on-disconnected-graphs

For Directed Graphs, we can defined “Directed Spanning Trees”

https://www.cs.tau.ac.il/~zwick/grad-algo-13/directed-mst.pdf

1.7k points
...