AQR UNIT 7 REVIEW

Front

What is the first step of Kruskal's Algorithm?

Back

Put all weights in a list from smallest to largest.

Front

In a Euler's Circuit or Path, can you use a vertex twice?

Back

True

Front

What is a cycle in graph theory?

Back

A path that starts and ends at the same vertex and does not use any edge more than once.

Front

What does a Hamiltonian path touch?

Back

All vertices.

Front

What is the smallest number of colors needed to color a graph called?

Back

Chromatic number.

Front

What is Kruskal's Algorithm used for?

Back

Finding the minimum spanning tree of a graph.

Front

What is a vertex in graph theory?

Back

A point where two or more edges meet.

Front

What is an edge in graph theory?

Back

A connection between two vertices.

Front

What is a complete graph?

Back

A graph in which every pair of vertices is connected by an edge.

Front

What is the difference between a path and a cycle?

Back

A path does not repeat vertices, while a cycle starts and ends at the same vertex.