5.1 Introduction of graph

A graph is a mathematical structure used to model pairwise relationships between objects. It is widely used in various fields such as computer science, biology, and sociology to represent networks, paths, and connections.

Definition of a Graph

A graph $G$ consists of two main components:

1. Vertices (Nodes): The objects or points in the graph. A vertex represents an entity, such as a city, computer, or person.
2. Edges (Links): The connections between the vertices. An edge represents a relationship, such as a road between cities or a friendship between people.

Formally, a graph is written as $G=(V,E)$, where:

• $V$ is the set of vertices (also called nodes).
• $E$ is the set of edges, which are pairs of vertices that indicate connections.

Types of Graphs

1. Undirected Graph: In an undirected graph, edges have no direction. The edge between two vertices $A$ and $B$ is the same as the edge between $B$ and $A$. For example, a friendship relationship is typically modeled as undirected because if A is friends with B, then B is also friends with A.

   Example:

   $$G=(V,E)\text{where}V=\{A,B,C\},E=\{(A,B),(B,C)\}$$

2. Directed Graph (Digraph): In a directed graph, each edge has a direction, meaning the relationship goes one way. An edge from $A$ to $B$ is different from an edge from $B$ to $A$. This is commonly used to represent processes like road directions or web page links.

   Example:

   $$G=(V,E)\text{where}V=\{A,B,C\},E=\{(A\to B),(B\to C)\}$$

3. Weighted Graph: A weighted graph is a graph in which each edge has an associated weight (or cost). This is used to represent networks where the connections have a value, such as distances between cities or the cost of a flight.
4. Complete Graph: A complete graph is a graph where there is an edge between every pair of vertices. If there are $n$ vertices in a complete graph, there will be n(n−1)2\frac{n(n-1)}{2}2n(n−1)​ edges.
5. Bipartite Graph: A bipartite graph is a graph whose vertices can be divided into two disjoint sets, such that every edge connects a vertex in one set to a vertex in the other set. It is often used to model relationships between two types of entities, such as jobs and applicants.

Applications of Graphs

1. Computer Networks: Graphs are used to represent networks of computers and their connections. Routers and data paths are modeled using graph structures.
2. Social Networks: In platforms like Facebook or LinkedIn, individuals are represented as vertices, and their friendships or connections are represented as edges.
3. Pathfinding: In transportation, maps are modeled as graphs where cities are vertices, and roads are edges. Algorithms like Dijkstra’s are used to find the shortest path between two cities.
4. Web Structure: The internet can be modeled as a graph where websites are vertices, and hyperlinks between them are edges. Search engines use graph algorithms to rank web pages.
5. Biology: Graphs are used to model biological networks, such as gene regulatory networks or protein-protein interaction networks.

Graph Terminology

• Adjacent Vertices: Two vertices are adjacent if there is an edge connecting them.
• Degree: The degree of a vertex is the number of edges connected to it. In a directed graph, a vertex has an in-degree (edges coming into the vertex) and an out-degree (edges going out of the vertex).
• Path: A path is a sequence of edges that connects a sequence of vertices.
• Cycle: A cycle is a path that starts and ends at the same vertex, with no repeated edges or vertices in between.
• Connected Graph: A graph is connected if there is a path between every pair of vertices.

5.2 Different types of Graphs

Graphs can be classified into various types based on the properties of their vertices and edges. These types are useful in different applications, from social networks to pathfinding algorithms.

1. Undirected Graph

An undirected graph is a graph where edges do not have any direction. The edge between two vertices $A$ and $B$ means there is a connection in both directions, making $A$ and $B$ mutually adjacent.

• Example: A graph representing friendships in a social network, where if person A is friends with person B, then person B is also friends with person A.
• Notation: $G=(V,E)$ where $E$ contains unordered pairs of vertices, like $(A,B)$.

2. Directed Graph (Digraph)

