Graph Theory Basics

Graphs

• A graph is a collection of points (nodes or vertices) connected by lines (edges).
• A simple graph has at most one edge between two nodes and no edges that loop back to the same vertex.

Walks, Paths, and Cycles

• A walk is a succession of connected edges of length n.
• A path is a walk that does not visit the same node twice.
• A cycle is a path that ends at the same node it started at.
• A walk is closed if it ends at the same node it started at, and open otherwise.
• Two nodes are adjacent if they are connected by a line.
• A node and edge are incident if they touch.

The Handshaking Lemma

• The degree of a vertex is the number of edges that meet at that vertex.
• The Handshaking Lemma states that the sum of all degrees in a graph is twice the total number of edges.

Matrices

• Graph information can be stored in a matrix, which is a grid of numbers.
• Adjacency matrices store information about graph connections.
• Raising an adjacency matrix to a power n gives the number of walks of length n between nodes.
• Undirected graphs are symmetrical along their main diagonal.
• Distance matrices record the weight of each edge between nodes.

Matrix Multiplication

• Matrix multiplication is not commutative (AB ≠ BA).
• The product of two matrices at position m,n is the dot product of the mth row in A and the nth column in B.

The Minimum Spanning Tree

• A tree is a connected graph with no cycles that visits every node once.
• The minimum spanning tree (MST) is the tree-shaped subgraph with the lowest total weight.
• The MST for n nodes has n - 1 edges.
• There are two algorithms to find the MST: Kruskal's Algorithm and Prim's Algorithm.

Kruskal's Algorithm

• Pick the edge of least weight in the graph.
• Select the next edge of least weight that does not create a cycle.
• Repeat until all nodes are included.

Prim's Algorithm

• Choose any node.
• Choose the edge of least weight connected to this node.
• Choose the next lowest weight edge connecting the tree to a new node.
• Repeat until all nodes are included.

Prim's Algorithm for Matrices

• Choose any starting node.
• Put a line through the row of the chosen node.
• Highlight the column of the chosen node.
• Circle the edge of least weight in the column.
• Repeat until all rows are deleted.

Dijkstra's Algorithm

• Dijkstra's algorithm finds the shortest path between any two nodes.
• Steps:
  • Begin at the starting node.
  • Calculate the shortest distance back to the start for all adjacent nodes.
  • Choose the node with the shortest distance and continue working with it.
  • Repeat until the desired end node has a shortest distance written.

Learn about the definitions and concepts of graphs, walks, paths, and cycles in graph theory. Understand the difference between a walk, path, and cycle.