Graph theory is a branch of mathematics that studies the relationships between objects. At its core, a graph consists of a set of nodes (also called vertices) connected by edges (also called links). Graphs can model a wide range of real-world systems: social networks where people are nodes and friendships are edges; transportation networks where locations are nodes and routes are edges; and even molecule structures where atoms are nodes and bonds are edges. The study of graphs allows us to formalize questions like: How many edges are needed to connect a group of nodes? What is the shortest path between two nodes? How can we color a map so that adjacent regions have different colors? Beyond these, graph theory concerns properties such as connectivity, planarity, cycles, degrees, and symmetry. It provides foundational tools for designing efficient networks, analyzing data flow, and solving optimization problems. Throughout this session, you will encounter concepts like paths, cycles, trees, graphs with and without direction, and special graph families such as bipartite graphs and complete graphs. You will also see how algorithms, from simple traversals to sophisticated optimization methods, exploit these structures to produce practical solutions.
Which statement best describes a graph in graph theory?
Sign up to unlock quizzes
Simple Graph Illustration
Consider a tiny network: A, B, C, D as nodes. Edges exist between A-B, B-C, C-D, and D-A, forming a square. This undirected graph has 4 vertices and 4 edges. If we add a diagonal edge A-C, the structure becomes more interconnected. Such drawings help visualize concepts like degree (number of edges incident to a vertex) and paths. In this example, degrees are: deg(A)=3, deg(B)=2, deg(C)=3, deg(D)=2. Traversing the edges shows how a path from A to C can be A-B-C or A-D-C. This simple graph introduces ideas you will see again: adjacency, degree, and the existence of cycles.
A path in a graph is a sequence of distinct edges that joins a sequence of vertices where each adjacent pair is connected by an edge. A graph can contain multiple paths between two vertices. When a path starts and ends at the same vertex, it is called a cycle. If a graph contains a cycle that visits each vertex exactly once before returning to the start, it is a Hamiltonian cycle. If a graph contains a cycle that visits every edge exactly once, it is an Eulerian cycle. Understanding these ideas helps in navigation problems, circuit design, and network routing. Additionally, the concept of connectivity concerns whether a path exists between every pair of vertices; a graph is connected if there is a path between any two vertices, and it is disconnected otherwise. Directed graphs (digraphs) introduce orientation, where edges have a direction, and the ideas of in-degree and out-degree per vertex become central.
What is a cycle in a graph?
Sign up to unlock quizzes
In a directed graph, the in-degree of a vertex counts edges _____ into the vertex, and the out-degree counts edges _____ from the vertex.
Sign up to unlock quizzes
Paths vs Cycles Example
Take a directed graph with vertices {A,B,C} and edges A->B, B->C, C->A. This forms a directed cycle A->B->C->A. A path A->B->C is valid, and its edges are all visited once. If we repeat A, we would have a cycle. Distinguishing between paths and cycles is crucial for problems like finding routes that return to a starting point or discovering long acyclic paths for scheduling tasks.
Which statement best distinguishes a connected graph from a disconnected graph?
Sign up to unlock quizzes
Connectivity Visual
Consider a graph with two components: Component 1 has vertices {A,B,C} connected in a chain A-B-C; Component 2 has vertices {D,E} with an edge D-E. There is no path from a vertex in {A,B,C} to a vertex in {D,E}. The graph is disconnected with two components. If we add an edge C-D, the graph becomes connected, linking the components and creating a single component.
Trees are a special kind of graph with five defining properties: a tree is connected, acyclic (no cycles), and has exactly n-1 edges if it has n vertices. Trees are fundamental in representing hierarchical structures like organizational charts, file systems, and taxonomic classifications. A rooted tree designates one vertex as the root, which helps in performing operations like depth-first search, breadth-first search, and distance calculations from the root. In many applications, we want to find minimal connections that keep everything reachable; this leads to spanning trees in graphs: a subgraph that is a tree containing all the vertices of the original graph. The notion of leaves (vertices with degree 1) and internal nodes plays a key role in understanding tree structure and optimization problems like minimizing edge count while preserving connectivity.
Which of the following statements characterizes a tree with n vertices?
Sign up to unlock quizzes
In a rooted tree, every node (except the root) has a unique _____, and a node with no children is called a _____.
Sign up to unlock quizzes
Constructing a Spanning Tree
Given a connected graph with vertices {A,B,C,D} and edges {A-B, B-C, C-D, D-A, A-C}, a spanning tree can be formed by selecting edges {A-B, B-C, C-D} which connect all vertices without forming a cycle. The resulting tree has 4 vertices and 3 edges. Spanning trees are important in network design because they connect all nodes with minimum redundancy.
Which property is guaranteed by a spanning tree of a connected graph?
Sign up to unlock quizzes
Depth-First Search (DFS) on a Tree
In a rooted tree, DFS starting from the root visits nodes by going as deep as possible before backtracking. This traversal yields a linear order of discovery that is useful for tasks like generating postorder sequences or validating tree structure. For example, given a tree rooted at R with children A and B, DFS may visit R -> A, then its descendants, back to R, then B and its descendants. DFS is fundamental for many tree algorithms and for implementing recursive solutions.
Graph representations are foundational for efficient computation. The two common representations are adjacency lists and adjacency matrices. An adjacency list stores for each vertex a list of its neighbors, which is space-efficient for sparse graphs. An adjacency matrix is a 2D matrix where cell (i,j) indicates whether an edge from i to j exists; it enables constant-time edge checks but uses O(n^2) space. The choice depends on graph density and the operations you intend to perform. For undirected graphs, the matrix is symmetric; for directed graphs, it is asymmetric. Other representations include incidence lists and edge lists. Graphs can also be weighted, where edges carry numerical values representing distance, cost, or capacity. Algorithms like Dijkstra’s for shortest paths and Kruskal’s or Prim’s for minimum spanning trees rely on these representations to access neighbor information efficiently.
Which graph representation is typically more memory-efficient for sparse graphs?
Sign up to unlock quizzes
In an undirected graph, the adjacency matrix is _____ symmetric, meaning a(i, j) = a(j, i).
Sign up to unlock quizzes
Adjacency List vs Matrix
Consider a graph with 4 vertices V = {A,B,C,D} and edges {A-B, A-C, B-D}. An adjacency list: A -> {B,C}, B -> {A,D}, C -> {A}, D -> {B}. An adjacency matrix would be a 4x4 grid with 1s at (A,B), (A,C), (B,D) and their symmetric pairs for an undirected graph. For dense graphs, the matrix is convenient for quick edge existence checks; for sparse graphs, the list is memory-friendly and often faster for traversals.
Which algorithm is commonly used to find the shortest path in graphs with non-negative edge weights?
Sign up to unlock quizzes
Planarity is a property of a graph drawn on a plane without any edges crossing. Some graphs are planar, while others are not; for example, K5 (the complete graph on five vertices) and K3,3 (the utility graph) are classic non-planar graphs. Planar graphs have many interesting properties and support efficient algorithms for drawing, embedding, and coloring. The four color theorem states that any planar graph can be colored with at most four colors so that no adjacent vertices share a color. Graph coloring, in general, is about assigning colors to vertices under constraints and has applications in scheduling, register allocation in compilers, and resource allocation. Understanding planarity also helps in network design where physical layout matters. Algorithms for planarity testing determine whether a graph can be drawn without edge crossings, and if not, they can provide a minor or a non-planar embedding to study structural properties.
Which graph is non-planar?
Sign up to unlock quizzes
White space and color restrictions in planar graphs lead to the famous _____ theorem stating that four colors suffice for any planar map.
Sign up to unlock quizzes
Planarity Testing Idea
A basic approach to planarity testing checks for edge crossings under a specific embedding. Modern algorithms (Hopcroft and Tarjan) can determine planarity in linear time. While constructing an embedding is non-trivial, understanding that some graphs force crossings guides us to study their minors and genus. Practical examples include circuit board layout and geographic map coloring, where planarity constraints impact feasibility and aesthetics.
What is a key consequence of a graph being planar?
Sign up to unlock quizzes
Coloring a Planar Graph
Take a planar graph with faces forming a map-like division. According to the Four Color Theorem, you can color the vertices using at most four colors so that no adjacent vertices share a color. A practical approach is greedy coloring with a suitable vertex ordering, which often uses far fewer than four colors in many small graphs, though a worst-case guarantee is four.
Graph algorithms often tackle optimization problems on graphs. Two cornerstone problems are the shortest path problem and the minimum spanning tree problem. The shortest path problem seeks the minimum total weight from a source vertex to every other vertex, which is essential for navigation and routing. Dijkstra’s algorithm solves this for graphs with non-negative weights, while the Bellman-Ford algorithm handles negative weights. The minimum spanning tree problem asks for a subset of edges that connects all vertices with the minimum possible total weight, enabling efficient network design with minimal cabling or cost. Algorithms like Prim’s and Kruskal’s solve this, each with different strategies: Prim’s grows a tree by adding the cheapest edge from the current tree, Kruskal’s builds a minimum spanning tree by repeatedly adding the smallest edge that does not form a cycle. In undirected graphs, a spanning tree has exactly n-1 edges for n vertices, and its total weight is as small as possible.
Which algorithm guarantees the shortest paths from a single source in graphs with non-negative weights?
Sign up to unlock quizzes
The _____ algorithm is used to construct a minimum spanning tree by repeatedly adding the smallest edge that connects two components without forming a cycle.
Sign up to unlock quizzes
Shortest Path Example
In a weighted graph with vertices S, A, B, and T, edges with weights: S-A(2), S-B(5), A-T(4), B-T(1). The shortest path from S to T is S-A-T with total weight 6 or S-B-T with total weight 6; Dijkstra’s algorithm would explore S, then the lighter edge to A (2) and B (5), and finally reach T via the optimal route.
Which problem asks for a connected subgraph with minimal total edge weight that includes all vertices?
Sign up to unlock quizzes
Prim's vs Kruskal's in Practice
Prim's algorithm grows a single tree by always adding the cheapest edge from the tree to a new vertex. Kruskal's algorithm sorts all edges globally and adds the smallest edge that does not form a cycle. In dense graphs, Prim's approach with a priority queue often performs well, especially when implemented with a min-heap. In sparse graphs, Kruskal's method can be more efficient due to fewer edges to consider. Both yield the same MST when the graph is connected.
You've previewed 6 of 12 pages
Sign up free to unlock the rest of this lesson and start tracking your progress.
6 more pages waiting:
- Page 7
- Page 8
- Page 9
- Page 10
- +2 more...