A directed graph is a graph where the edges have directions. An edge from $A$ to $B$ is represented as $A\to B$, meaning the relationship is one-way.

• Example: A graph representing the links between web pages, where $A\to B$ indicates that page A links to page B.
• Notation: $G=(V,E)$, where $E$ contains ordered pairs, like $(A\to B)$.

3. Weighted Graph

A weighted graph is a graph where each edge has an associated weight (or cost), which could represent distance, time, or any other quantitative measure.

• Example: A graph representing cities connected by roads, where the weight on each edge indicates the distance or cost of travel between the cities.
• Notation: $G=(V,E,w)$, where $w(e)$ gives the weight of each edge $e\in E$.

4. Complete Graph

A complete graph is a graph in which every pair of distinct vertices is connected by an edge. In a complete graph with $n$ vertices, there are n(n−1)2\frac{n(n-1)}{2}2n(n−1)​ edges.

• Example: A fully connected social network where each person knows every other person.
• Notation: KnK_nKn​, where $n$ is the number of vertices. For example, K4K_4K4​ is a complete graph with 4 vertices.

5. Bipartite Graph

A bipartite graph is a graph where the set of vertices can be divided into two disjoint sets $U$ and $V$, and every edge connects a vertex in $U$ to a vertex in $V$. No edge exists between vertices within the same set.

• Example: A job assignment problem where $U$ represents workers and $V$ represents jobs, and edges represent which worker can perform which job.
• Notation: $G=(U,V,E)$, where $U\cup V=V$.

6. Cyclic and Acyclic Graphs

• Cyclic Graph: A graph that contains at least one cycle, meaning there is a path that starts and ends at the same vertex.
  • Example: A road system where one can return to the starting point after visiting other points.
• Acyclic Graph: A graph that contains no cycles. If the graph is directed, it’s called a Directed Acyclic Graph (DAG).
  • Example: A task scheduling system where tasks must be completed in a specific order, and no task can depend on itself indirectly.

7. Connected and Disconnected Graphs

• Connected Graph: A graph is connected if there is a path between every pair of vertices. In other words, all vertices are reachable from any other vertex.
  • Example: A graph representing a computer network where all computers are directly or indirectly connected.
• Disconnected Graph: A graph in which at least one pair of vertices is not connected by a path. The graph is divided into two or more separate components.

8. Planar Graph

A planar graph is a graph that can be drawn on a plane without any of the edges crossing. In such a graph, edges only intersect at vertices.

• Example: A map of cities connected by roads, where no two roads intersect unless they meet at a city.
• Notation: A graph is planar if it can be drawn in the plane such that no edges cross.

9. Sparse and Dense Graphs

• Sparse Graph: A graph with relatively few edges compared to the number of vertices. A graph is sparse if $|E|\approx O(|V|)$.
  • Example: A graph representing friendships in a large community where only a few people know each other.
• Dense Graph: A graph with a large number of edges, close to the maximum number of possible edges. A graph is dense if ∣E∣≈O(∣V∣2)|E| \approx O(|V|^2)∣E∣≈O(∣V∣2).
  • Example: A fully connected network of computers where each computer is connected to every other computer.

10. Tree

A tree is a special type of graph that is connected and acyclic. In a tree with $n$ vertices, there are exactly $n-1$ edges.

• Example: A family tree or a file directory structure, where each node (person or file) is connected by one path.
• Notation: A tree is often denoted as $T=(V,E)$, where the graph is connected and acyclic.

11. Multigraph

A multigraph is a graph that allows multiple edges between two vertices. It also allows for loops, where an edge connects a vertex to itself.

• Example: A transportation network where multiple routes exist between two cities.
• Notation: A multigraph is denoted as $G=(V,E)$, but $E$ may contain multiple edges between any pair of vertices.

12. Subgraph

A subgraph is a graph formed from a subset of the vertices and edges of another graph.

