Overview
This lecture introduces graph theory, covering types of graphs, key concepts like adjacency, degrees, and special paths, and introduces weighted graphs.
Graph Basics and Types
- A graph consists of vertices (nodes) and edges (connections between vertices).
- Graphs can represent real-world structures, like maps where provinces are vertices and shared borders are edges.
- An undirected graph has edges with no direction; a directed graph's edges have a direction.
- A simple graph has only one edge between any two vertices; a multigraph has multiple edges between some vertex pairs.
- A directed multigraph allows multiple directed edges between pairs of vertices.
Key Concepts in Graph Theory
- Two vertices are adjacent if they are connected by an edge.
- An edge is incident with its two endpoints.
- The degree of a vertex is the number of incident edges (undirected).
- In a directed graph, in-degree is the number of edges coming into a vertex; out-degree is edges going out.
- A loop (an edge from a vertex to itself) contributes 1 to both in-degree and out-degree.
Paths, Circuits, and Connectivity
- A path is a sequence of edges joining a sequence of vertices (e.g., IMJ).
- A circuit (or cycle) is a path that starts and ends at the same vertex (e.g., IMJI).
- A graph is connected if a path exists between every pair of vertices; disconnected if not.
Special Paths: Euler and Hamilton Paths/Circuits
- An Euler path traverses every edge exactly once; an Euler circuit does so and starts/ends at the same vertex.
- An Euler circuit exists if all vertex degrees are even; an Euler path exists if exactly two vertices have odd degrees.
- A Hamilton path visits every vertex exactly once; a Hamilton circuit does so and is a cycle.
Weighted Graphs
- Weighted graphs have edges assigned numerical values (weights) representing quantities like distance, cost, or time.
- Path length in a weighted graph is the sum of weights along the path.
- Finding shortest paths in weighted graphs is a key application (not covered in this lecture).
Key Terms & Definitions
- Vertex (Node) — a point in the graph.
- Edge — a connection between two vertices.
- Degree — number of edges incident to a vertex.
- In-degree — number of incoming edges to a vertex (directed graph).
- Out-degree — number of outgoing edges from a vertex (directed graph).
- Path — sequence of edges connecting vertices.
- Circuit/Cycle — path starting and ending at the same vertex.
- Euler Path/Circuit — path or circuit traversing every edge once.
- Hamilton Path/Circuit — path or circuit visiting every vertex once.
- Weighted Graph — graph with numbers assigned to edges.
Action Items / Next Steps
- Review Chapter 5.3 in the textbook.
- Prepare for further discussion on algorithms for finding shortest paths in weighted graphs.