Handbook of Computer Science(cs) and IT

Graph

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

1. A set of vertices V.
2. 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 ₀,v ₁, v₂,…,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 nodeu 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 Twithout any cycles is known as tree graph or free tree orsimply 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 edgee inG 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 pont and end

point i.e., if e = [u4.1]

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].

• is predecessor of v and v is a successor of u or neighbour of
• is adjacent to v and v is adjacent to
• 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 indegrea
• A nodeu 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₁,v₂,…,v_m.

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

1 if v_i is adjacent to v_i, i.e., if there is an ege (v₁, v₁)

a_{i j}   =                                      Otherwise

0

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.