Chapter 5: Network in Graph Theory 


5.1 Network 
Relationship between a network and a graph 
  • 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 
  • Involve two vertices 
  • The vertices are connected by more than one edge 
  • The sum of degrees is twice the number of edges 
  • Involve one vertex 
  • The edge is in the form of an arc that starts and ends at the same vertex.
  • Each loop adds \(2\) to the degree
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
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 

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 
  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 \(= n-1\)
  Example of subgraph