# Graph in C Language Tutorial Notes Study Material with Examples

## Graph

A graph is a set of vertices and edges which connects them. *A graph G* consists of two things

- A set of vertices V.
- A set of edges
*E*such that edge e in*E*is identified with a unique pair*u, v*of vertices in*V,*denoted bye =*{u, v}*

**Path:**A path*P*of length*n*from a node*u*to a node v is defined as a sequence of*(n +*1) nodes.

**P = (v _{0}, v _{1}, v_{2 },…, v _{n})**

**Adjacent Nodes or Neighbours:**Suppose e*[u, vi*then the nodes*u*and v are called the endpoints of e and*u*and v are said to be adjacent nodes or neighbours.**Degree of a Node:**The number of edges containing*u,*is the degree of a node deg*(u).*If deg(u) = 0, this means*u*doesn’t belong to any edge, then*u***is called as**isolated node.**Connected Graph:**A graph G is said to be connected, if there is a path**between any**two of its nodes.**Complete Graph:**A graph G is said to be complete, if**every node u in G**is adjacent to every other node v in**{Number of edges**with*n*nodes in a complete graph G

** =***n* (n —1)/2

**Tree Graph or****Free Tree/Tree**A connected graph**T**without any cycles is known as tree graph or free tree or simply a tree.

If T is a finite tree with *k *nodes, then T will have *(k —1)* edges.

**Labelled and Weighted Graph **

**A graph G **is said to be labelled, if its edges are assigned data.** G **is said to be weighted, if each edge in G is assigned a non-negative numerical value. w (e) = Weight or length of edge e

**Multigraph: **If a graph is having multiple edges and/or loops, then it will be called a **multigraph.**

**Multiple Edges: **Distinct edges e and e’ are called **multiple edges, **if they connect the same endpoints *i.e., *if e *[u, *v] and e’ *[u, *v].

**Loops: **An edge e is called a **loop, **if it has identical stmt point and end. point *i.e., *if e = [u, **µ**].

**Directed Graph **(Digraph)

Each edge in graph G is assigned a direction or each edge e is identified with an ordered pair *(u, *v) of nodes G rather than an unordered pair *[u, *v].

u is predecessor of v and v is a successor of *u *or neighbour of

u is adjacent to v and v is adjacent to u.

- Outdegree of a node
*u*in G

outdeg *(u) *= Number of edges beginning at *u*

- Indegree of a node
*u*in G –

indeg*(u) *= Number of edges ending at *u*

- A node
*u*is called source, if it has positive outdegree but zero indegree - A node u is called sink, if it has a zero outdegree but a positive
*indegree*

* *

**indeg(c) = 2; outdeg (c) = 0**

**So, C is a sink and there is no source node of this graph.**

**Adjacency Matrix**

suppose G is a simple directed graph with m nodes and suppose the nodes of G have been ordered are called v_{1},v_{2},…,v_{m}.

Then adjacency matrix (A) = (aij ) of the graph G is the m x m matrix defined as follows

Such a matrix which contains entries of on by 0 and 1, is called a bit matrix or a Boolean Matrix.

The adjacency matrix A of the graph G does depend on the ordering of the nodes of G; i.e a different ordering of the nodes may results in a different adjacency matrix.

# Importance of Turing Machine Tutorial Notes Study Material with Examples

Follow Us on Social Platforms to get Updated : **twiter, ****facebook, Google Plus**

Learn Turing Machine in Handbook Series: **Click here **