Graph Theory
Graph Theory
A graph G is an ordered pair (V,E) where V is theset of vertices and E is the set of
edges.
Each edge is associated with an unordered pair(vi, vj). The vertices Vi & vj are
called the end vertices or the terminal vertices of the edge Eij.
Incident
An edge is said to be incident with the vertices it joins
Adjacent
Two vertices are said to be adjacent if they are joined by an edge.
Two edges are said to be adjacent if they are joined by common vertices
Degree of Vertices
No. of edges incident on a particular vertex are called degree of that vertex
Indegree & Outdegree
Number of edges incident on to a vertex & number of vertex incident out of a vertex.
Loop
If the initial vertex viand the terminal vertex vj are same for an edge eij, then eij are
called self loop or simply loop.
Parallel Edges
If there are more than one edges associated with a given pair of vertices then those
edges are called parallel edges or multiple edges.
Isolated Vertex
A vertex is said to be isolated vertex if no edge is incident on it.
Pendant Vertex
Graph Theory 1
, A vertex with degree 1 is called a Pendant vertex.
Adjacent Matrix
An adjacency matrix is a square matrix used to represent a finite graph. The
elements of the matrix indicate whether pairs of vertices are adjacent or not in the
graph.
Incidence Matrix
An incidence matrix is a logical matrix that shows the relationship between two
classes of objects, usually called an incidence relation. If the first class is X and the
second is Y, the matrix has one row for each element of X and one column for each
element of Y.
Directed Graph
A directed graph G is defined as an ordered pair (V,E) ,where V is the set of vertices
and E is the set of edges. (in the sense any graph that has directions)
Graph Theory 2
Graph Theory
Graph Theory
A graph G is an ordered pair (V,E) where V is theset of vertices and E is the set of
edges.
Each edge is associated with an unordered pair(vi, vj). The vertices Vi & vj are
called the end vertices or the terminal vertices of the edge Eij.
Incident
An edge is said to be incident with the vertices it joins
Adjacent
Two vertices are said to be adjacent if they are joined by an edge.
Two edges are said to be adjacent if they are joined by common vertices
Degree of Vertices
No. of edges incident on a particular vertex are called degree of that vertex
Indegree & Outdegree
Number of edges incident on to a vertex & number of vertex incident out of a vertex.
Loop
If the initial vertex viand the terminal vertex vj are same for an edge eij, then eij are
called self loop or simply loop.
Parallel Edges
If there are more than one edges associated with a given pair of vertices then those
edges are called parallel edges or multiple edges.
Isolated Vertex
A vertex is said to be isolated vertex if no edge is incident on it.
Pendant Vertex
Graph Theory 1
, A vertex with degree 1 is called a Pendant vertex.
Adjacent Matrix
An adjacency matrix is a square matrix used to represent a finite graph. The
elements of the matrix indicate whether pairs of vertices are adjacent or not in the
graph.
Incidence Matrix
An incidence matrix is a logical matrix that shows the relationship between two
classes of objects, usually called an incidence relation. If the first class is X and the
second is Y, the matrix has one row for each element of X and one column for each
element of Y.
Directed Graph
A directed graph G is defined as an ordered pair (V,E) ,where V is the set of vertices
and E is the set of edges. (in the sense any graph that has directions)
Graph Theory 2
