GRAPHS DATA STRCUTURE

-

Definition and Concepts

A graph G consists of non-empty set V called the set of nodes (points,vertices) of the graph, a set E which is the set of edges of the graph, and a mapping from the set of edges E to a set of pairs of elements of V.

G = (V, E)

We shall assume throughout that both sets V and E are finite. Every edge of the graph G, we can associate a pair of nodes(u, v) where u, v belong to set V, then we say that the edge x connects the nodes u and v. Any two nodes which are connected by an edge in a graph are called adjacent nodes.

In a graph G = (V, E), an edge is directed from one node to another node is called directed edge. A graph in which every node has directed edges is called directed graph, or a digraph. An edge which has no specific direction is called undirected edge. A graph which consists of undirected edges is called undirected graph. A graph which consists of both directed and undirected graphs is called a mixed graph.

A city map showing only the one-way streets is an example of directed graphs where the intersections are the nodes and the streets are the edges. Similarly a city map showing only the two-way streets is an example of undirected graphs. A city map showing both the one-way and two-way roads is an example of mixed graphs.

In the above image, we find the examples of directed and undirect graphs. Using this, we can also form a mixed graph. The directed edges are shown by arrow indicators. 

Let (V, E) be a graph and let x, an element of the set E be an edge associated with a ordered pair of nodes(u, v). Then, the edge x is said to initiating or originating in the node u and terminating in the node v.The nodes u and v are the initial and terminal nodes respectively. 

An edge of a graph which joins a node to itself is called a loop. The direction of the loop is of no significance. Therefore it can be considered a directed or undirected edge. 

In some directed as well as undirected graphs, we may have a certain pair of nodes joined by more than one edge. Such edges are called parallel. 

Any graph which contains a parallel edge is multigraph.

The graphs with parallel edges can be represented by the second diagram in which the number on any edge shows the multiplicity of the edge.

We may also consider the multiplicity as a weight assigned to an edge. A graph in which weights are assigned to every edge is called weighted graph.

A graph representing a system of pipelines, in which the weights assigned indicate some type of commodity transferred through pipe is an example of weighted graph. Similarly, a graph of city streets representing the traffic density can be considered as a weighted graph.

In a graph, a node which is not adjacent to any other node is called an isolated node. A graph containing only isolated nodes is called a null graph.

In a graph, the number of edges connected to v as initial node are called the outdegree of node v. The number of edges connected to v as terminal node are called indegree of node v. The sum of indegree and outdegree of nodes is called the total degree of node v.  

Comments

Post a Comment

Popular posts from this blog

THREE LEVELS OF DATA INDEPENDENCE

-
Image
THREE LEVELS OF DATA INDEPENDENCE It divides the entire system into three inter-related but independent modules: Physical Level: Here, information about the location of database objects in the data store is kept. Various DBMS users are unaware of the locations of these objects. The Physical level of database describes how the data is stored in secondary storage devices such as disks and tapes. Conceptual Level: Here, data is represented in the form of various tables. For Example, STUDENT database may contain NAME and COURSE tables, but the users are unaware of their storage. It refers to what kind of data to be stored in a database. External Level: Here, it specifies the view of data in terms of conceptual level tables. It can generate different views of the database for different users. It focuses main on data abstraction.  Data Independence: It means change of data at one level must not affect the another level. Physical Data Independence: Any change in the physical location of the t
Read more

Python-HackerRank Problem List Comprehensions

-
Problem Print a list of all possible coordinates given by (i,j,k) on a 3D grid where the sum of i+j+k is not equal to  n. Here, 0<=i<=x;0<=j<=y;0<=k<=z. Please use list comprehensions rather than multiple loops, as a learning exercise.  Source Code   if  __name__ ==  '__main__' :     x =  int ( input ())     y =  int ( input ())     z =  int ( input ())     n =  int ( input ())      print   ([[ a , b , c ]   for  a  in   range ( 0 , x+1 )   for  b  in   range ( 0 , y+1 )   for  c  in   range ( 0 , z+1 )     if  a + b + c != n  ])                 
Read more

Python Problem Solving - Lonely Integer

-
Given an array of integers, where all elements but one occur twice, find the unique element. Solution: n  =  int ( input ()) array  =  list ( map ( int ,   input () . rstrip () . split ())) for   element   in   array :      count  =  array . count ( element )      if   count  ==  1 :          print ( element )
Read more