## Network

 5.1 Network
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 many-to-many 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.
 Example

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.
 Tips
The degree of a vertex with a loop in an undirected graph is $$2$$, one in clockwise direction and the other in anticlockwise direction.
 Example

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
Undirected Graph Directed Graph
• A simple graph with loops.
• A graph with multiple edges drawn without any direction being assigned.
• A direction is assigned to the edge connecting two vertices.
• Used to represent the flow of a certain process.
 Simple Graph

 Simple Graph

 Graph with Loops and Multiple Edges

 Graph with Loops and Multiple Edges

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

 Example

The diagram shows one-way 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 one-way 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 one-way 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.
 Example

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}=n-1$$

 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.

 Example

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$$

## Network

 5.1 Network
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 many-to-many 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.
 Example

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.
 Tips
The degree of a vertex with a loop in an undirected graph is $$2$$, one in clockwise direction and the other in anticlockwise direction.
 Example

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
Undirected Graph Directed Graph
• A simple graph with loops.
• A graph with multiple edges drawn without any direction being assigned.
• A direction is assigned to the edge connecting two vertices.
• Used to represent the flow of a certain process.
 Simple Graph

 Simple Graph

 Graph with Loops and Multiple Edges

 Graph with Loops and Multiple Edges

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

 Example

The diagram shows one-way 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 one-way 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 one-way 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.
 Example

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}=n-1$$

 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.

 Example

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$$