|
|
| |
| 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 |
| |
|
|
| |
- The vertices are connected by more than one edge
|
| |
- The sum of degrees is twice the number of edges
|
| |
| Loops |
| |
|
|
| |
- 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 |
|
| |
|
|
| |
 |
|
| |
 |
|
|
| |
| |
| |
| |
| |
