Flashcard Review - Minimum Spanning Trees

Front

What is a subgraph?

Back

A subgraph is a part of a graph or the whole graph redrawn.

Front

What is the weight of the minimum spanning tree according to Prim's Algorithm?

Back

7

Front

How many edges are in a tree with 32 vertices?

Back

31

Front

What is a Spanning Tree?

Back

A Spanning Tree is a subset of a graph that includes all the vertices with the minimum number of edges.

Front

What does it mean if a graph contains no cycles?

Back

It means the graph is a tree.

Front

Define a Minimum Spanning Tree.

Back

A Minimum Spanning Tree is a spanning tree with the smallest possible total edge weight.

Front

What is the difference between a graph and a subgraph?

Back

A graph is a collection of vertices and edges, while a subgraph is a portion of a graph.

Front

What is Prim's Algorithm used for?

Back

Prim's Algorithm is used to find the Minimum Spanning Tree of a graph.

Front

What is the significance of edges in a tree?

Back

In a tree, the number of edges is always one less than the number of vertices.

Front

What is a cycle in a graph?

Back

A cycle is a path that starts and ends at the same vertex without traversing any edge more than once.