Analysis of Graph Theory

Analysis of Graph Theory In mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pair wise relations between objects from a certain collection. A graph is a very simple structure consisting of a set of vertices and a family of lines (possibly oriented), called edges (undirected) or arcs (directed), each of them linking some pair of vertices. An undirected graph may for example model conflicts between objects or persons. A directed graph (or digraph) may typically represent a communication network, or some domination relation between individuals, etc. The famous problem of the bridges of Kà ¶nigsberg, solved by Euler, is viewed as the first formal result in graph theory. This theory has developed during the second half of the 19th century (with Hamilton, Heawood, Kempe, Kirchhoff, Petersen, Tait), and has boomed since the 1930s (with Kà ¶nig, Hall, Kuratowski, Whitney, Erdà ¶s, Tutte, Edmonds, Berge, Lovà ¡sz, Seymour, and many other people). It is clearly related to Algebra, Topology, and other topics from Combinatorics. It applies to and gets motivating new problems from Computer Science, Operations Research, Game Theory, Decision Theory. â€Å"Because of its inherent simplicity, graph theory has a very wide range of applications in engineering, in physical, social, and biological sciences, in linguistics, and in numerous other areas. A graph can be used to represent almost any physical situation involving discrete objects and relationship among them† (Narsingh Deo). The term â€Å"graph† in mathematics has different meanings. There is a graph for the function and relation. Graphs, especially tree graphs and directed graphs appear in the computer and information sciences. Flowcharts for example are directed graphs. A flowchart is a visual representation of an algorithm. It is frequently used in the planning, development and structuring of an algorithm for solving a complex problem. The flowchart is regarded as an essential part of the documentation of any computer translation of the original algorithm (Seymour Lipschutz). There are two commonly used tools to help to document program logic (the algorithm). These are flowcharts and Pseudocode. Generally, flowcharts work well for small problems but Pseudocode is used for larger problems. Flowcharts are used in the design phase of software creation. It specifies the logical flow of a program. The semantics of a flowchart are totally concerned just with control flow-what happens first, and then what happens next, and so on. A flowchart is drawn using a small set of symbols with well-defined meanings. An elongated oval denotes the beginning of the program, where the execution commences. Passage of flow from the beginning, and at later stages, is denoted by edges with directional arrows. A box in the shape of a parallelogram denotes either an input (such as a READ), or an output (such as a PRINT). A rectangle denotes a computational step, such as addition, and a diamond-shaped box denotes a decision step. A diamond usually has one arrow leading in, and two or more leading out, denoting different ways the control can proceed from that point. A diamond is used in cases of decision statements like, If A is more than 7, proceed to multiply B and C; else, divide C and D. Example of flowchart which reads 2 numbers A and B, and prints them in decreasing order after assigning the larger number to BIG and smaller number to SMALL. â€Å"Essential computer mathematics† Seymour Lipschutz, 1987, page 101 A flowchart is a visual representation of sequence of operations performed to get the solution of the problem. They are usually drawn in early stages of programming project. They help with better communication between the programmers and their business customers. The flowcharts are very helpful with understanding complicated problems and programming logic, especially for people who do not work with (or understand) programming and coding. We can say that flowcharts are necessary for better documentation of complex programs. They also work as a guide during the system analysis and program development phase. If we have good flowchart for the programme the maintenance becomes easier, as the programmer can be more efficient in debugging process, as he can clearly see which parts he has to focus on. Flowcharts are also used in industrial and process engineering and management. The Unified Modelling Language (UML) created by the Three Amigos of software engineering borrows some of its basic ideas from the flowchart paradigm, although it is much more sophisticated. Visual Paradigm for UML is a professional tool that supports complete software lifecycle object-oriented analysis, object-oriented design, construction, testing and deployment. The UML modelling software helps to build quality applications faster and better. You can draw all types of class diagrams, reverse or generate code. It allows turning models into Java codes and Java codes into models. Graph theory is also helpful when building databases. Directed graphs (or digraphs) are a special case of graphs that constitute a powerful and convenient way of representing relationships between entities. In a digraph, entities are represented as nodes and relationships as directed lines or arrows that connect the nodes. The orientation of the arrows follows the flow of information in the digraph  ­. Digraphs offer a number of advantages to information visualization, with the most important of them being: comprehensibility the information that a digraph contains can be easily and accurately understood by humans and expressiveness- digraph topology bears non-trivial information. Case of graphical representation of logic rules, digraphs seem to be extremely appropriate. They can offer explanation of derived conclusions, since the series of inference steps in the graph can be easily detected and retraced. Also, by going backwards from the conclusion to the triggering conditions, on e can validate the truth of the inference result, gaining a means of proof visualization and validation. One of the examples can be found in the book â€Å"Automated Data Processing and Computations by David I. Donatoy. It is an example of geographic names database. An algorithm specifies how to quickly identify names that approximately match any specific name when searching the mentioned database. The algorithm identifies matching names by applying an artificial measure of name simplicity. A digraph index enables computer name searches that are carried out within this technique to be fast enough for Web application. The use of digraph index enables name search application to restrict comparisons to a small subset of the database name, speeding up processing. A digraph index lists in digraph sequence all digraphs found in the database of geo ­graphic names. The entry for a particular digraph consists of a set of pointers to all names in the geographic-names database that includes at least one occurrence of that digraph. Once the search-for name has itself been broken down into a list of its unique constituent digraphs, the digraph index can then be used to produce a candidate list containing only those names from the database that include at least one of the digraphs found in the search-for name. In most cases, several names in the candidate list will be referenced more than once (by different digraphs). After sorting the list of can ­didate names (thus, bringing together all occurrences of each particular candidate name), the number of occurrences of each candidate name can be counted. The number of occurrences of a candidate name will be the same as the number of unique digraphs a candidate name has in common with the search-for nam e. This number can be regarded as a first-approximation measure of a names similarity to the search-for name, with larger numbers corresponding to stronger similarity. Computer scientists have developed a great deal of theory about graphs and operations on them. One reason for this is because graphs can be used to represent many problems in computer science that are otherwise abstract. Finding a way to represent the solution to a problem as a graph can present new approaches to solving the problem or even lead directly to a solution derived from graph theory. This sort of technique is often used when discussing algorithmic efficiency and when trying to prove that a certain algorithm is NP-Complete; because many problems involving graphs, such as finding the shortest path to traverse all nodes (the Travelling Salesman Problem), are NP-Complete, if you can find a way to represent a problem as a graph and show that it is analogous to one of the other NP-Complete problems, then you can show the problem you are trying to solve is also NP-Complete, which gives you a hint that the solution will take a great deal of time. Another reason for using graphs is that many problems computers are used to solve involve representing relationships between objects, places, or concepts. Because graphs can be either directed or undirected, they are a flexible method of showing connections. For instance, you can describe who knows who in a room as a collection of nodes, each representing a person, and directed edges, each representing that one person knows another. Because graphs are so often used and because they allow the representation of many problems in computer science, they are a convenient means of expressing problems with which many people are comfortable. This familiarity simplifies the process of creating mental models of problems, which ultimately leads to better problem solving. Because computer science is a young discipline, it played essential role in development of graph theory. Mathematics plays essential role in computer science, as its language defines the generic structures and proves properties of those structures. Computer systems can be very complex and it is very difficult to have a clear picture of all details and keep the overview of the whole system. Computer science has put lots of effort to develop mathematically based frameworks to model computer systems. References: Gibbons, Alan (1985), Algorithmic graph theory, Cambridge University Press http://www-leibniz.imag.fr/GRAPH/english/overview.html http://www.bookrags.com/research/flowchart-wcs/ Brent Daviduck† Introduction to Programming in C++: Algorithms,  Flowcharts and Pseudocode† Narsingh Deo â€Å"Graph theory with applications to engineering and computer science†2004 An augmented directed graph base for application development Dan C. Clarke , 1982 Knoxville, Tennessee David I. Donato â€Å"Fast, Inclusive Searches for Geographic Names Using Digraphs† Chapter 1 of Book 7, Automated Data Processing and Computations, Section A, Algorithms, page 2-3 Quentin Charatan Aaron Kans â€Å"Java in two semesters†, The McGraw Hill, 2006, page 4-7 Seymour Lipschutz â€Å"Essential computer mathematics†, McGraw Hill 1987, page 95-107