Latest Updates ☛
- Graphs: Introduction of graphs and types of graphs
- SPOJ : Geeky solves geeky solution
- Solution Code : Pass the time problem on SPOJ.
- Find the minimum shortest path solution in c language ! !
- Code
Author
Welcome !
Heya ! Firstly thanks for giving look to this website .Here you can find all the stuff related to programming plus its solutions means a pack for learners and coders.
So keep visiting and enjoy learning and browsing this Code Author ! !
About Me
- Java Programs
- C++
C++ Programs List
- Books
- C & Data Structures
Data Structures
Reference Book
This is a basic book for a starter to learn data structures in c programming language.Filled with total explanation of all programs working and many more.Read more...
- Privacy Policy
- Others
Tuesday, September 10, 2013
Graphs and Types of graphs
Graphs – An Introduction
A graph is an ordered triple (V(G),E(G),ψG).Where graph G consists of-
V(G) – a non-empty set of vertices,
E(G) – a set of edges (it can be null i.e. a Null set )
ψG – a incident function that associates with each edge
of graph G in an unordered pair vertices of G.
If e is an edge and u and v are its vertices such that ψ0(e)=uv then e is are said to be joined.
The vertices u and v are said to be the ends of the edge e .
Consider the given example –
 |
| A graph |
In this the graph G consists of five vertices i.e. V(G) = {A,B,C,D,E} and four edges namely E(G) = { (A,B),(A,C),(A,D),(A,E) }
and hence for the graph G the incidence function ψG is given as –
ψe(A,B) = AB
ψe(A,C) = AC
ψe(A,D) = AD
ψe(A,E) = AE
Planar Graphs – The graphs that have a diagram whose edges intersect only at their ends, in simple
words they are graph that can be represented in a plane.
Some points to be remembered –
The ends of an edge are incident with the edge and the edge is incident on the ends.
Two vertices are said to be incident if they have acommon edge i.e. those vertices are end points of the edge.
Two edges are said to be incident if they have common vertice.
An edge with same ends points i.e. which points to one vertex is called loop.
An edge with different ends is called as a link.
Symbols used in Graph theory –
G - Graph
V - Vertices set
E - Edges set
| V | - Total number of vertices in graph G.
| E | - Total number of edges in graph G.
δ(G) – Minimal degree of all vertices in graph G
Δ (G) - Maximum degree of all vertices in graph G
Types of Graphs
There are different types of graphs based on their direction, links and loops (I hope u know what these terms are ) .
They can be discussed below as –
Directed graph / Digraph :
A graph containing arrows as a link is called a directed graph or a digraph.
 |
| Directed graph |
 |
| Non -Directed Graph |
 |
| Mixed Graph |
Self-loop graph : A graph with loops (i.e. joining itself) is called self loop graphs.
 |
| Self-loop Graph |
Multi graph : A graph containing loops and parallel edges in it is called a multi graph.
 |
| Multi Graph |
 |
| Simple Graph |
Finite graph : A graph with finite number of edges is called a finite graph.
 |
| Finite Graph |
Infinite graph : A graph with infinite number of edges is called infinite graph.
e.g. Considering universe stars as vertices, can u join all stars ?
Answer is no because they are in infinite numbers same goes here, where universe in infinite graph.
Trivial graph : A graph having only one vertex but no edge is called a trivial graph.
 |
| Single vertex : Trivial Graph |
 |
| Null graph |
Pseudo graph : A graph containing loops but no parallel edges is called pseudo graph.
 |
| Pseudo Graph |
Weighted graph :When the edges are assigned with weights on them then such a graph is called a weighted graph.
 |
| Weighted Graph |
Wheel graph : When all the vertices of the graph join to single vertex then it is called a wheel graph.
 |
| Wheel Graph |
| Relations between the above graphs: Every trivial graph is a simple graph but vice versa is not true. |
Every Null graph is a simple graph but vice versa not true.
Except infinite graph above all graphs are finite graphs until it edges can be counted.
In wheel graph all the edges can be accessed by a single vertex i.e. it has a same starting point or say ending point.
