Introduction to Graph

gistfile1.txt

# Introduction to Graph

A **graph** \( G \) is a mathematical structure consisting of a set of vertices (also called nodes) \( V \) and a set of edges \( E \), where each edge is a pair of vertices. Formally, a graph can be denoted as \( G = (V, E) \).

## Directed/Undirected Graphs

A **directed graph** (or digraph) \( G \) is a graph in which the edges have a direction associated with them. Each edge \( (u, v) \) in a directed graph goes from vertex \( u \) to vertex \( v \). In contrast

**undirected graph** is a graph in which the edges have no direction associated with them; they simply indicate a connection between two vertices.

## Weighted/Unweighted Graphs

A **weighted graph** is a graph in which each edge is assigned a numerical value, called a weight. These weights can represent various measures such as distance, cost, or any other relevant quantity.
**unweighted graph** is a graph in which all edges have the same implicit weight, often considered as 1.

## Indegrees/Outdegrees

In a **directed graph**, the **indegree** of a vertex is the number of edges entering the vertex
the **outdegree** is the number of edges leaving the vertex.

## Walk (aka. Path) / Path (aka. Simple Path)

A **walk** in a graph \( G \) is a sequence of vertices \( v_1, v_2, ..., v_n \) such that there exists an edge between each consecutive pair of vertices in the sequence.
A **path** is a walk in which all vertices in the sequence are distinct, except possibly the first and last vertices. A **simple path** is a path in which all vertices (except possibly the first and last) are distinct.

## Cyclic/Acyclic

A **cycle** in a graph \( G \) is a non-empty path in which the first and last vertices are the same, meaning there is a sequence of edges that starts and ends at the same vertex.

If a graph contains at least one cycle, it is called **cyclic**; otherwise, it is **acyclic**.