# Graph Introduction

A Graph is a non linear data structure. It is often viewed as a generalization of the tree structure. It contains two main components **vertices (nodes)** and **edges**. Two nodes are connected via an edge. The graph is used to represent many computer applications, like - a computer network, in which nodes are network workstations and the edges are the network connections.

## Formal Definition of Graph

A graph **G** is defined as an ordered set **(V, E)**, where **V(G)** represents the set of nodes or vertices and **E(G)** represents the edges that connect these nodes.

## Types of Graph

There are two types of Graphs -

### Directed Graph

In a directed graph, there is a path between nodes. So, edges form an ordered pair. Suppose, there are two nodes A and B and there is an edge from A to B. Then the only possible path from A to B, but not from B to A.

A directed graph **G** is a graph in which an edge is given as an ordered pair **(u,v)** of nodes in **G**. So for the edge (u,v) -

- The edge starts at u and terminates at v.
- u is the initial point and v is the destination point.
- both nodes u and v are adjacent to each other.

### Undirected Graph

In an undirected graph, there is no any directed edges between nodes. Suppose, there is an edge between node A to B, then we can easily traverse from A to B and from B to A.

## Graph Terminology

These are the graph terminologies -

**Adjacent Nodes** - The edge E that connects nodes u and v, so the nodes u and v are adjacent to each other.

**Degree of a node** - The degree of a node is defined as the total number of edges connecting to the node.

**Regular graph** - If each vertex of a graph has the same number of neighbours, i.e., every node has the same degree, that is called regular graph.

**Cycle** - A path has the same first and last vertices are called cycle.

**Connected Graph** - A graph is said to be connected, for any two vertices (u,v) there is a path from u to v.

**Complete Graph** - A graph is said to be complete, if all its nodes are fully connected.

**Weighted Graph** - A graph is said to be weighted or labelled, if every edge in a graph is assigned some data. If e denotes the edge of a graph, then w(e) denotes the weight of a graph.

**Multiple Edges** - Distinct edges which connect the same end-points are called multiple edges.

**Loop** - An edge with identical end points is called a loop, i.e, e(u,u).

**Multi-graph** - A graph with multiple edges or loops is called a multi-graph.

**Size of a graph** - The total number of edges in a graph is the size of a graph.