Graph Theory Introduction

tutorial and example
tutorial and example

Simple Terminologies used in Graph Theory

What is Graph?

A Graph is a connection of lines and points which represents a network. A graph ‘G’ is a set of vertices called nodes. Vertices are denoted by ‘v’ which are connected by edges called links ‘e’. Graph is represented as: G= (v, e).

Vertices

These are the set of points where edges or arcs meet.

Edges

It is the line which connects two vertices or nodes.

Degree of Vertices

The degree of the vertex v is written as d(v). It is the number of edges that meets the particular vertex.

Isolated Vertex

The vertex that has zero degree is known as isolated vertex. These are the vertex that no incident edge.

Pendant Vertex

The vertex that has “one” degree is known as pendant vertex.

What is Subgraph?

A subgraph ‘g’ is a graph in which all the vertices and edges of graph ‘G’ are present and it has the same end vertices as in graph ‘G’.

Walks

A walk in the graph G = (V, E) is the sequence of vertices and edges. For example: v i 0 , e j 1 , v i 1 , e j 2 , . . . , e j k , v i k .The walk starts at a vertex.

  • Open Walk: If the starting vertex and end vertex of the walk is not same than it is known as open walk.
  • Close Walk: If the starting vertex and vertex of the walk are same than it is known as close walk.

Trail

A trail is a walk in which all the edges are different.

Path

A path is a walk in which all vertices are different. In path, the vertices cannot be repeated.

Circuit

A “closed path” is known as a circuit. A circuit can have repeated vertices but not repeated edges.

Isomorphism: Isomorphism is a property in which two graphs are identical i.e. they have one to one correspondence of edges and vertices so that identical relationship is developed. The two isomorphic graph must follow the conditions given below:

  • The number of vertices should be same.
  • The number of edges should be same.
  • An equal number of vertices with a same degree.