Matrix representation of Graph, Edge Sequence, Walk, Path and Circuit

 Matrix Representation of Graphs

When G is a simple graph with n vertices V1,V2,V3…Vn the matrix A (or AG)=Aij.

Where,Aij is called the adjacency matrix of G.

Properties of an Adjacency Matrix

  • Since a simple graph has no loops, each diagonal entry of A, viz., Aij=0, for i=1,2,…n.
  • The adjacency matrix of simple graph is symmetric, viz. Aij= Aji, since both of these entries are 1 when vi, vj are adjacent and both are 0 otherwise.
  • Note: The given any symmetric zero-one matrix A which contains only 0’s on its diagonal there exists a simple graph G whose adjacency matrix is A.
  • deg(vi) is equal to the number of 1’s in the ith row and ith column.

Examples

1.Adjacency Matrix of a Simple Graph

2.Adjacency Matrix of a Weighted Graph

3.Adjacency Matrix of a Directed Graph

EDGE SEQUENCE, WALKS, PATHS AND CIRCUITS

Edge Sequence

An edge is the mathematical term for a line that connects two vertices.

Many edges can be formed from a single vertex.

Without a vertex, an edge cannot be formed.

There must be a starting vertex and an ending vertex for an edge.


Here, ‘a’ and ‘b’ are the two vertices and the link between them is called an edge.

Example

1. Edge Sequence for Undirected Graph



In this graph,

There are six vertices (A, B, C, D, E, F)

Edges or edge sequences are (A,B), (B,C), (C,D), (D,E), (E,F) and (F,A)

2. Edge Sequence for Directed Graph

 

In this graph,

There are four vertices (A, B, C, D)

Edges or edge sequences are (A,C), (B,A), (B,D) and (D,C)

Walks

A walk is a sequence of vertices and edges of a graph that is if we traverse a graph then we get a walk.

Vertex can be repeated

Edges can be repeated

Walk can be open or closed

Here, B→C→D→E→F→G→H→C→D→A is Walk

The edge (C,D) is repeated

The vertices C, D is repeated

 

Trail

Trail is a walk in which no edge is repeated.

Vertex can be repeated.

Trail can be open or closed.

From the above graph,

A→D→E→F→G→H→C→B is Open Trail

B→C→D→E→F→G→H→C→B is Closed Trail

 

Path 

  • Path is a trail in which neither vertices nor edges are repeated.

  • Vertex not repeated.

  • Edges not repeated.

  • Path can be open.

  • From the above graph,

A→B→C→D→E→F→G→H  is a path

 

Circuit

  • Traversing a graph such that not an edge is repeated but vertex can be repeated and it is closed.

  • Vertex can be repeated.

  • Edges cannot be repeated.

  • Circuit can be closed.

A→B→C→D→E→H→G→F→A  is a circuit

Degree Sequence of a Graph

  • The degree of a vertex in an undirected graph is the number of edges incident with it.

  • If the degrees of all vertices in a graph are arranged in ascending or descending order, then the sequence obtained is known as the degree sequence of the graph.

Example


Vertex

A

B

C

D

E

F

G

H

Connecting to

B,D,F

A,C

B,D,H

A,C,E

D,F,H

A,E,G

F,H

C,E,G

Degree

3

2

3

3

3

3

2

3

In the above graph, for the vertices {A,C,D,E,F,H,C,G}, the degree sequence is {3,3,3,3,3,3,2,2}


Comments

Post a Comment

Popular posts from this blog

Backtracking - N-Queens Problem, Sum of Subsets, Graph Colouring, Hamiltonian Cycle

Image
UNIT - V : BACKTRACKING General Method – 8-Queens Problem – Sum Of Subsets – Graph Coloring –  Hamiltonian Cycles General Method Backtracking is a problem-solving technique used in algorithms to find solutions by exploring all possible options. In backtracking, a state-space tree is a tree-like structure that represents all possible states (solutions or non-solutions) of a problem. Backtracking algorithms explore this tree using a depth-first search approach, systematically checking each path until a solution is found or all possibilities have been exhausted.  Here’s how it works, step-by-step: Start with a choice : Make a decision and move forward. Check feasibility : If this choice leads to a solution or partial solution, continue. If not, stop exploring this path. Go back and try a different path : If you reach a dead end, go back to the last point where you made a choice. Try a different path from there. Repeat until you find a solution ...
Read more

Divide and Conquer Technique - Binary Search, Quick Sort, Merge Sort

Image
  UNIT II - DIVIDE AND CONQUER TECHNIQUE General Method – Binary Search – Merge Sort – Quick Sort.  GENERAL METHOD The divide and conquer technique is a problem-solving approach that works in three main steps: 1.       Divide : Break down a large problem into smaller, simpler sub-problems. 2.       Conquer : Solve each of the sub-problems individually. This can often be done recursively if the sub-problems are still large. 3.     Combine : Combine the solutions of the sub-problems to get the solution to the original, larger problem. This approach is commonly used in algorithms like binary search, merge sort and quick sort, where breaking down a problem makes it easier and faster to solve.   BINARY SEARCH Binary search is an efficient algorithm for finding a target value within a sorted list. Here’s how it works: Start in the Middle : Look at the middle element of the list. Compare : ...
Read more

GRAPH THEORY

Image
  GRAPH THEORY DEFINITION A graph G = (V, E) consists of a non-empty set V, called the set of vertices (points, nodes) and a set  of ordered or unordered pairs of elements of V, called the edges E set (links), such that there is a mapping from the set E to the set of ordered or unordered pairs of elements of V. Example In the first graph, V = { A , B , C , D } E = {(A,B) , (A,C) , (A,D), (B,C), (B,D) , (C,D)} In the second graph, V = { E, F, G } E = {(F,E) , (E,G) , (G,F)} If an edge e ∈ E is associated with an ordered pair (u,v) or an unordered pair (u,v), where u,v ∈ V, then e is said to connect or join the nodes u and v.  The edge e that connects the nodes u and v is said to be incident on each of the nodes.  The pair of each node that is connected by an edge is called adjacent nodes . Isolated Nodes If any node has no edges connected with any other node then its degree will be zero(0) and it will be called as isolated node. Adjacent Nodes Her...
Read more