• Example: Taking a part of a larger network, such as a neighborhood within a city network.
• Notation: If $G=(V,E)$ is a graph, then a subgraph H=(V′,E′)H = (V’, E’)H=(V′,E′) where V′⊆VV’ \subseteq VV′⊆V and E′⊆EE’ \subseteq EE′⊆E.

5.3 Vertex and edges of graphs

A graph is a collection of two sets: vertices (also called nodes) and edges (also called links or arcs). These fundamental components define the structure and relationships in the graph.

1. Vertices (Nodes)

A vertex (plural: vertices) represents an entity or object in the graph. It can represent different real-world elements depending on the context, such as people in a social network, cities in a transportation map, or computers in a network.

• Notation: Vertices are typically denoted by $V$, and individual vertices are denoted by capital letters like $A,B,C$.
• Set of Vertices: The set of all vertices in a graph $G$ is denoted by $V(G)$.

  For example, in a graph $G=(V,E)$ with vertices $A,B,C$, we write:

  $$V(G)=\{A,B,C\}$$

• Vertex Degree:
  • The degree of a vertex is the number of edges connected to it. In an undirected graph, the degree is simply the count of edges incident to the vertex.
  • In a directed graph, a vertex has:
    • In-degree: The number of edges coming into the vertex.
    • Out-degree: The number of edges going out from the vertex.

2. Edges (Links)

An edge is a connection between two vertices in a graph. Edges define the relationships or interactions between the entities (vertices).

• Notation: Edges are typically denoted by $E$, and individual edges are denoted as pairs of vertices like $(A,B)$, which represents an edge connecting vertex $A$ to vertex $B$.
• Set of Edges: The set of all edges in a graph $G$ is denoted by $E(G)$.

  For example, in a graph $G=(V,E)$ with edges connecting vertices $A$ to $B$ and $B$ to $C$, we write:

  $$E(G)=\{(A,B),(B,C)\}$$

• Types of Edges:
  1. Undirected Edge: In an undirected graph, edges do not have direction. $(A,B)$ is the same as $(B,A)$.
  2. Directed Edge (Arc): In a directed graph (digraph), each edge has a direction. $(A\to B)$ means the edge goes from $A$ to $B$, but not necessarily from $B$ to $A$.
  3. Weighted Edge: In some graphs, edges have associated weights or costs, such as distances between cities or the cost of sending data between computers.
  4. Self-loop: An edge that connects a vertex to itself. This occurs in a graph where an entity has a relationship with itself.

3. Properties of Vertices and Edges

• Adjacency:
  • Two vertices are said to be adjacent if there is an edge connecting them.
  • In a directed graph, vertex $A$ is adjacent to vertex $B$ if there is an edge from $A$ to $B$.
• Incident:
  • An edge is incident on a vertex if the vertex is one of the endpoints of the edge.
  • For a directed edge $(A\to B)$, vertex $A$ is the starting point (source), and vertex $B$ is the endpoint (destination).
• Path: A path is a sequence of edges connecting a sequence of distinct vertices. The number of edges in the path is its length.
• Cycle: A cycle is a path that starts and ends at the same vertex, with no repeated edges or vertices except the starting/ending point.

4. Vertex and Edge in Different Types of Graphs

1. Undirected Graph:
   • Vertices are connected by edges without any direction.
   • If $(A,B)\in E(G)$, then $A$ is adjacent to $B$, and $B$ is adjacent to $A$.
2. Directed Graph (Digraph):
   • Vertices are connected by directed edges (arcs).
   • If $(A\to B)\in E(G)$, $A$ is the source, and $B$ is the destination.
3. Weighted Graph:
   • Vertices are connected by edges with weights (costs or distances).
   • The edge $(A,B)$ may have a weight, like $w(A,B)$, which indicates the strength or cost of the connection between vertices.
4. Multigraph:
   • A multigraph allows multiple edges between the same pair of vertices.
   • Vertices can be connected by several edges, potentially representing different types of connections.
