

Relationship between a network and a graph 


Explanation 





 A graph is used to represent data consisting of discrete objects and to show the relationship between these objects in a simple graphical manner






 In a particular graph theory, a graph is intepreted as a series of dots which are either linked or not linked to one another by lines.






 Each dots is known as a vertex and the line joining two vertices is known as an edge






 A graph is usually used to represent a certain network.






 A network is part of graph with the vertices and edges having their own characteristics and the structure of network data has a many to many relation.






A graph is denoted by a set of ordered pairs \(G= (V,E)\) where
 \(V\) is the set of dots or vertices, \(V={ v_1, v_2, v_3, ....v_n }\)
 \(E\) is the set of edges or lines linking each pair of vertices






The degree, \(d\) is the number of edges that connect two vertices .
The sum of degrees of graph is twice the number of edges that is
\(\sum d(v)= 2E\)




Simple graph 

 A simple graph has no loops and no multiple edges.
 The sum of degrees of the graph is twice the number of edges.


Multiple edges and loops of a graph 

Multiple edges 



 The vertices are connected by more than one edge


 The sum of degrees is twice the number of edges


Loops 



 The edge is in the form of an arc that starts and ends at the same vertex.


 Each loop adds \(2\) to the degree



Example 












Differences between a directed graph and an undirected graph 

Directed graph 
Undirected graph 
 A type of graph that contains ordered pairs of vertices

 A type of graph that contains unordered pairs of vertices

 Edges represents the direction of vertexes

 Edges do not represent the direction of vertexes

 An arrow represents the edges

 Undirected arcs represent the edges




Example 












Differences between weighed graphs and unweighed graphs 


Weighed graph 
Unweighed graph 
Type of graph 
Directed graph and undirected graph 
Directed graph and undirected graph 
Edge 
Associated with a value or a weight 
Not associated with a value or a weight 
Example 
The edge represents:
 distance between two cities
 traveling time
 the current in an electrical circuit
 cost

The edge relates information like:
 job hierarchy in an organisation chart
 flow map
 tree map
 bubble map



Subgraph 


Definition 





A subgraph is a part of a graph or the whole graph redrawn without changing the original positions of the vertices and edges 





A graph \(H\) is said to be a subgraph of \(G\) if,
 the vertex set of graph \(H\) is a subset of the vertex set of graph \(G\) that is \(V(H) \subset V(G)\)
 .the edge set of graph \(H\) is a subset of the edge set of graph \(G\) that is \(E(H) \subset E(G)\)
 the vertex pairs of the edges of graph \(H\) are the same as the edges of graph \(G\)




A tree of a graph is a subgraph of the graph with the following properties


 A simple graph without loops and multiple edges


 All the vertices are connected and each pair of vertices is connected by only one edge


 Number of edges \( =\) Number of vertices \(1\)


 Number of vertices \(=n\)


 Number of edges \(= n1\)



Example of subgraph 















