Graph :
Definition-
It is a triple consisting of a vertex set V(G), an edge set E(G) and a relation that associates with each edge and two vertices (not necessarily distinct) called its end points. Basic types of graphs are directed and undirected graphs.
Trails: Vertices may repeat. Edges cannot repeat (Open)
Example 1: A-B-I-C-D-J-I-G is trail example in given graph.(repeated vertices are I, no repeated edges).
Path : Vertices cannot repeat. Edges cannot repeat (Open)
Circuit : Vertices may repeat. Edges cannot repeat (Closed).
Cycle : Vertices cannot repeat except that the initial vertex is the terminal vertex. Edges cannot repeat (Closed)
Connected graphs: A graph is a connected graph if selected any two vertices Vi, Vj from set V(G), there is a path from Vi to Vj. So, Every vertex is reachable from every other vertex in V(G) by some path. We see example of the connected graph both in directed and undirected graph.
Example connected directed graph: In below figure first graph is disconnected directed graph with no path from B to D. After adding the directed edge B to D graph become connected. Now, every vertex is reachable to other vertex.
Regular graphs: A graph is a regular graph if its every vertex has the same degree (or valency). A graph has every vertices of degree k, such regular graph is called k-regular graph.
Example:
A 0-regular graphs are graphs with each vertices having degree 0, then such graph have all disconnected vertices.
A 1-regular graphs are graphs with each vertices having degree 1, then such graph consists of disconnected edges therefore no of vertices in graph is even.
A 2-regular graphs are graphs with each vertices having degree 2, then such graph disjoint union of the cycles.
Every complete graph Km is k-regular.
Bipartite graphs:
A simple graph G = (V, E) with two disjoint and independent sets V = {V1, V2} is called a bipartite graph if every edge of E joins a vertex in V1 to a vertex in V2.
There is no edge among vertices of same set(V1 or V2).
Bipartate graph doesn't have any odd length cycles.
Bipertite graph has two sets disjoint and independent sets of vertices, let us say, V1 and V2, and if an edge is drawn, it should connect any vertex in set V1 to any vertex in set V2.
Tree and rooted tree:
A tree is a connected graph without cycles.
A rooted tree T is a connected acyclic graph with one vertex is specified as the root of the tree.
Path to every vertex originates directly or indirectly from the root vertex.
The level of a vertex from the root defined as the number of edges in the shortest walk between vertex and the root.
It is assumed that root node is at Level-0 for the rooted tree.
The vertex directly connected to the root vertex is at Level-1.
Spanning trees:
A spanning tree T is tree which is subgraph of an undirected connected graph G, which includes all of the vertices connected with minimal set of edges.
Eccentricity of a vertex:
The eccentricity of vertex e(V) is the greatest of the distances between a vertex V to all other vertices.
Diameter of a graph:
Diameter of the Graph G is maximum of eccentricities of the vertices in a graph.The maximum among all the distances between a any vertex to all other vertices.
The diameter of a connected graph is the largest distance between pairs of vertices of the graph.
Radius of a graph:
Radius of the Graph G is minimum of eccentricities of the vertices in a graph.
Centres of a tree:
In a tree, a vertex with minimal eccentricity is called center.
There are two types of the tree based on center.
A tree is called central tree if a tree has only one center and tree with two centers is Bi-centered tree.
Central Graphs:
Hamiltonian Path is a path which visits every vertex in a given graph exactly once.
Hamiltonian Circuit is a Hamiltonian path which starts and ends on the same vertex.
A graph which contains a Hamiltonian cycle is called a Hamiltonian graph.
Eulerian Path is a path or trail which visits every edge in a given graph exactly once.
Eulerian Circuit is a Eulerian path which starts and ends on the same vertex.
Eulerian graphs: A graph which contains the Eulerian circuit is called the Euler/Eulerian graph.
A graph contains the Eulerian circuit if and only if every vertex has even degree and all non-zero degree vertices belongs to one connected component.
Planar graphs is a graph which can be drawn on a plane such that no edges in graph intersect each other.
Definition-
It is a triple consisting of a vertex set V(G), an edge set E(G) and a relation that associates with each edge and two vertices (not necessarily distinct) called its end points. Basic types of graphs are directed and undirected graphs.
To understand difference between walk, path, trail, cycle and circuit, its needed to define walk trail path cycle and circuit of a graph with example.
Walk : Vertices may repeat. Edges may repeat (Closed or Open). Here, You can take any edge and vertices combination to find the walk in graph. There are two types open walk and closed walk in graph theory.
Lets take some example in above graph.
Example 1: A-B-I-J-I-C-D is open walk. (repeated vertices are I, repeated edges are I-J (or J-I)).
Example 2: A-B-I-J-D-C-I-G-A is closed walk as start and end vertices are same. (repeated vertices except start and end vertices are I, no repeated edges).
Example 1: A-B-I-C-D-J-I-G is trail example in given graph.(repeated vertices are I, no repeated edges).
Path : Vertices cannot repeat. Edges cannot repeat (Open)
A-B-I-J-D-C is a path example.
A-B-C-I-J-D-H-E-F-G is Hamiltonian path example.(each vertex visited exactly once in this path)
Circuit : Vertices may repeat. Edges cannot repeat (Closed).
Cycle : Vertices cannot repeat except that the initial vertex is the terminal vertex. Edges cannot repeat (Closed)
Example connected directed graph: In below figure first graph is disconnected directed graph with no path from B to D. After adding the directed edge B to D graph become connected. Now, every vertex is reachable to other vertex.
 |
