Spanning tree

A tree is a connected undirected graph with no cycles.

It is a spanning tree of a graph G if it spans G (that is, it includes every vertex of G) and is a subgraph of G (every edge in the tree belongs to G).

A spanning tree of a connected graph G can also be defined as a maximal set of edges of G that contains no cycle or as a minimal set of edges that connect all vertices.


https://en.wikipedia.org/wiki/Spanning_tree

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s