5 Questions
What is a common way to store information about the connections of a graph?
Adjacency matrix
What is the purpose of Kruskal's Algorithm?
To find the minimum spanning tree
Raising an adjacency matrix to a power n gives the number of what?
Walks of length n
What is the purpose of Dijkstra's Algorithm?
To find the shortest path between two nodes
What is the main difference between Prim's Algorithm and Kruskal's Algorithm?
The order in which edges are chosen
Study Notes
Graphs
- A graph is a collection of points, called nodes or vertices, connected by lines called edges.
- Edges can have a weight and can be directed.
Graph Representation
- Graph information can be stored in a matrix, known as an adjacency matrix.
- Adjacency matrices store information about connections between nodes.
Matrix Operations
- Raising an adjacency matrix to a power n gives the number of walks of length n between any two nodes.
Distance Matrices
- Distance matrices record the weight of each edge between nodes.
Minimum Spanning Tree (MST)
- The MST is a subgraph that connects all nodes of a graph with the lowest total weight.
- MST can be found using Kruskal's Algorithm or Prim's Algorithm.
Kruskal's Algorithm
- Continually choose the lowest-weight edge that does not create a loop in the tree.
Prim's Algorithm
- Start at a random node and continually choose the lowest-weight edge that connects the tree to an unconnected node.
Shortest Path
- Dijkstra's Algorithm is used to find the shortest path between two nodes.
This quiz covers the basics of graph theory, including nodes, edges, and weight, as well as matrix representations and matrix multiplication.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