| Disconnected graph |
 |
| Connected Graph |
Example:
A 0-regular graphs are graphs with each vertices having degree 0, then such graph have all disconnected vertices.
A 1-regular graphs are graphs with each vertices having degree 1, then such graph consists of disconnected edges therefore no of vertices in graph is even.
A 2-regular graphs are graphs with each vertices having degree 2, then such graph disjoint union of the cycles.
Every complete graph Km is k-regular.
Bipartite graphs:
A simple graph G = (V, E) with two disjoint and independent sets V = {V1, V2} is called a bipartite graph if every edge of E joins a vertex in V1 to a vertex in V2.
There is no edge among vertices of same set(V1 or V2).
Bipartate graph doesn't have any odd length cycles.
Bipertite graph has two sets disjoint and independent sets of vertices, let us say, V1 and V2, and if an edge is drawn, it should connect any vertex in set V1 to any vertex in set V2.
A tree is a connected graph without cycles.
A rooted tree T is a connected acyclic graph with one vertex is specified as the root of the tree.
Path to every vertex originates directly or indirectly from the root vertex.
The level of a vertex from the root defined as the number of edges in the shortest walk between vertex and the root.
It is assumed that root node is at Level-0 for the rooted tree.
The vertex directly connected to the root vertex is at Level-1.
Spanning trees:
A spanning tree T is tree which is subgraph of an undirected connected graph G, which includes all of the vertices connected with minimal set of edges.
Eccentricity of a vertex:
The eccentricity of vertex e(V) is the greatest of the distances between a vertex V to all other vertices.
Diameter of a graph:
Diameter of the Graph G is maximum of eccentricities of the vertices in a graph.The maximum among all the distances between a any vertex to all other vertices.
The diameter of a connected graph is the largest distance between pairs of vertices of the graph.
Radius of a graph:
Radius of the Graph G is minimum of eccentricities of the vertices in a graph.
Centres of a tree:
In a tree, a vertex with minimal eccentricity is called center.
There are two types of the tree based on center.
A tree is called central tree if a tree has only one center and tree with two centers is Bi-centered tree.
Central Graphs:
Hamiltonian Path is a path which visits every vertex in a given graph exactly once.
Hamiltonian Circuit is a Hamiltonian path which starts and ends on the same vertex.
A graph which contains a Hamiltonian cycle is called a Hamiltonian graph.
 |
| Non-Hamiltonian Graph Hamiltonian Path: 3-1-4-2-5 |
 |
| Hamiltonian Graph Hamiltonian Circuit: 3-1-5-2-4-3 |
Eulerian Circuit is a Eulerian path which starts and ends on the same vertex.
Eulerian graphs: A graph which contains the Eulerian circuit is called the Euler/Eulerian graph.
A graph contains the Eulerian circuit if and only if every vertex has even degree and all non-zero degree vertices belongs to one connected component.
|
| Eulerian Graph Eulerian Circuit: 2-0-1-2-4-3-2 All vertices has even degree. |
 |
| Non-Eulerian Graph Eulerian path:2 -1 -0 -2 - 3 -5 -4 -3 Vertices 2 and 3 has odd degree |
Planar graphs is a graph which can be drawn on a plane such that no edges in graph intersect each other.
 |
| Above complete graph K4, is Planar graph as it can be drawn on the plane as above |
 |
| Above complete graph K5 is non-planar graph as it cannot be drawn on plane without intersection of edges. Here, when we try to draw edge (2-4), it intersects with edge (0-3) or edge (1-3) |
No comments:
Post a Comment