Discrete Graph Theory Test Review

Front

What is a circuit in graph theory?

Back

A circuit is a path in a graph that starts and ends at the same vertex.

Front

What is redundancy in graph theory?

Back

Redundancy refers to the number of edges in a graph that can be removed without disconnecting the graph.

Front

What is an Euler Path?

Back

An Euler Path is a trail in a graph that visits every edge exactly once.

Front

What is an Euler Circuit?

Back

An Euler Circuit is a circuit that visits every edge exactly once and returns to the starting vertex.

Front

What is a minimal spanning tree?

Back

A minimal spanning tree is a subset of edges that connects all vertices in a graph with the minimum possible total edge weight.

Front

How do you calculate the total cost of a minimal spanning tree?

Back

Add the weights of all the edges in the minimal spanning tree.

Front

What is a spanning tree?

Back

A spanning tree is a subgraph that includes all the vertices of the original graph and is a tree (connected and acyclic).

Front

What is the difference between a spanning tree and a minimal spanning tree?

Back

A spanning tree connects all vertices without cycles, while a minimal spanning tree has the smallest possible total edge weight.

Front

What does it mean for a graph to be connected?

Back

A graph is connected if there is a path between every pair of vertices.

Front

What is the significance of the same vertex in circuits?

Back

In circuits, starting and ending at the same vertex indicates that the path is closed.