24 November 2020

Graph Theory II

"Graph theory is often under attack, and so are its practitioners. We are accused of being shallow, knowing and using no real mathematics, and tackling problems of little interest, whose solutions are easy if not trivial. Although these criticisms are usually made by people unsympathetic to everything combinatorial, there is a grain of truth in these accusations - perhaps even more than a grain. In graph theory we do write too many papers, sometimes we do tackle problems that are too easy, and we have a tendency to become wrapped up in our circle of ideas and problems, unconcerned about the rest of mathematics. However, I am convinced that these are mostly teething problems." (Béla Bollobás, "The Future of Graph Theory", [in "Quo Vadis, Graph Theory?"] 1993)

"The four-color map theorem is an assertion about graph theory, which is the study of discrete points and the lines that connect them; each point is called a vertex and each line is called an edge." (Alexander Humez et al, "Zero to Lazy Eight: The romance of numbers", 1993)

"Perhaps the greatest strength of graph theory is the abundance of natural and beautiful problems waiting to be solved. […] Paradoxically, much of what is wrong with graph theory is due to this richness of problems. It is all too easy to find new problems based on no theory whatsoever, and to solve the first few cases by straightforward methods. Unfortunately, in some instances the problems are unlikely to lead anywhere […]" (Béla Bollobás, "The Future of Graph Theory", [in "Quo Vadis, Graph Theory?"] 1993)

"Graphs are one of the unifying themes of computer science - an abstract representation that describes the organization of transportation systems, human interactions, and telecommunication networks. That so many different structures can be modeled using a single formalism is a source of great power to the educated programmer." (Steven S Skiena, "The Algorithm Design Manual", 1997)

"A graph in mathematics is a set of nodes and a set of edges between pairs of those nodes; the edges are ordered or nonordered pairs, or a relation, that defines the pairs of nodes for which the relation being examined is valid. […] The edges can either be undirected or directed; directed edges depict a relation that requires the nodes to be ordered while an undirected edge defines a relation in which no ordering of the edges is implied." (Dennis M Buede, "The Engineering Design of Systems: Models and methods", 2009)

"A graph enables us to visualize a relation over a set, which makes the characteristics of relations such as transitivity and symmetry easier to understand. […] Notions such as paths and cycles are key to understanding the more complex and powerful concepts of graph theory. There are many degrees of connectedness that apply to a graph; understanding these types of connectedness enables the engineer to understand the basic properties that can be defined for the graph representing some aspect of his or her system. The concepts of adjacency and reachability are the first steps to understanding the ability of an allocated architecture of a system to execute properly." (Dennis M Buede, "The Engineering Design of Systems: Models and methods", 2009)

"First, what are the 'graphs' studied in graph theory? They are not graphs of functions as studied in calculus and analytic geometry. They are (usually finite) structures consisting of vertices and edges. As in geometry, we can think of vertices as points (but they are denoted by thick dots in diagrams) and of edges as arcs connecting pairs of distinct vertices. The positions of the vertices and the shapes of the edges are irrelevant: the graph is completely specified by saying which vertices are connected by edges. A common convention is that at most one edge connects a given pair of vertices, so a graph is essentially just a pair of sets: a set of objects." (John Stillwell, "Mathematics and Its History", 2010)

"Infinite reasoning is likewise essential for graph theory. The field had its origins in topology, and it is still relevant there, but it has expanded extraordinarily far in other directions. Graph theory today is exploring the boundaries of finite provability first exposed by Gödel’s incompleteness theorem." (John Stillwell, "Mathematics and Its History", 2010)

"The most naive branch of combinatorics is graph theory, a subject that is visual and easily grasped, yet rich in connections with other parts of mathematics." (John Stillwell, "Mathematics and Its History", 2010)

"Graphs are among the most important abstract data structures in computer science, and the algorithms that operate on them are critical to modern life. Graphs have been shown to be powerful tools for modeling complex problems because of their simplicity and generality." (Jeremy Kepner & John Gilbert [Eds],"Graph Algorithms in the Language of Linear Algebra", 2011)

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...

A Picture's Worth

"The drawing shows me at a glance what would be spread over ten pages in a book." (Ivan Turgenev, 1862) [2] "Sometimes, half ...