Relationship Between a Network and a Graph 
 A graph represents discrete data and shows the relationships between objects in a simple, visual way.
 A graph is a series of dots connected or not connected by lines.
 Each dot is known as a vertex, and the line joining two vertices is known as an edge.
 A graph typically represents a network.
 A network is a part of a graph where the vertices and edges have specific characteristics.
 The structure of network data has a manytomany relationship.

The Sum of Degrees of a Graph 
\(\sum d(v)=2E;v \isin V\)
\(G\) 
Graph 
\(d\) 
Degree 
\(v\) 
Vertex or Dot 
\(V\) 
Set of Dots or Vertices 
\(e\) 
Edge or line or arc 
\(E\) 
Set of Edges or Lines Linking Each Pair of Vertices 
\(\sum\) 
Sum 

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.

Based on the simple graph given, determine \(V\text{ and }n(V)\), \(E\text{ and }n(E)\) and sum of degrees.
\(V\text{ and }n(V)\) 
\(\text{Set of vertices}=V=\{1,2,3,4,5,6\}\\\text{Number of vertices}=n(V)=6\color{red}\text{}\) 
\(E\text{ and }n(E)\) 
\(\text{Set of vertex pairs}=E=\{(1,2),(1,5),(2,3),(2,4),(3,4),(4,5),(5,6)\}\\\text{Number of edges}=n(E)=7\) 
Sum of Degrees 
\(\sum d(v)=2(E)\\\qquad\quad\;=2(7)\\\qquad\quad\;=14\)


Multiple Edges and Loops of a Graph 
Multiple Edges 
Loops 
 Involve \(2\) vertices.
 The vertices are connected by more than \(1\) edge.
 The sum of degrees is twice the number of edges.

 Involve \(1\) vertex.
 The edge in the form of an arc that starts and ends at the same vertex.
 Each loops adds \(2\) to the degree.


The degree of a vertex with a loop in an undirected graph is \(2\), one in clockwise direction and the other in anticlockwise direction. 
The diagram below shows a graph with a loop and multiple edges. State \(V\text{ and }n(V)\), \(E\text{ and }n(E)\) and sum of degrees.
\(V\text{ and }n(V)\) 
\(V=\{P,Q,R,S,T,U\} \\n(V)=6\color{red}\text{}\) 
\(E\text{ and }n(E)\) 
\(E=\{(P,Q),(P,U),(P,U),(Q,R),(Q,U),(R,S),(R,T),(S,S),(S,T),(T,U)\} \\n(E)=10\color{red}\text{}\) 
Sum of Degrees 
\(\text{Degree of vertex }P=3\\\text{Degree of vertex }Q=3\\\text{Degree of vertex }R=3\\\text{Degree of vertex }S=4\\\text{Degree of vertex }T=3\\\text{Degree of vertex }U=4\)
The sum of degrees is \(20\).


Difference Between a Directed Graph and an Undirected Graph 

Differences Between Weighted Graphs and Unweighted Graphs 
Weighted Graph 
Unweighted Graph 
 Type of graph:
 directed graph
 undirected graph
 Edge:
 associated with a value or a weight
 The edge represents:
 distance between two cities
 travelling time
 the current in an electrical circuit
 cost

 Type of graph:
 directed graph
 undirected graph
 Edge:
 not associated with a value or a weight
 The edge relates informaton like:
 job hierarchy in an organisation chart
 flow map
 tree map
 bubble map


The diagram shows oneway paths that Aiman can choose for his running practice. Vertex \(v_1\) is the starting position and vertex \(v_5\) is the ending position before he goes home.
Determine
 the shortest distance from \(v_1\) to \(v_5\).
 the longest distance from \(v_1\) to \(v_5\).
 the vertices that must be passed through if the distance of the oneway run is between \(1.4\text{ km}\) and \(2.1\text{ km}\).

Solution 
Shortest distance from \(v_1\) to \(v_5\) 
\(\quad v_1\rightarrow v_2 \rightarrow v_5\\=(600+500)\text{ m}\\=1\,100\text{ m}\\=1.1\text{ km}\) 
Longest distance from \(v_1\) to \(v_5\) 
\(\quad v_1\rightarrow v_2 \rightarrow v_3\rightarrow v_4 \rightarrow v_5\\=(600+900+500+500)\text{ m}\\=2\,500\text{ m}\\=2.5\text{ km}\) 
The vertices that must be passed through if the distance of the
oneway run is between \(1.4\text{ km}\) and \(2.1\text{ km}\) 
\(v_1,v_3,v_4,v_5 \text{ and }v_1,v_2,v_4,v_5\) 

Subgraph 
A subgraph is part of a graph or the whole graph redrawn without changing the original positions of the vertices and edges. 
Determine whether below are the subgraphs of graph \(G\).

Solution 

Yes, because the vertex pair of edge \(e_5\) is the same.
\(\{e_5\}\subset\{e_1,e_2,e_3,e_4,e_5\}\) and \(\{P,S\}\subset\{P,Q,R,S\}\)


No, because the position of loop \(e_2\) is not on vertex \(Q\). 

No, because the edge connecting vertex \(P\) and vertex \(S\) is not \(e_3\). 

No, because the loop and and the edge connecting vertex \(Q\) and vertex \(R\) are wrong. 

Tree 
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.
 \(\text{Number of edges}=\text{Number of vertices}1\\\text{Number of vertices}=n\\\text{Number of edges}=n1\)


Tree, because
 all the vertices are connected.
 every pair of vertices is connected by an edge only.
 there are no loops or multiple edged.
 \(5\) vertices, \(4\) edges.


Not a tree, because
 vertex \(B\) and vertex \(E\) can be connected in two ways
 \(B \rightarrow E\)
 \(B \rightarrow C \rightarrow D \rightarrow E\)
 \(5\) vertices, \(5\) edges.


The following diagram shows an undirected weighted graph. Draw a tree with a minimum total weight.
Solution:
Step \(1\) 
Step \(2\) 
 \(5\) vertices, \(7\) edges.
 \(3\) edges to be removed.
 Remove edges with the greatest weights \((PQ, QR, PT)\).
The graph above is not a tree because
 vertex \(P\) is not connected to the other vertices.
 \(3\) edges, \(RS,ST\) and \(RT\), connect \(3\) vertices only.

 Between the weights \(19\) and \(25\), keep weight \(19\) because its weight is smaller.
 Between the weights \(12\), \(14\) and \(17\), remove weight \(17\).
The graph above is a tree.
Minimum total weight of the tree
\(=10+12+14+19\\=55\)


