Quick Notes

• 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\)

• 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

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 

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\)