1. Learn
  2. Quick Notes
  3. List
  4. Networking
Back

Chapter 5: Network in Graph Theory 

 

5.1 Network 
 
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 
 
  • Involve two vertices 
 
  • The vertices are connected by more than one edge 
 
  • The sum of degrees is twice the number of edges 
 
Loops 
 
  • 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
 
  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 \(= n-1\)
 
  Example of subgraph   
     
   
   
 
 
 
 
 
The views expressed in the notes here are those of the contributor and don’t necessarily represent the views of pandai.

Chapter 5: Network in Graph Theory 

 

5.1 Network 
 
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 
 
  • Involve two vertices 
 
  • The vertices are connected by more than one edge 
 
  • The sum of degrees is twice the number of edges 
 
Loops 
 
  • 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
 
  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 \(= n-1\)
 
  Example of subgraph   
     
   
   
 
 
 
 
 
The views expressed in the notes here are those of the contributor and don’t necessarily represent the views of pandai.
Chapter : Networking in Graph Theory
Topic : Networking
Form 4 Mathematics
Related notes

Report this note
Report Card

Evaluate your academic performance through detailed report

Learn more
Register for a free Pandai account now
© 2025 Pandai.org All Rights Reserved

Quiz
View video m
Notes
Account