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