Common Types of Graphs

Types of Graphs

In our previous post, we learned what graphs are and why they’re so powerful. Now, let’s dive deeper into the fascinating variety of graphs that exist in mathematics and the real world.

Graphs come in many shapes and sizes, each with unique properties that make them suitable for modeling different kinds of systems. Just as a toolbox contains different tools for different jobs, graph theory provides different types of graphs for different problems.

In this post, you’ll learn about:
- Undirected vs. Directed graphs
- Weighted graphs and their applications
- Special graph structures (complete graphs, bipartite graphs, trees)
- When to use each type of graph

Let’s explore these fundamental graph types and see them in action!

1. Undirected Graphs

An undirected graph is a graph where edges have no orientation—the relationship between two vertices is symmetric. If an edge connects vertex A to vertex B, it automatically also connects B to A. Think of it as a two-way street.

Key Properties:
- Edges are bidirectional
- Order doesn’t matter: edge $\{A, B\}$ is the same as $\{B, A\}$
- Perfect for modeling mutual relationships

Real-World Examples:
- Social Networks: Friendship on Facebook (if you’re my friend, I’m your friend)
- Chemistry: Molecular bonds between atoms
- Geography: Borders between countries (if A borders B, then B borders A)
- Collaboration: Co-authorship in academic papers

Example: A Friendship Network

Our social network example from the previous post is an undirected graph because friendship is mutual—if Alice is friends with Bob, then Bob is friends with Alice!

Notice: The edges have no arrows—they simply connect two vertices, indicating a symmetric relationship.

2. Directed Graphs (Digraphs)

In a directed graph (or digraph), every edge has a direction, pointing from a source vertex to a target vertex. These are perfect for modeling asymmetric relationships where the connection goes one way.

Key Properties:
- Edges are unidirectional (have a direction)
- Order matters: edge $(A, B)$ is different from $(B, A)$
- Represented with arrows in visualizations
- Each vertex can have in-degree (incoming edges) and out-degree (outgoing edges)

Real-World Examples:
- Twitter/Instagram: Following relationships (you can follow someone without them following you back)
- Web Pages: Hyperlinks (page A links to page B, but B might not link back to A)
- Task Dependencies: Task B can’t start until task A is complete
- Traffic Flow: One-way streets in a city
- Food Chains: Predator-prey relationships in ecology

Example: One-Way Streets in Downtown

Imagine a small downtown area with one-way streets—a perfect example of a directed graph!

The Setup:
- Vertices: Intersections A, B, and C
- Edges: One-way streets with specific directions
- There’s a street from A to B (you can drive from A to B)
- There’s a street from B to C (you can drive from B to C)
- There’s a street from C back to A (you can drive from C to A)

Formal Notation:

The edge set $E$ would be $E = \{(A, B), (B, C), (C, A)\}$.

Important: We use parentheses $(A, B)$ to denote order in directed graphs—$(A, B)$ is different from $(B, A)$!

This creates a one-way traffic loop. Notice that you can drive around the loop clockwise, but you cannot drive directly from B to A or from C to B!

Key Observation: The arrows indicate the direction of flow. If you’re at intersection B, you can only proceed to C—you cannot go back to A directly!

In-Degree and Out-Degree:
- Vertex A: in-degree = 1 (from C), out-degree = 1 (to B)
- Vertex B: in-degree = 1 (from A), out-degree = 1 (to C)
- Vertex C: in-degree = 1 (from B), out-degree = 1 (to A)

3. Weighted Graphs

A weighted graph is a graph where each edge is assigned a numerical value called a weight. This weight can represent various real-world metrics that give meaning to the connections.

What Can Weights Represent?
- Distance: Miles or kilometers between cities
- Cost: Price or expense of traveling a route
- Time: Duration of travel or process
- Capacity: Maximum flow through a connection
- Strength: Intensity of a relationship
- Probability: Likelihood of transition between states

Formal Definition:

