Mathematics
Graph Theory
Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures used to model pairwise relations between objects. It involves the exploration of properties and applications of graphs, such as paths, cycles, connectivity, and coloring. Graph theory has applications in various fields including computer science, operations research, and social network analysis.
Written by Perlego with AI-assistance
Related key terms
1 of 5
11 Key excerpts on "Graph Theory"
eBook - PDFComplex Networks
Principles, Methods and Applications
- Vito Latora, Vincenzo Nicosia, Giovanni Russo(Authors)
- 2017(Publication Date)
- Cambridge University Press(Publisher)
1 Graphs and Graph Theory Graphs are the mathematical objects used to represent networks, and Graph Theory is the branch of mathematics that deals with the study of graphs. Graph Theory has a long his- tory. The notion of the graph was introduced for the first time in 1763 by Euler, to settle a famous unsolved problem of his time: the so-called Königsberg bridge problem. It is no coincidence that the first paper on Graph Theory arose from the need to solve a problem from the real world. Also subsequent work in Graph Theory by Kirchhoff and Cayley had its root in the physical world. For instance, Kirchhoff’s investigations into electric circuits led to his development of a set of basic concepts and theorems concerning trees in graphs. Nowa- days, Graph Theory is a well-established discipline which is commonly used in areas as diverse as computer science, sociology and biology. To give some examples, Graph Theory helps us to schedule airplane routing and has solved problems such as finding the max- imum flow per unit time from a source to a sink in a network of pipes, or colouring the regions of a map using the minimum number of different colours so that no neighbouring regions are coloured the same way. In this chapter we introduce the basic definitions, set- ting up the language we will need in the rest of the book. We also present the first data set of a real network in this book, namely Elisa’s kindergarten network. The two final sections are devoted to, respectively, the proof of the Euler theorem and the description of a graph as an array of numbers. 1.1 What Is a Graph? The natural framework for the exact mathematical treatment of a complex network is a branch of discrete mathematics known as Graph Theory [48, 47, 313, 150, 272, 144]. Dis- crete mathematics, also called finite mathematics, is the study of mathematical structures that are fundamentally discrete, i.e. made up of distinct parts, not supporting or requiring the notion of continuity.
eBook - PDF- Yogesh Singh(Author)
- 2011(Publication Date)
- Cambridge University Press(Publisher)
3 Essentials of Graph Theory Graph Theory has been used extensively in computer science, electrical engineering, communication systems, operational research, economics, physics and many other areas. Any physical situation involving discrete objects may be represented by a graph along with their relationships amongst them. In practice, there are numerous applications of graphs in modern science and technology. Graph Theory has recently been used for representing the connectivity of the World Wide Web. Global internet connectivity issues are studied using graphs like the number of links required to move from one web page to another and the links which are used to establish this connectivity. It has also provided many ways to test a program. Some testing techniques are available which are based on the concepts of Graph Theory. 3.1 WHAT IS A GRAPH? A graph has a set of nodes and a set of edges that connect these nodes. A graph G = (V, E) consists of a non-empty finite set V of nodes and a set E of edges containing ordered or unordered pairs of nodes. V = (n 1 , n 2 , n 3 ……..n m ) and E = (e 1 , e 2 , e 3 ………e k ) If an edge e i E is associated with an ordered pair or an unordered pair (n i , n j ), where n i , n j V, then the e i is said to connect the nodes n i and n j . The edge e i that connects the node n i and n j is called incident on each of the nodes. The pair of nodes that are connected by an edge are called adjacent nodes. A node, which is not connected to any other node, is called an isolated node. A graph with only isolated nodes is known as null graph. If in graph G = (V, E), each edge e i E is associated with an ordered pair of nodes, then graph G is called a directed graph or digraph. If each edge is associated with an unordered pair of nodes, then a graph G is called an undirected graph.
eBook - PDF- Peter Grossman(Author)
- 2017(Publication Date)
- Red Globe Press(Publisher)
Introduction to Graph Theory 10.1 What is a graph? The objects that we study in the branch of mathematics known as Graph Theory are not graphs drawn with x and y axes. In this chapter, the word ‘graph’ refers to a structure consisting of points (called ‘vertices’), some of which may be joined to other vertices by lines (called ‘edges’) to form a network. Structures of this type abound in computing. The computers on a site may be connected into a local area network, which in turn may be linked to wider networks, including the Internet. The circuitry inside a computer (which we represented schematically by digital circuit diagrams in Chapter 8) provides another example of a graph or network structure. At a more abstract level, we saw in Chapter 5 how a relation on a set can be depicted using a diagram that takes the form of a graph. There is a particular type of graph called a tree , which we will study in Chapter 11. Trees are used in computing to represent the structure of expressions; we saw an example of a logical expression tree in Chapter 4. Trees can also be used to represent decision processes, in which we are faced with two or more choices at each step of a procedure; the tree diagrams in Chapter 9 were of this type. In this chapter, we introduce graphs, study their basic properties, and investigate some practical problems in which they can be applied. In Chapter 11, we will study trees and investigate some of their applications to computing. 10.2 Basic concepts in Graph Theory Definition A graph consists of a non-empty set of points, called vertices (singular: vertex ), and a set of lines or curves, called edges , such that every edge is attached at each end to a vertex. 180 CHAPTER 10 An example of a graph is shown in Figure 10.1, with the edges and vertices labelled. An edge is said to be incident to the vertices to which it is attached. For example, the edge e 1 is incident to the vertices v 1 and v 2 in the graph in Figure 10.1.
eBook - PDF- Owen D. Byer, Deirdre L. Smeltzer, Kenneth L. Wantz(Authors)
- 2018(Publication Date)
- American Mathematical Society(Publisher)
9 Graph Theory Thus you see, most noble Sir, how this type of solution to the Königsberg bridge problem bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle .... —Leonhard Euler (1707–1783) In “continuous” mathematics such as algebra, trigonometry, and calculus, a graph is often defined to be the set of ordered pairs that satisfy an equation. Less formally, a graph can refer to the visual representation obtained by plotting the ordered pairs in a Cartesian plane. Graphs have proven to be robust, yet straightforward, mechanisms for representing and organizing complex relationships. For example, graphs may dis-play two-way transit between locations, such as cities, intersections, airports, or net-work nodes, via bridges, flights, or network connections. In other applications, graphs may represent relationships—similarities or differences—between people, products, or characteristics. Graphs are simply examples of relations as defined in Chapter 5. The distinctive nature of “discrete” graphs can be illustrated by the digraphs (short for directed graphs) defined in Section 5.1. For a relation ? on a set ? , each element of ? is indicated by a labeled point (or vertex); the ordered pair (?, ?) ∈ ? , for ?, ? ∈ ? , is represented by an edge drawn from ? to ? . Also recall that if ? is a symmetric relation, whenever there is an edge from ? to ? , there must also be an edge from ? to ? . For graphs of these symmetric relations, we replace each “double edge” with a single undirected arc or line segment. In discrete mathematics, a graph will always refer to the visual representation of the symmetric relation just described. 211 212 Chapter 9 Graph Theory 9.1 The Language of Graphs Graph Theory provides tools to sort and analyze the connections between items and collections of items.
eBook - PDF- Ivan Stanimirovic(Author)
- 2019(Publication Date)
- Arcler Press(Publisher)
Thanks to Graph Theory, various problems can be solved, such as the synthesis of the circuit’s sequential counters or opening systems. It is used for various areas such as computer drawing, in all fields of engineering. Graphs are also used to model paths such as a bus through the streets of a city, where we can get optimal paths for applying different path algorithms such as the algorithm Floyd. For project management, we use techniques such as technical (PERT), in which we are using graphs and optimizing time to realize their modeling. Applications of Graph Theory 6 Graph Theory has also served as inspiration for the social sciences, especially to develop a non-metaphorical concept social replacing nodes by social actors and verifies the position, centrality, and importance of each actor within the network. This measure allows to quantify and abstracting complex relationships, so the social structure can be represented graphically. For example, a social network can represent the structure of power within a society by identifying the links (edges), its direction and intensity and suggests the way in which power is transmitted and to whom. It is used in production control problems, to design computer networks, for designing modern electronic modules and project physical parameters localized systems (mechanical, acoustic, and electric). It is used for troubleshooting problems genetic and automation projection (EWRS). Mathematical support of modern systems for information processing. Comes in nuclear (the technique of Feynman diagrams) research. Graphs are important in the study of biology and habitat. The apex represents a habitat and edges (or “edges”) represents the animal trails or migration. With this information, scientists can understand how this can change or affect species in their habitat. 1.1.1. Types of Graphs • Simple Graph: Simple graph or simply graph is one that accepts a single edge connecting two vertices any.
eBook - PDF- Alexander Kheyfits(Author)
- 2010(Publication Date)
- De Gruyter(Publisher)
Chapter 2 Basic Graph Theory Graphs and, in particular, trees are graphical mathematical models useful in many problems. This chapter is devoted to a brief introduction to the Graph Theory. The first two sections introduce the vocabulary. Graphs are defined in terms of sets and mappings in the spirit of Section 1.1, but we soon resort to more intuitive and transparent language of geometric diagrams. In the next three sections we study important special classes of graphs – trees, planar graphs, Eulerian graphs, and use the methods and results of Chapter 1 to solve some problems of graphical enumeration. More such problems are considered in Chapters 4 and 5. Our exposition was strongly influenced by Wilson’s beautiful book [48]. For a deeper study of the subject we recommend the course of B. Bollobás [8]; we mostly follow the latter in terminology. 2.1 Vocabulary In this section we create the basic vocabulary of the Graph Theory and consider elementary properties of graphs. Recall that 2 V 2 denotes the set of all two-element subsets of a set V .
eBook - PDF- Alberto D. Yazon(Author)
- 2019(Publication Date)
- Arcler Press(Publisher)
Graph Theory 6 CONTENTS 6.1. Introduction .................................................................................... 148 6.2. Links And Their Structures ............................................................... 152 6.3. Basic Structural Properties .............................................................. 153 6.4. Graph Theory Trees ......................................................................... 155 6.5. Graph Theory Application ............................................................... 159 6.6. A Graph—Theoretic Data Model For Genome Mapping Databases ....................................................... 171 6.7. Case Study: Applying Graph Theory To Interaction Design .............. 175 References ............................................................................................. 180 Fundamentals of Advanced Mathematics 148 This chapter discusses the Graph Theory in detail. It begins with the explanation of Graph Theory origin and other elements required to explain Graph Theory. It further describes a different type of links and basic structural properties like symmetry, root, tree, nodes, isthmus, etc. The chapter briefly discusses the Graph Theory trees and its type. It defines the Graph Theory application in terms of Cantor–Schröder–Bernstein Theorem, Fermat’s (Little) Theorem, The Nielson–Schreier Theorem, The SNP Assembly Problem, Computer Network Security, The Timetabling Problem, Map Coloring, and GSM Mobile Phone Networks and Knight’s Tours. The chapter ends with the graph-theoretic data model discussion for genome mapping database. 6.1. INTRODUCTION A graph symbolically represents network and connectivity. It signifies an abstraction of the reality, so it is basically a set of connected nodes.
eBook - PDFDiscrete Mathematics
Proofs, Structures and Applications, Third Edition
- Rowan Garnier, John Taylor(Authors)
- 2009(Publication Date)
- CRC Press(Publisher)
Chapter 11 Graph Theory 11.1 Definitions and Examples Although generally regarded as one of the more modern branches of mathematics, Graph Theory actually dates back to 1736. In that year Leonhard Euler † published the first paper on what is now called Graph Theory. In the paper, Euler developed a theory which solved the so-called K¨ onigsberg Bridge problem (see §11.2). Surely few other branches of the subject can be given as precise a ‘birthday’ as this. However, it must be said that, as a mature subject, Graph Theory is indeed modern. It came of age, so to speak, exactly 200 years after Euler’s paper with the publication in 1936 of the first text in Graph Theory. (The first 200 years of Graph Theory are beautifully outlined in Biggs et al (1976) which includes extracts from many of the original papers concerned with the development of Graph Theory.) Like many of the concepts we have considered, the idea of a graph is very simple. It is probably due to its simplicity that Graph Theory has found many applications in recent years in fields as diverse as chemistry, computer science, economics, electronics and linguistics. Before we begin by explaining what a graph is, perhaps we should say what it is not . The term ‘graph’ as used in this chapter and the next does not mean the graph of a function (considered in chapter 5). It is unfortunate that the same term has † Euler (1707–83) was born in Switzerland and spent most of his long life in Russia (St Petersburg) and Prussia (Berlin). He was the most prolific mathematician of all time, his collected works filling more than 70 volumes. Like many of the very great mathematicians of his era, Euler contributed to almost every branch of pure and applied mathematics. He is also responsible, more than any other person, for much of the mathematical notation in use today. 548 Definitions and Examples 549 two quite different meanings, although it is usually clear from the context which meaning is intended.
eBook - PDFGraphs
Theory and Algorithms
- K. Thulasiraman, M. N. S. Swamy(Authors)
- 2011(Publication Date)
- Wiley-Interscience(Publisher)
This page intentionally left blank PREFACE In the past two decades Graph Theory has come to stay as a powerful analytical tool in the understanding and solution of large complex problems that arise in the study of engineering, computer, and communication systems. While its origin is traced to Euler's solution in 1735 of the Konigsberg bridge problem, its first application to a problem in physical science did not occur until 1847, when Kirchhoff developed the theory of trees for its application in the study of electrical networks. The elegance with which the graph of an electrical network captures the structural relationships between the voltage and current variables of the network has led to equally elegant contributions to electrical network theory. One such condition is Tellegen's theorem, the application of which in the computation of network sensitivities is now well recognized. The theory of network flows developed by Ford and Fulkerson in 1956 was the first major application of Graph Theory to operations research. This theory provides the main link between Graph Theory and operations research and continues to be a fascinating topic of further research. Computer and communication systems are among the recent additions to the growing list of application areas of Graph Theory. Motivated by applications in the design of interconnection networks for these systems, in recent years there has been a great deal of interest in the design of graphs having specified topological properties such as distance, connectivity, and regularity. Fascinated by the challenges encountered in the design of efficient algorithms for graph problems, theoretical computer scientists have developed in the past two decades a large number of interesting and deep graph algorithms adding to the richness of Graph Theory. Theoretical computer scientists have also identified the class of graph problems for which efficient algorithms are not likely to xiii
No longer available |Learn moreEngineering Mathematics Exam Prep
Problems and Solutions
- A. Saha, D. Dutta, S. Kar, P. Majumder, A. Paul, S. Musa, PhD(Authors)
- 2023(Publication Date)
- Mercury Learning and Information(Publisher)
C H A P T E R 11 Graph Theory 11.1 GRAPHS 11.1.1 Definition of a Graph A graph G is an ordered pair (V, E) where ( ) V ¹ Æ (called the set of vertices or set of nodes) and E is called the set edges of the graph. Every graph can be represented by a diagram in which each vertex is represented by a point and each edge is represented by a straight line (or a curve). For e ∈ E, if e is an edge joining the vertices u and v, then we write e = (u, v). Example: Let V = {v 1 , v 2 , v 3 , v 4 }, E = {e 1 , e 2 , e 3 , e 4 } and e 1 = v 1 , v 2 e 2 = (v 2 , v 3 ), e 3 = (v 1 , v 4 ), e 4 = (v 3 , v 4 ). Then the graph G = (V, E) can be diagram- matically represented by v 2 e 2 v 3 v 4 e 4 e 3 v 1 e 1 Remember: (i) In any graph an edge should not pass through any vertices other than two end vertices of the edge. (ii) In a graph G = (V, E), the number of vertices is denoted by |V| or |V(G)|; and the number of edges is denoted by |E| or |E(G)|. (iii) In a graph G = (V, E) for e ∈ E and e = (u, v), we say that the vertices u and v are adjacent. In other words, any pair of ver- tices which are connected by an edge, are called adjacent vertices. Thus, in the previous example, the vertices v 1 and v 2 are adjacent, v 2 and v 3 are adjacent v 3 and v 4 are adjacent, v 1 and v 4 are adjacent. (iv) A graph G is said to be a finite if the set of vertices and the set of edges are finite. (v) A graph with “p” vertices and “q” edges is called a (p, q) graph. p is called the order of the graph and q is called the size of the graph. 11.1.2 Incidence In a graph G = (V, E), let e ∈ E and e = (u, v), i.e., e is an edge joining the vertices u and v. Then e is said to be incident with the vertices u and v. Example: Consider the following graph: v 3 e 2 v 2 e 1 v 1 e 3 Here e 1 is incident with v 1 and v 2 , e 2 is incident with v 2 and v 3 , and e 3 is incident with v 1 and v 3 .
eBook - PDFGraph Theory
Advanced Algorithms and Applications
- Beril Sirmacek(Author)
- 2018(Publication Date)
- IntechOpen(Publisher)
In geometry also there are diagrams but these diagrams are defined by their formulas. For instance, ellipse, hyperbola, etc. are defined by their formulas or how many geometrical units will comprise a given Figure 2. Sequential and harmonious bipartite tree where edges do not cross. Sequential and harmonious edge labels written on left and right, respectively, separated by a comma. Graph Theory - Advanced Algorithms and Applications 30 diagram is specified as in a triangle (three line segments and angles), square, etc. But trees are just defined as connected and acyclic and can be drawn in any way with no restrictions and nothing which can be measured or quantified resulting in infinite shapes rendering them suitable only for specialized results of particular kinds of trees and not generalized results. So far, the research in Mathematics has discounted how the mind influences the perceptions of looking at mathematical problems, formulating them, and going about solv -ing them. How mind and its perceptions influence viewing a mathematical problem, its formulation and solution could be an area of research which can be quite subjective but could yield interesting results when done more consciously. Ref. [ 1] which answers the graceful tree conjecture and Ref. [ 11] which finds that the definition of tree alone can not be the controlling factor in similar conjectures, both factor in the psychological conditioning in looking at a mathematical problem. From the rules of mathematical logic some of above mentioned ideas can be proved as follows: Theorem 2 : Definition of tree alone is not the controlling factor in assuming the graceful tree conjecture to be true. Figure 3. Sequential and felicitous bipartite tree where edges do not cross: Sequential and felicitous edge labels written on left and right, respectively, separated by a comma. An Example Usage of Graph Theory in Other Scientific Fields: On Graph Labeling, Possibilities and Role...
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
