Graph Theory in Computer Science - Assignment Example

Section A Flow chart for check whether a number entered at the keyboard is odd or even ` 2. Flow chart for calculate the mean of series of numbers. 4. Flow chart for find largest and smallest numbers from a list. 3. Flow chart list of initial letters from a series of words entered at the keyboard Section B Graph theory Graph theory is an essential part of computer science. Graph theory and computer science are complementary to each other. The significance of graph theory in computer science is remarked by Dr. Narasingh Deo as "Computers allow us to solve very large problems concerning graphs, while on the other hand, graph theory helps advance computer science" ( Deo). It is used to solve complex problems. The theory of graph has a definite starting place in a paper published in 1936 by the Swiss mathematician, Leonhard Euler. In this paper he solved a problem that was then known as the Konigsberg bridge problem by formulating it in terms of graph theory. Now, this theory is being fruitfully used for solving problems related to the manufacture of integrated circuits, routing problems in transport network, and other important areas of computer science. First major application of graph theory to operational research was the theory of network flows developed by Ford and Fulkerson in 1956.Graph theory was motivated by the application of interconnection networks that is in the network topology properties like distance, connectivity, and regularity. Thinking about the applications of graph theory in computer science, the first point that comes to mind is that "the World Wide Web can be modeled as a directed graph where each node is a Web page and each hyperlink is an edge or line. Studying Web graphs gives insight into lots of things, such as Web algorithms for crawling, searching or ranking Web resources. Or if a virus spreads, we can use graph theory to see how it would travel through the Web. The Internet is a similar, large graph, and if you want to isolate certain cyber attacks, or something, you can do it using graph theory" (Deo) Due to the importance of graph theory in computer science computer scientists have developed many interesting and deep graph algorithms. Based on the researches conducted by many computer scientists, they have identified a set of graph problems which has no efficient algorithm for solving those problems. This leads to the birth of an important part of graph theory called NP-Completeness. It is a significant contribution of graph theory in computer science. Graph theory is mainly used in the following areas of computer science. They are algorithms, cryptography, Fortran, Internet connectivity, logic, Maple programming, Numerical analysis, C, error correction, graph theory, Java, Machine learning, Matlab, and theory of computation. Definition of graph A graph G = (V (G), E (G)).That is a graph G is a non empty set of vertices V with set of edges E consisting of a pair of points of V. Usages of graph in computer science: Various computers, printers and plotters in a school, college hospital etc can be connected using Local Area Network (LAN).These networks are based on star topology. Star topology is a product of graph theory. Here n devices are connected to a central device called hub, from which messages are sent to other connected device. As I already mentioned, one of the major application areas of graph theory in computer science is algorithms and internet connectivity. For example, in computer science dynamic programming is a technique used to solve optimization problems, using bottom –up approach. The essential idea of the dynamic programming is to avoid calculating the same thing repeatedly, using by keeping a table of known results, that fills up the instance of the problem are solved. In computer science we have some algorithms based on greedy technique, which are used for solving optimization problems. The essence of greedy technique is the process of solving an optimization problem, initially and subsequence stages; we evaluate the cost/benefits of the various available alternatives for the next step. Choose the alternative which is optimal in the sense that either it is least costly or it is the maximum profit yielding. In this context, it may be noted that the overall solution, yielded by choosing locally optimal steps, may not be optimal. We can apply greedy technique to develop algorithm to solve some problems like finding minimum spanning tree for a given graph. Definition of spanning tree in graph theory A spanning tree for a graph say G = (V, E) with V as set of vertices and E as set of edges, is its connected acyclic sub-graph that is tree that contains all the vertices of the graph. A Minimum spanning tree of a weighted graph is its spanning tree of smallest weight, where the weight of the tree defined as the sum of the weights on all its edges. In computer science Prim’s algorithm and Kruskal’s algorithm use greedy technique to find spanning trees for connected graphs. Depth First Search (DFS) and Breadth First Search (BFS) are another two algorithms used for creating spanning tree. In Breadth first search first discovers all vertices adjacent to a given vertex before moving to the vertices far ahead in the search graph. CIf G (V, E) is a graph having vertex set V and edge set E and a particular source vertex s, breadth first search find or discovers every vertex that is reachable from s. First it discovers every vertise adjacent to s, and then systematically for each of those vertices it finds all the vertices adjacent to them and so on. The depth first search is a search strategy in which the examination of a given vertex u, is displayed when a new vertex say v is reached and examination of v is decayed when new vertex say w is reached and so on. Spanning trees are important in data networking particularly in multicasting over Internet Protocol (IP) networks. To send data from a source computer to multiple receiving computers, each e.g. which is sub-network, data could be sent separately to each computer. This type of networking, called uncasing, is inefficient, since many copies of the sane data are transmitted over the network. To make the transmission of data to multiple receiving computers more efficient, IP multicasting is used. With IP multicasting, a computer sends a single copy of data over the network, and as data reaches intermediate routers the data are forwarded to one or more other routers so that ultimately all receiving computers in their various sub-networks receive these data. For data to reach receiving computers as quickly as possible there should be no loop, in terms of graph theory circuits or cycle in the path that data take thr4ough the network. That is once data have reached a particular router, data should never return to this router. To avoid loops, the multicast routers use network algorithms to construct a spanning tree in the graph that has the multicast source, the routers, and the sub-networks containing receiving compilers as vertices, with edges representing the links between computers and/or routers. In computer science graph theory is also used in computer network security area. Vertex cover problem in graph theory is recently used to protect large network against attack worm propagation .The idea behind it is that find the minimum vertex cover in the graph whose vertices are the routing servers and its edges are the connections between two routing severs. It is the optimal solution against worm propagation. I already mentioned about the NP-Completeness in graph theory, a problem is said to be NP-Complete if it is in NP and for which no polynomial –time Deterministic TM solution is known so far. Polynomial time reduction means a polynomial time algorithm which constructs the instances of a problem P2 from the instances of some other problem P1Some NP-Complete problems are Satisfiability problem or SAT, Primality problem, Travelling salesman problem, Vertex cover problem,, K-Colourability problem, the complete subgraph problem or clique problem, Independent set problem, exact cover problem etc. A method of establishing the NP-Completeness of a problem P2 constitutes of designing a polynomial time reduction that constructs an instances of P2 for each instances of P1, where P1 is already known to be NP-Complete. Let us look at the vertex cover problem and its justification. A vertex cover for a graph G is a set C of vertices so that each edge in C has an end point in C. Justification for vertex cover problem is NP-complete A vertex cover of an undirected graph G= (V, E) is a subset V of the vertices of the fraps which contain at least on of the two end points of each edge. The vertex cover problem is the optimization problem of finding a vertex cover of minimum size in a graph. The problem can also be stated as a decision problem: VERTEX COVER = ( Read More