A weighted graph includes a weight function $w: E \rightarrow \mathbb{R}$ that assigns a real number to each edge.

Real-World Examples:
- GPS Navigation: Roads with distances and travel times
- Network Routing: Links with bandwidth capacities
- Airline Routes: Flights with costs and durations
- Telecommunications: Connections with signal strength
- Supply Chain: Routes with transportation costs

Example: A Flight Map

Consider a simplified map connecting major cities with flight routes.

The Setup:
- Vertices: New York, Chicago, and Los Angeles
- Edges: The flight paths connecting them
- Weights: The flight time in hours
- New York to Chicago: 2 hours
- Chicago to Los Angeles: 4 hours
- New York to Los Angeles: 5 hours

Why Are Weights Important?

Weighted graphs are crucial for solving optimization problems. For example:
- Shortest Path: What’s the quickest way to fly from New York to Los Angeles?
- Direct flight: 5 hours
- Via Chicago: 2 + 4 = 6 hours
- The direct flight is faster!

• Cheapest Route: If each edge had a cost weight instead, we could find the most economical route

Graph Algorithms for Weighted Graphs:
- Dijkstra’s Algorithm: Finds shortest paths from one vertex to all others
- Bellman-Ford Algorithm: Handles negative weights
- Floyd-Warshall Algorithm: Finds shortest paths between all pairs of vertices
- Prim’s/Kruskal’s Algorithm: Finds minimum spanning trees

4. Complete Graphs

A complete graph is an undirected graph where every distinct pair of vertices is connected by a unique edge. In other words, every vertex is adjacent to every other vertex—it’s a graph with the maximum possible number of edges!

Notation: A complete graph with $n$ vertices is denoted as $K_n$ (pronounced “K-n”).

Key Properties:
- Every vertex has degree $n-1$ (connected to all other vertices)
- Number of edges: $\frac{n(n-1)}{2}$ (this is the maximum for any simple graph with $n$ vertices)
- Highly connected—you can reach any vertex from any other vertex in just one step
- No missing connections—it’s as connected as possible!

Examples of Complete Graphs:
- $K_3$: A triangle (3 vertices, 3 edges)
- $K_4$: A tetrahedron shape (4 vertices, 6 edges)
- $K_5$: 5 vertices, 10 edges
- $K_n$: $n$ vertices, $\frac{n(n-1)}{2}$ edges

Example: Complete Graph $K_4$

Here’s a complete graph with 4 vertices. Notice that each of the 4 vertices is connected to the other 3 vertices, giving us a total of $\frac{4 \times 3}{2} = 6$ edges.

Count the Connections:
- Vertex A connects to: B, C, D (3 edges)
- Vertex B connects to: A, C, D (3 edges, but A-B already counted)
- Vertex C connects to: A, B, D (3 edges, but A-C and B-C already counted)
- Vertex D connects to: A, B, C (3 edges, all already counted)

Total unique edges: AB, AC, AD, BC, BD, CD = 6 edges

Real-World Applications:
- Tournament Scheduling: Every team plays every other team (round-robin)
- Network Design: Maximum redundancy—if any connection fails, alternatives exist
- Social Dynamics: A small group where everyone knows everyone
- Testing: Checking all possible pairwise interactions

5. Bipartite Graphs

A bipartite graph is an undirected graph whose vertices can be divided into two disjoint and independent sets, $U$ and $V$, such that every edge connects a vertex in $U$ to one in $V$. Crucially, there are no edges between vertices within the same set.

Key Properties:
- Vertices split into two groups: $V = U \cup V$
- No edges within a group (no edges between vertices in $U$, no edges between vertices in $V$)
- All edges go between the two groups
- Can be colored with just 2 colors (each group gets one color)

Formal Definition:

A graph $G = (V, E)$ is bipartite if we can partition $V$ into two sets $U$ and $V$ such that:
- $U \cap V = \emptyset$ (the sets are disjoint)
- $U \cup V = V$ (together they include all vertices)
- For every edge $(u, v) \in E$: either $u \in U$ and $v \in V$, or $u \in V$ and $v \in U$

