Introduction to Graph | Types | Different Conventions Used

Welcome to the foundational opening chapter of the Graph Data Structures and Algorithms (DSA) series. This chapter establishes the fundamental nomenclature, mental models, types of graphs, and core mathematical properties that will be utilized throughout all subsequent advanced graph modules.

1. Why Do We Need Graphs? (The Problem Statement)

In software engineering and real-world modeling, hierarchical data structures like binary trees or linear lists fall short when we need to represent complex, many-to-many relationships (e.g., social network friend connections, GPS map routing, computer network topologies).

• Status Quo Limitation: Trees enforce a strict parent-child single-path hierarchy with an explicit root.
• The Graph Solution: Graphs generalize trees by allowing arbitrary connections between any entities, making them the ultimate structure for modeling networks.

2. Core Mental Model & Terminology

At its core, a graph is composed of two primary building blocks: Nodes (or Vertices) and Edges.

• Nodes / Vertex ($V$ or $N$): The circular entities representing individual data points, objects, or locations.
  • They are typically labeled with numbers (e.g., 1, 2, 3, 4, 5).
  • Important Convention: There is no specific required order for numbering nodes; labels can be assigned arbitrarily.
• Edges: The connecting lines between nodes representing relationships or pathways.
• Structural Flexibility: A graph does not have to be a closed circular shape. It can be open, branching, or even resemble a binary tree (since trees satisfy all minimal graph conditions: nodes connected by edges).

3. Types of Graphs: Undirected vs. Directed

Graphs are primarily categorized based on whether their edges have directional constraints.

Note: In a directed graph, you can have multiple directed edges between the same two nodes (e.g., $1 \to 4$ and $4 \to 1$ simultaneously), creating a bi-directional corridor using directed edges.

4. Cycles in Graphs: Cyclic vs. Acyclic

Understanding whether a graph contains loops (cycles) is crucial for traversal algorithms (like DFS/BFS) and topological sorting.

• Cycle Definition: A cycle occurs when you start at a specific node, traverse a sequence of valid edges through other nodes, and reach back to that exact same starting node.
• Undirected Cyclic Graph: An undirected graph containing at least one closed loop.
• Directed Acyclic Graph (DAG): A directed graph that contains no cycles. DAGs are heavily used in dependency scheduling and compilation tasks (and will appear frequently in upcoming lectures).

5. Paths in a Graph

A path is a sequence of vertices where each adjacent pair in the sequence is connected by a valid edge.

Critical Path Rules & Pitfalls:

1. No Duplicate Nodes: A node cannot appear twice in a single valid path. (e.g., 1 -> 2 -> 3 -> 2 -> 1 is invalid because node 2 repeats).
2. Valid Edge Connectivity: Adjacent nodes in a path definition must have a direct edge connecting them. (e.g., writing 1 -> 3 -> 5 is invalid if no edge exists directly between 1 and 3).

6. Degrees in Undirected Graphs

The degree of a node in an undirected graph is defined as the total number of edges attached to that node.

The Handshaking Lemma (Total Degree Property)

Mathematical Property: The sum of the degrees of all vertices in an undirected graph is always equal to twice the number of edges ($2E$).

• Why? Because every single edge connects exactly two nodes, contributing to the degree count of both endpoints.
• Example Verification: If a graph has 6 edges, the sum of all node degrees across the graph will always equal $12$.

7. In-Degree and Out-Degree in Directed Graphs

Because directed edges have specific orientations, degrees are split into two distinct metrics:

• In-Degree: The total number of incoming edges entering a node (edges pointing towards the node).
• Out-Degree: The total number of outgoing edges leaving a node (edges pointing away from the node).

In the diagram above, Node 3 has an In-Degree of 2 and an Out-Degree of 1.

8. Edge Weights and Conventions

Not all edges are created equal. In real-world routing (like Google Maps or network latency), edges carry costs or distances.

• Edge Weight: A numerical value assigned to an edge representing cost, distance, capacity, or time (e.g., weight = 3, 5, 7).
• Unweighted Graph Convention: If a problem statement or graph diagram does not explicitly assign weights to edges, algorithms always assume unit weight ($1$) for every edge by default.

Summary and Key Takeaways

• Graphs vs. Trees: Graphs generalize trees by allowing arbitrary many-to-many relationships without requiring a root or strict hierarchy.
• Nodes & Vertices ($V$ / $N$): Fundamental entities labeled in any arbitrary order.
• Undirected Edges: Provide bi-directional travel between connected nodes ($u \leftrightarrow v$).
• Directed Edges: Restrict travel strictly to the arrow's orientation ($u \to v$), though dual arrows can simulate bi-directionality.
• Cycles: A closed loop starting and ending at the same node via valid paths; directed acyclic graphs are known as DAGs.
• Path Integrity: Valid paths require direct edge connectivity between adjacent steps and prohibit node repetition.
• Undirected Degree: Total connected edges; the sum of all node degrees in an undirected graph is always twice the number of edges ($2E$).
• Directed Degree: Separated into In-Degree (incoming arrows) and Out-Degree (outgoing arrows).
• Edge Weights: Custom numerical costs assigned to edges; defaults to a unit weight of 1 when unspecified.