5. Bipartite Graph:
   • Vertices are divided into two disjoint sets, $U$ and $V$, and edges connect vertices from $U$ to vertices in $V$, but not within the same set.

Examples:

1. Simple Graph Example:
   • Vertices: $A,B,C$
   • Edges: $(A,B),(B,C),(C,A)$

   The degree of each vertex is 2.

2. Directed Graph Example:
   • Vertices: $A,B,C$
   • Edges: $(A\to B),(B\to C),(C\to A)$

   The in-degree and out-degree of each vertex is 1.

3. Weighted Graph Example:
   • Vertices: $A,B,C$
   • Edges: $(A,B)$ with weight 5, $(B,C)$ with weight 3.

   The weights represent the cost or distance between connected vertices.

5.4 Walks, paths and cycles of Graphs

In graph theory, the concepts of walks, paths, and cycles are essential for understanding how vertices are connected through edges. These terms describe various ways of traversing a graph and are foundational in many applications, such as navigation, network analysis, and algorithm design.

1. Walks

A walk is a sequence of vertices and edges, where each edge is incident to the vertices immediately before and after it in the sequence. Walks are the most general form of traversal in a graph, with no restrictions on revisiting vertices or edges.

• Definition: A walk from vertex v1v_1v1​ to vkv_kvk​ is a sequence of vertices v1,v2,…,vkv_1, v_2, \dots, v_kv1​,v2​,…,vk​ such that for each $i$, there is an edge (vi,vi+1)(v_i, v_{i+1})(vi​,vi+1​) in the graph.
• Types of Walks:
  1. Closed Walk: A walk that starts and ends at the same vertex. That is, v1=vkv_1 = v_kv1​=vk​.
  2. Open Walk: A walk that starts and ends at different vertices. That is, v1≠vkv_1 \neq v_kv1​=vk​.
• Examples:
  • A walk in an undirected graph could be $A\to B\to C\to A\to D$.
  • In a directed graph, a valid walk could be $A\to B\to C\to D$, where each edge follows the direction.

2. Paths

A path is a walk in which all the vertices (and thus the edges) are distinct, meaning no vertex or edge is revisited during the traversal. Paths represent the most efficient way to traverse from one vertex to another without repeating any vertices.

• Definition: A path from vertex v1v_1v1​ to vertex vkv_kvk​ is a walk in which all vertices are distinct, i.e., vi≠vjv_i \neq v_jvi​=vj​ for i≠ji \neq ji=j.
• Types of Paths:
  1. Simple Path: A path in which no vertex is repeated (except possibly the start and end vertices if it forms a cycle).
  2. Directed Path: In a directed graph, a path must follow the direction of the edges.
• Length of a Path: The length of a path is the number of edges in the path. If the path consists of the vertices v1,v2,…,vkv_1, v_2, \dots, v_kv1​,v2​,…,vk​, the length of the path is $k-1$.
• Example:
  • A simple path in an undirected graph: $A\to B\to C\to D$.
  • A directed path in a directed graph: $A\to B\to D\to E$.

3. Cycles

A cycle is a path that starts and ends at the same vertex, with no other vertices repeated along the way. Cycles are important for detecting feedback loops, dependencies, and repetitions in graphs.

• Definition: A cycle is a path v1,v2,…,vkv_1, v_2, \dots, v_kv1​,v2​,…,vk​ where v1=vkv_1 = v_kv1​=vk​ and all other vertices are distinct, i.e., vi≠vjv_i \neq v_jvi​=vj​ for $1\le i<j<k$.
• Types of Cycles:
  1. Simple Cycle: A cycle that does not repeat any vertices except the starting and ending vertex.
  2. Directed Cycle: In a directed graph, a cycle must follow the direction of the edges.
• Examples:
  • A simple cycle in an undirected graph: $A\to B\to C\to A$.
  • A directed cycle in a directed graph: $A\to B\to C\to A$.