Example: Job Applicants and Positions

Let’s model a hiring scenario where applicants are qualified for certain positions.

The Setup:
- Set $U$ (Applicants): $\{Alice, Bob, Carol\}$
- Set $V$ (Positions): $\{Developer, Designer, Manager\}$
- Edges: A line from an applicant to a position means they are qualified for that role
- Alice → Developer, Designer
- Bob → Developer, Manager
- Carol → Designer, Manager

Notice:
- No edges connect Alice-Bob-Carol to each other (they’re all in set $U$)
- No edges connect Developer-Designer-Manager to each other (they’re all in set $V$)
- All edges cross between the two groups!

Real-World Applications:
- Job Matching: Applicants to positions
- Dating Apps: Users to potential matches
- Recommendation Systems: Users to products/movies
- Course Scheduling: Students to classes
- Task Assignment: Workers to tasks
- Matching Problems: Any scenario with two distinct types of entities and relationships between them

Special Property: Bipartite graphs can be solved with the Maximum Matching algorithm to find optimal pairings!

6. Trees

A tree is a special type of undirected graph that is connected and has no cycles. It’s one of the most fundamental structures in computer science and mathematics.

Key Properties:
- Connected: There’s a path between any two vertices
- Acyclic: No loops or cycles exist
- Unique paths: Exactly one path exists between any two vertices
- Minimal connectivity: Removing any edge disconnects the graph
- Edge count: A tree with $n$ vertices has exactly $n-1$ edges

Important Theorem:

In a tree with $n$ vertices, there are always exactly $n-1$ edges.

Tree Terminology:
- Root: A designated starting vertex (in rooted trees)
- Leaf: A vertex with degree 1 (endpoint)
- Internal Node: A non-leaf vertex
- Parent/Child: Relationships in rooted trees
- Height: The longest path from root to a leaf
- Subtree: A tree formed by a vertex and all its descendants

Verify the Property:

Count the vertices and edges in the tree above:
- Vertices: (count them)
- Edges: (count them)
- Does it satisfy $|E| = |V| - 1$? ✓

Real-World Applications:
- File Systems: Directory and folder hierarchies
- Organization Charts: Company structure
- HTML/XML: Document structure (DOM tree)
- Family Trees: Genealogy and ancestry
- Decision Trees: AI and machine learning
- Binary Search Trees: Efficient data storage and retrieval
- Network Routing: Spanning trees in networks
- Parse Trees: Compiler design and language processing

Special Types of Trees:
- Binary Tree: Each node has at most 2 children
- Binary Search Tree: Ordered binary tree for searching
- Balanced Tree: Height is minimized (like AVL trees, Red-Black trees)
- Spanning Tree: A tree that includes all vertices of a graph
- Minimum Spanning Tree: Spanning tree with minimum total edge weight

Combining Graph Types

Real-world problems often involve combinations of these graph types:

Examples:
- Directed Weighted Graph: Road network with one-way streets and distances
- Directed Acyclic Graph (DAG): Task dependencies in project management
- Weighted Bipartite Graph: Job matching with qualification scores
- Weighted Tree: Network design with minimum cost spanning tree

Quick Reference Table

What’s Next?

Now that you understand the basic types of graphs, you’re ready to dive deeper! In the next posts, we’ll explore:

• Graph Properties: Degree, paths, cycles, and connectivity
• Graph Algorithms: How to traverse, search, and optimize graphs
• Advanced Topics: Coloring, planarity, and special graph structures

Continue Learning:
- ← Previous: What is a Graph?
- → Understanding Graph Order, Size, and Degree

Try It Yourself!

Ready to create and experiment with different types of graphs?

👉 Visit the GraphArena Playground to:
- Build your own graphs
- Experiment with different graph types
- Visualize graph properties
- Test your understanding

Try creating each type of graph we discussed and see how they behave differently!