Introduction to Graph Theory

# CHAPTER 18

Introduction to Graph Theory #

1. Introduction #

2. Learning Objectives #

• Define the two foundational components of a Graph (Vertices and Edges).

• Differentiate between Directed and Undirected graphs.

• Understand the impact of Edge Weights.

• Identify the concept of Cycles and Connected Components.

3. The Core Components #

1. 1. Vertices (Nodes - $V$): The entities holding the data. (e.g., A City on a map, a User on Facebook).

1. 2. Edges ($E$): The physical lines/links connecting the Vertices. (e.g., A highway between cities, a friendship between users).

Visual Example:

  (A)-------(B)
   |       / |
   |     /   |
   |   /     |
  (C)-------(D)

*In this graph, there are 4 Vertices ($A, B, C, D$) and 5 Edges.* *Notice the loop ($A \rightarrow B \rightarrow C \rightarrow A$). This is a Cycle. Cycles are illegal in Trees, but totally normal in Graphs!*

4. Undirected vs. Directed Graphs #

1. Undirected Graph:

• The edge is a two-way street. If Vertex A connects to Vertex B, then Vertex B inherently connects back to Vertex A.

• *Real-world Analogy:* Facebook. If I am your friend, you are automatically my friend.

2. Directed Graph (Digraph):

• The edge has an Arrow ($A \rightarrow B$). It is a one-way street. You can travel from A to B, but NOT from B to A (unless a second reverse arrow exists).

• *Real-world Analogy:* Twitter/X. I can follow Elon Musk ($Me \rightarrow Elon$), but that does not mean Elon Musk follows me back.

5. Unweighted vs. Weighted Graphs #

1. Unweighted Graph:

• Every edge is treated equally. The "cost" to travel any edge is simply $1$.

• *Real-world Analogy:* Counting degrees of separation. "How many friends between me and Kevin Bacon?"

2. Weighted Graph:

• Every edge is assigned a numerical "Weight" (or Cost).

• *Real-world Analogy:* Google Maps. The edge connecting City A to City B might have a weight of 50 (representing 50 miles, or 50 minutes of traffic). The algorithms must now calculate paths not just by the fewest edges, but by the smallest total sum of edge weights.

6. Sub-Terminology #

• Degree of a Vertex: The number of edges connected to it. (In a Directed Graph, it is split into *In-Degree* and *Out-Degree*).

• Path: A sequence of alternating vertices and edges that gets you from a start point to an end point.

• Connected Graph: A graph where there is a valid path to reach every single node. There are no isolated "island" nodes.

7. Why Graph Theory Matters #

• Google Search: The "PageRank" algorithm treats every website as a Vertex and every hyperlink as a Directed Edge.

• Amazon Logistics: Finding the cheapest delivery route using Weighted Graphs.

• Flight Networks: Calculating overlapping layovers.

• Neural Networks: The nodes in an AI brain are vertices; the synaptic connections are weighted edges.

8. Complexity Analysis Constraints #

9. Common Mistakes #

• Assuming all graphs are fully connected: When writing an algorithm to search a social network graph, a major mistake is assuming you can reach User Z by starting at User A. What if User Z has absolutely zero friends? They are an isolated vertex floating in memory. Your algorithm MUST account for disconnected components!

10. Exercises #

1. 1. Draw a visual Directed Graph representing the food chain: Grass, Rabbit, Fox, Hawk. Use arrows to show the flow of energy.

1. 2. If an Undirected Graph has 5 Vertices, and every vertex is connected to every other vertex (a Complete Graph), mathematically calculate exactly how many Edges exist. *(Hint: Combinatorics $\frac{N(N-1)}{2}$)*.

11. MCQs with Answers #

12. Interview Preparation #

• *Data Modeling:* "How would you model the backend system for tracking 'Mutual Friends' on a social network?" *(Answer: Model it as an Undirected, Unweighted Graph. Execute an immediate Set Intersection algorithm between the connected Adjacency lists of Vertex A and Vertex B!)*

13. Summary #

14. Next Chapter Recommendation #