GRAPH THEORY
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
V = { A , B , C , D }
E = {(A,B) , (A,C) , (A,D), (B,C), (B,D) , (C,D)}
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.
Here B is isolated vertex. A is a adjacent node of C and E, C is the
adjacent node of A, D, D is adjacent node of C, E
Self Loop
An
edge of a graph that joins a vertex to itself is called a self loop.
The
direction of a loop is not significant as the initial and terminal nodes are
and the same.
In
a directed or undirected graph, certain pairs of vertices are joined by more
than one edge, such edges are called parallel edge.
Types of Graphs
Various important types of graphs in graph
theory are
1.
Null Graph
2.
Trivial Graph
3.
Directed Graph
4.
Undirected Graph
5.
Connected Graph
6.
Disconnected Graph
7.
Regular Graph
8.
Complete Graph
9.
Cycle Graph
10.
Cyclic Graph
11.
Acyclic Graph
12.
Finite Graph
13.
Infinite Graph
14.
Bipartite Graph
15.
Weighted Graph
16.
Simple Graph
17.
Multi Graph
18.
Pseudo Graph
19.
Euler Graph
20.
Hamiltonian Graph
1. Null Graph
A graph containing only isolated nodes is called a null graph.
Example
- Since the edge set is empty, therefore it is a null graph.
2. Trivial Graph
A graph having only
one vertex in it is called as a trivial graph.
It is the smallest possible graph.
Example
If in graph G(V, E), each edge e∈E is associated
with an ordered pair of vertices, then G is called a directed graph or digraphs.
In other words, all the edges of a directed
graph contain some direction.
Example
If each edge is associated with an unordered
pair of vertices, then G is called an undirected graph.
In other words, edges of a graph do not
contain any direction.
Example
A graph in
which we can visit from any one vertex to any other vertex is called as a
connected graph.
In connected graph, at least one path exists
between every pair of vertices.
Example
- we can visit from any one vertex to any other vertex.
- There exists at least one path between every pair of vertices.
- Therefore, it is a connected graph.
6. Disconnected Graph
A graph in which there does not exist any path
between at least one pair of vertices is called as a disconnected graph.
Example
- consists of two independent components which are disconnected.
- It is not possible to visit from the vertices of one component to the vertices of other component.
- Therefore, it is a disconnected graph.
7. Regular Graph
A graph in which degree of all the vertices is
same is called as a regular graph.
If all the vertices in a graph are of degree
‘k’, then it is called as a “k-regular graph“.
Example
- All the vertices have degree-2.
- Therefore, they are 2-Regular g
8. Complete Graph
A simple graph in which there is exactly one
edge is present between every pair of vertices is called as a complete graph.
A complete graph of ‘n’ vertices contains
exactly nC2 or (n(n-1))/2 edges.
Example
- Each vertex is connected with all the remaining vertices through exactly one edge.
- Therefore, they are complete graphs.
9. Cycle Graph
A simple graph of ‘n’ vertices (n>=3) and n
edges forming a cycle of length ‘n’ is called as a cycle graph.
In a cycle graph, all the vertices are of
degree 2.
Example
- Each vertex is having degree 2.
- Therefore, they are cycle graphs.
10. Cyclic Graph
A graph containing at least one cycle in it is
called as a cyclic graph.
Example
- contains two cycles in it.
- Therefore, it is a cyclic graph.
11. Acyclic Graph
A graph not containing any cycle in it is
called as an acyclic graph.
Example
- does not contain any cycle in it.
- Therefore, it is an acyclic graph.
12. Finite Graph
A graph consisting of finite number of vertices and edges is called as a finite graph.
Example
A graph consisting of infinite number of
vertices and edges is called as an infinite graph.
Example
A bipartite graph is a graph where
Vertices can be divided into two sets X and Y.
The vertices of set X only join with the
vertices of set Y.
None of the vertices belonging to the same set
join each other.
Example
A weighted graph is
a graph where each edge has a numerical value called weight.
The weight of an edge can represent cost or distance.
It can be represented in two
ways:
Directed
weighted graphs where the edges have arrows that show path direction.
Undirected
weighted graphs where edges are bi-directional and have no arrows.
Example - Undirected weighted graphs
A graph having no self loops and no parallel edges in it is
called as a simple graph.
Example
- consists of three vertices and three edges.
- There are neither self loops nor parallel edges.
- Therefore, it is a simple graph.
17. Multi Graph
A graph having no self loops but having
parallel edge(s) in it is called as a multi graph.
Example
- consists of three vertices and four edges out of which one edge is a parallel edge.
- There are no self loops but a parallel edge is present.
- Therefore, it is a multi graph.
18. Pseudo Graph
A pseudo graph having parallel edges and self loop(s)
Example
- consists of three vertices and four edges out of which one edge is a self loop.
- This graph also have parallel edges.
- Therefore, it is a pseudo graph.
19. Euler Graph
Euler Graph is a connected graph in which all
the vertices are even degree.
Example
- is a connected graph.
- The degree of all the vertices is even.
- Therefore, it is an Euler graph.
20. Hamiltonian Graph
If there exists a closed walk in the connected
graph that visits every vertex of the graph exactly once (except starting
vertex) without repeating the edges, then such a graph is called as a
Hamiltonian graph.
Example
- contains a closed walk ABCDEFA that visits all the vertices (except starting vertex) exactly once.
- All the vertices are visited without repeating the edges.
- Therefore, it is a Hamiltonian Graph.
SUBGRAPHS
A graph S=(V′, E′) is called a subgraph of G=(V, E), if V′⊆V and E′⊆E.
Proper Subgraph of G
If V′⊂V and E′⊂E, then S is called a proper
subgraph of G.
Spanning Subgraph of G
If V′=V, then H is called a spanning
subgraph of G.
A spanning
subgraph of G need not contain all its edges.
Vertex deleted Subgraph of G
If we delete a subset U
of V and all the edges incident on the elements of U from a graph G=(V,E), then
the subgraph (G – U) is called a vertex deleted subgraph of G
Note:
Any subgraph of a graph G can be
obtained by removing certain vertices and edges from G.
The removal of an edge does not go with
the removal of its adjacent vertices, whereas the removal of a vertex goes with
the removal of any edge incident on it.
Edge deleted Subgraph of G
If we delete a subset F
of E from a graph G(V,E), , then the subgraph (G – F) is called an edge deleted
subgraph of G
Induced Subgraph of G
A subgraph S=(V′,
E′) of G=(V, E), where V′⊆V and E′ consists of
only those edges that are incident on the elements of V′, is called an induced
subgraph of G.
Matrix Representation of Graph & Edge Sequence, Walk, Path and
Circuits
https://deepanotes.blogspot.com/2020/10/matrix-representation-of-graph-edge.html
Comments
Post a Comment