Introduction to Graphs and Definitions

 

Introduction to Graphs

In our daily life, we often deal with objects and the relationships between them.

For example:

• Cities and Roads: Each city is a point, and the road connecting two cities is a link.

• Social Networks: Each person is a point, and friendship or a “follow” is a link.

• Computer Networks / Internet: Each computer is a point, and the cable or wireless connection is a link.

• Electric Circuits: Each junction is a point, and wires are the links.

All of these situations can be modeled using a Graph.

---

What is a Graph?

A graph is a way to represent objects and the connections between them.

• The objects are called vertices (or nodes).

• The connections are called edges (or links).

👉 Example:

If we have 4 cities {A, B, C, D} and roads between them:

• A ↔ B, B ↔ C, A ↔ D
  This can be drawn as a graph diagram where cities are circles and roads are lines connecting them.

---

Why Graphs?

Graphs help us to:

• Visualize relationships between entities.

• Model real-world problems like shortest path (Google Maps), friend recommendations (Facebook), or data routing (Internet).

• Provide the foundation for important algorithms (DFS, BFS, Dijkstra’s, etc.).

Basic Definitions

Introduce formal terminology step by step:

1. Graph (G):
   A graph is defined as an ordered pair:

   $$G = (V, E)$$

   where:

   • $V$ = set of vertices (or nodes)

   • $E$ = set of edges (connections between vertices)

2. Vertices (Nodes): Elements of the set $V$. Example: cities, people, computers.

3. Edges (Links): Pairs of vertices. Example: a road between cities.

   • Undirected edge: $(u, v)$means connection between $u$ and $v$, no direction.

   • Directed edge (Arc): $⟨u,v⟩\; means\; edge\; is\; from$$u$ to $v$.

4. Types of Graphs:

   • Undirected Graph: Edges have no direction.

   • Directed Graph (Digraph): Edges have direction.

   • Weighted Graph: Edges carry weights (cost, distance, time).

   • Unweighted Graph: Edges carry no weights.

5. Special Terms:

   • Degree of a vertex (deg(v)): Number of edges incident on vertex $v$.

     • In directed graphs → in-degree and out-degree.

   • Path: Sequence of vertices connected by edges.

   • Cycle: Path where the first and last vertices are the same.

   • Connected Graph: Every vertex is reachable from every other.

   • Complete Graph (K$_n$): Every vertex connected to every other vertex.

   • Sparse vs Dense Graphs: Few edges vs many edges.