• Special Types of Cycles:
  • Hamiltonian Cycle: A cycle that visits every vertex of the graph exactly once (except the starting/ending vertex).
  • Eulerian Cycle: A cycle that visits every edge of the graph exactly once.

4. Walks, Paths, and Cycles in Different Types of Graphs

1. Undirected Graphs:
   • Walks, paths, and cycles do not have to follow any direction since the edges are bidirectional.
   • Example of a path: $A\to B\to C$.
   • Example of a cycle: $A\to B\to C\to A$.
2. Directed Graphs:
   • Walks, paths, and cycles must follow the direction of the edges.
   • Example of a directed path: $A\to B\to C\to D$.
   • Example of a directed cycle: $A\to B\to C\to A$.
3. Weighted Graphs:
   • Walks, paths, and cycles may have associated costs or distances based on the weights of the edges. In shortest path problems, the goal is often to find the path with the minimum total weight.
   • Example of a path: $A\to B\to C$, where each edge has a specific weight (distance or cost).
4. Disconnected Graphs:
   • A disconnected graph has multiple components, and walks, paths, and cycles can only exist within a connected component.

5. Key Properties of Walks, Paths, and Cycles

• Path Existence: A graph is connected if there is a path between every pair of vertices.
• Cycle Detection: Detecting cycles in a graph is important in many algorithms, such as detecting deadlocks in operating systems or feedback loops in networks.
• Shortest Path: The shortest path is the path between two vertices that minimizes the total number of edges (or total weight in a weighted graph).
• Acyclic Graph: A graph that contains no cycles is called an acyclic graph. If a directed graph contains no cycles, it is called a Directed Acyclic Graph (DAG).

Examples of Applications:

1. Navigation Systems: Finding the shortest path between two locations (vertices) in a map (graph).
2. Computer Networks: Identifying the most efficient route for data packets to travel between devices.
3. Social Networks: Analyzing connections and friendships through walks and paths.
4. Task Scheduling: In Directed Acyclic Graphs (DAGs), cycles represent feedback loops, and breaking them is important for proper scheduling.

5.5 Eulerian and Hamiltonian graphs concept and examples only

1. Eulerian Graphs

An Eulerian graph is a graph where there exists an Eulerian circuit—a closed walk that visits every edge of the graph exactly once, starting and ending at the same vertex.

• Eulerian Circuit: A cycle that traverses each edge of the graph exactly once.
• Eulerian Path: A path that traverses each edge exactly once but does not necessarily end at the starting vertex.
• Conditions for Eulerian Graph:
  • For Eulerian Circuit (in an undirected graph), all vertices must have an even degree.
  • For Eulerian Path (in an undirected graph), exactly two vertices must have odd degrees.
• Example:
  • Eulerian Circuit: A square where every edge is traversed once, starting and ending at the same vertex.
  • Eulerian Path: A graph shaped like a “T” where each edge is visited exactly once, but the starting and ending points are different.

2. Hamiltonian Graphs

A Hamiltonian graph is a graph that contains a Hamiltonian cycle—a cycle that visits every vertex exactly once, starting and ending at the same vertex.

• Hamiltonian Cycle: A cycle that visits each vertex of the graph exactly once and returns to the starting vertex.
• Hamiltonian Path: A path that visits each vertex exactly once but does not necessarily end at the starting vertex.
• Conditions for Hamiltonian Graph:
  • There is no simple degree-based rule like in Eulerian graphs, but Dirac’s and Ore’s theorems provide sufficient conditions for Hamiltonian cycles in specific cases.
• Example:
  • Hamiltonian Cycle: A pentagon where each vertex is visited once, and the path forms a closed loop.
  • Hamiltonian Path: A straight line of connected vertices where each vertex is visited once without forming a cycle.

5.6 Trees and Forest concept with examples.