Finding the Spanning Tree of a Graph - Barneygumble742

  • Context: Undergrad 
  • Thread starter Thread starter barneygumble742
  • Start date Start date
  • Tags Tags
    Graph Tree
Click For Summary
SUMMARY

The discussion centers on the concept of a spanning tree in graph theory, specifically in relation to a test question posed by user Barneygumble742. The graph in question includes edges 5, 6, 7, and 8, with vertices A, B, C, D, and E. A spanning tree is defined as a subgraph that includes all vertices of the original graph while maintaining connectivity and without any cycles. The user confirms their understanding of spanning trees as induced subgraphs that exclude non-connected vertices.

PREREQUISITES
  • Understanding of graph theory concepts
  • Familiarity with terms like vertices and edges
  • Knowledge of induced subgraphs
  • Basic comprehension of connectivity in graphs
NEXT STEPS
  • Study the properties of spanning trees in graph theory
  • Learn about algorithms for finding spanning trees, such as Kruskal's and Prim's algorithms
  • Explore the concept of connected components in graphs
  • Investigate the differences between spanning trees and minimum spanning trees
USEFUL FOR

Students studying graph theory, computer scientists, and anyone interested in algorithms related to graph connectivity and spanning trees.

barneygumble742
Messages
27
Reaction score
0
hi,

what's the spanning tree from the graph shown? it was on a test and I'm curious as to if I'm right or not.

what i wrote down was a graph with edges 5, 6, 7, 8 and vertices A, B, C, D, E

barneygumble742
 

Attachments

  • graph.JPG
    graph.JPG
    5.9 KB · Views: 506
Mathematics news on Phys.org
your solution should be fine...outta curiosityf do you know what a spanning tree of a graph is?
 
i think so. it's like an induced subgraph except without the non-connected vertices?!
 

Similar threads

Undergrad Find Smallest Subtree of G w/ Nodes from S
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Number of edges in a tree digraph
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Finding if a subgraph of a minimal non-planar graph is maximal planar
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Edge connectivity of a graph given the number of edge disjoint paths
  • · Replies 1 ·
Replies
1
Views
2K
High School 4-colours theorem can be proved visually
  • · Replies 21 ·
Replies
21
Views
2K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
4K
MHB 7.8.99 find PS, VS Period, graph
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Asymptotics for finding the successors in a Binary Tree
  • · Replies 3 ·
Replies
3
Views
2K
MHB Gre.al.12 transformationof a function
  • · Replies 2 ·
Replies
2
Views
3K
Easy proof about spanning trees (for you)
  • · Replies 5 ·
Replies
5
Views
2K