Definition
Graph theory is the study of mathematical objects known as graphs, which consist of vertices (or nodes) connected by edges. (In the figure below, the vertices are the numbered circles, and the edges join the vertices.)
Any scenario in which one wishes to examine the structure of a network of connected objects is potentially a problem for graph theory. Examples of graph theory frequently arise not only in mathematics but also in physics and computer science. 2
Who
See examples of who uses graph theory in the What section below.
What
Computer Science
The branch of computer science known as data structures uses graphs to represent networks of communication, data organization, computational devices, the flow of computation, etc. For instance, the link structure of a website can be represented by a directed graph, in which the vertices represent web pages and directed edges represent links from one page to another. A similar approach can be taken to problems in social media, travel, biology, computer chip design, mapping the progression of neuro-degenerative diseases, and many other fields. The development of algorithms to handle graphs is therefore of major interest in computer science. The transformation of graphs is often formalized and represented by graph rewrite systems. Complementary to graph transformation systems focusing on rule-based in-memory manipulation of graphs are graph databases geared towards transaction-safe, persistent storing and querying of graph-structured data.
Linguistics
Graph-theoretic methods, in various forms, have proven particularly useful in linguistics, since natural language often lends itself well to discrete structure. Traditionally, syntax and compositional semantics follow tree-based structures, whose expressive power lies in the principle of compositionality, modeled in a hierarchical graph. More contemporary approaches such as head-driven phrase structure grammar model the syntax of natural language using typed feature structures, which are directed acyclic graphs. Within lexical semantics, especially as applied to computers, modeling word meaning is easier when a given word is understood in terms of related words; semantic networks are therefore important in computational linguistics. Still, other methods in phonology (e.g. optimality theory, which uses lattice graphs) and morphology (e.g. finite-state morphology, using finite-state transducers) are common in the analysis of language as a graph. Indeed, the usefulness of this area of mathematics to linguistics has borne organizations such as TextGraphs, as well as various ‘Net’ projects, such as WordNet, VerbNet, and others.
Physics and Chemistry
Graph theory is also used to study molecules in chemistry and physics. In condensed matter physics, the three-dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms. Also, “the Feynman graphs and rules of calculation summarize quantum field theory in a form in close contact with the experimental numbers one wants to understand.” In chemistry a graph makes a natural model for a molecule, where vertices represent atoms and edges bonds. This approach is especially used in computer processing of molecular structures, ranging from chemical editors to database searching. In statistical physics, graphs can represent local connections between interacting parts of a system, as well as the dynamics of a physical process on such systems. Similarly, in computational neuroscience graphs can be used to represent functional connections between brain areas that interact to give rise to various cognitive processes, where the vertices represent different areas of the brain and the edges represent the connections between those areas. Graph theory plays an important role in electrical modeling of electrical networks, here, weights are associated with resistance of the wire segments to obtain electrical properties of network structures. Graphs are also used to represent the micro-scale channels of porous media, in which the vertices represent the pores and the edges represent the smaller channels connecting the pores. Chemical graph theory uses the molecular graph as a means to model molecules. Graphs and networks are excellent models to study and understand phase transitions and critical phenomena. Removal of nodes or edges leads to a critical transition where the network breaks into small clusters which is studied as a phase transition. This breakdown is studied via percolation theory.
Social Sciences
Graph theory in sociology: Moreno Sociogram (1953).
Graph theory is also widely used in sociology as a way, for example, to measure actors’ prestige or to explore rumor spreading, notably through the use of social network analysis software. Under the umbrella of social networks are many different types of graphs. Acquaintanceship and friendship graphs describe whether people know each other. Influence graphs model whether certain people can influence the behavior of others. Finally, collaboration graphs model whether two people work together in a particular way, such as acting in a movie together.
Biology
Likewise, graph theory is useful in biology and conservation efforts where a vertex can represent regions where certain species exist (or inhabit) and the edges represent migration paths or movement between the regions. This information is important when looking at breeding patterns or tracking the spread of disease, parasites or how changes to the movement can affect other species.
Graphs are also commonly used in molecular biology and genomics to model and analyse datasets with complex relationships. For example, graph-based methods are often used to ‘cluster’ cells together into cell-types in single-cell transcriptome analysis. Another use is to model genes or proteins in a pathway and study the relationships between them, such as metabolic pathways and gene regulatory networks. Evolutionary trees, ecological networks, and hierarchical clustering of gene expression patterns are also represented as graph structures.
Graph theory is also used in connectomics; nervous systems can be seen as a graph, where the nodes are neurons and the edges are the connections between them.
Mathematics
In mathematics, graphs are useful in geometry and certain parts of topology such as knot theory. Algebraic graph theory has close links with group theory. Algebraic graph theory has been applied to many areas including dynamic systems and complexity.
Transportation
The link between Leonhard Euler and graphs comes from the solution that he presented in 1735 to the problem known as The Seven Bridges of Königsberg. Kóningsberg, a merchant city in the Pregel River, was the capital of Eastern Prussia (now Kaliningrad, Russia). The abstraction of a city as a graph help us map the different types of transportation infrastructure into a multiplex network, in which each layer is transportation infrastructure, take for example the above video, in which Manhattan is mapped into a multiplex network, with their pedestrian, bike, subway and street infrastructure. Using this abstraction we can study problems such as how to improve bicycle connectivity, identify underserved areas of a city and their quality of life. 3
BBC Radio 4 Extra – A Brief History Of Mathematics, Leonard Euler
Other Topics
A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights, or weighted graphs, are used to represent structures in which pairwise connections have some numerical values. For example, if a graph represents a road network, the weights could represent the length of each road. There may be several weights associated with each edge, including distance (as in the previous example), travel time, or monetary cost. Such weighted graphs are commonly used to program GPS’s, and travel-planning search engines that compare flight times and costs.
Why
Note what Wikipedia mentions about the application of graph theory. 1
Graphs can be used to model many types of relations and processes in physical, biological, social and information systems. Many practical problems can be represented by graphs. Emphasizing their application to real-world systems, the term network is sometimes defined to mean a graph in which attributes (e.g. names) are associated with the vertices and edges, and the subject that expresses and understands real-world systems as a network is called network science.
See Theoretical Knowledge Vs Practical Application.
How
Many of the References and Additional Reading websites and Videos will assist you with understanding and applying graph theory.
As some professors say: “It is intuitively obvious to even the most casual observer.“
References
1 “Graph Theory – Wikipedia”. 2022. en.wikipedia.org. https://en.wikipedia.org/wiki/Graph_theory.
2 “Graph Theory | Brilliant Math & Science Wiki”. 2022. brilliant.org. https://brilliant.org/wiki/graph-theory/.
3 Luis Natera, Ph.D. 2020. “Leonhard Euler And Graph Theory”. Luis Natera, Ph.D. https://luisnatera.com/posts/2020/04/Euler/.
Additional Reading
Flovik, Vegard. “What Is Graph Theory, And Why Should You Care?” 2020. Medium. https://towardsdatascience.com/what-is-graph-theory-and-why-should-you-care-28d6a715a5c2.
“Graph Theory”. 2022. play.google.com. https://play.google.com/store/apps/details?id=com.faadooengineers.free_graphtheory.
The app is a complete free handbook of Graph Theory which covers important topics, notes, materials & news on the course. Download the App as a reference material & digital book for Computer science engineering, IT, software engineering programs & Mathematics & Combinatorial Theory degree courses. This useful App lists 100 topics with detailed notes, diagrams, equations, formulas & course material, the topics are listed in 5 chapters. The app is must have for all the engineering science students & professionals.
“Graph Theory: Definitions For Common Terms”. 2017. Statistics How To. https://www.statisticshowto.com/graph-theory/.
Graph Theory is the study of lines and points. It is a sub-field of mathematics which deals with graphs: diagrams that involve points and lines and which often pictorially represent mathematical truths. Graph theory is the study of the relationship between edges and vertices.
“Graph Theory Tutorial”. 2022. tutorialspoint.com. https://www.tutorialspoint.com/graph_theory/index.htm.
“Graph Theory — History & Overview”. 2023. setzeus.com. https://www.setzeus.com/community-blog-posts/graph-theory-history-overview.
“Graph Theory — Set & Matrix Notation”. 2023. setzeus.com. https://www.setzeus.com/community-blog-posts/graph-theory-set-matrix-notation.
“Graph Theory — Basic Properties”. 2023. setzeus.com. https://www.setzeus.com/community-blog-posts/graph-theory-basic-properties.
“Graph Theory — On To Network Theory”. 2023. setzeus.com. https://www.setzeus.com/community-blog-posts/graph-theory-on-to-network-theory.
Joshi, Vaidehi. “A Gentle Introduction To Graph Theory”. 2017. Medium. https://medium.com/basecs/a-gentle-introduction-to-graph-theory-77969829ead8.
Graph theory might sound like an intimidating and abstract topic to you, so why should you even spend your time reading an article about it? However, although it might not sound very applicable, there are actually an abundance of useful and important applications of graph theory! In this article, I will try to explain briefly what some of these applications are. In doing so, I will do my best to convince you that having at least some basic knowledge of this topic can be useful in solving some interesting problems you might come across.
Honner, Patrick. “What a Math Party Game Tells Us About Graph Theory”. 2022. Quanta Magazine. https://www.quantamagazine.org/what-a-math-party-game-tells-us-about-graph-theory-20220324/.
“Mathematics | Graph Theory Basics – Set 1 – GeeksForGeeks”. 2018. GeeksForGeeks. https://www.geeksforgeeks.org/mathematics-graph-theory-basics-set-1/.
McNulty, Keith. “Graph Theory And The Great London Stink of 1858”. 2023. Medium. https://keith-mcnulty.medium.com/graph-theory-and-the-great-london-stink-of-1858-f1f3f31d8d63.
It was the beginning of what became known as the Great Stink of 1858. The River Thames, full to the brim with centuries of human waste that had been dumped directly from the medieval wooden sewer system, was finally getting its revenge. Washed up onto the banks of the river, the cholera-ridden sludge basked in the unusually hot summer temperatures and formed a miasmic stench that was inescapable for miles.
Joseph Bazalgette’s feat of engineering is an example of some of the first uses of the emerging field of graph theory, and illustrated the importance of two concepts which we look at all the time today in relation to networks: distance between vertices and the importance of vertices.
Bazalgette’s sewer network is still going strong, carrying the waste of millions of people eastwards to processing facilities towards the mouth of the Thames. As an engineering project, it was an astounding example of human endeavor: 22,000 kilometers of sewers, 318 million bricks, 2.7 million cubic meters of excavated earth.
Pickard, Joshua. “Graph Theory: Euler’s Formula for Planar Graphs”. 2022. Medium. https://medium.com/math-simplified/graph-theory-eulers-theorem-for-planar-graphs-2076bbdb59be.
Safan. “Introduction To Graph Theory!” 2022. Medium. https://medium.com/math-simplified/introduction-to-graph-theory-ebe4f30677c4.
We have met graphs many times. A better name for “graph” would be “network”. Graphs describe the connectedness, for example, transport systems, communication systems, computer networks, islands with bridges and many more.
Sumba, Xavier. “Graph Theory”. 2019. Medium. https://towardsdatascience.com/graph-theory-132122ac38f2.
Recently, graphs have attracted a plethora of attention by the machine learning community. Graphs can represent many complex systems such as social networks, protein-protein interaction networks, knowledge graphs, citations, Internet, etc. These are examples of information that operate in the non-Euclidean space but even images and text are special graphs that operate in the Euclidean space.
⭐Tech Wise. “Introduction to Graph Theory”. 2023. Medium. https://medium.com/@TechWise/introduction-to-graph-theory-974020df1772.
Join me on this exciting journey as we unravel the mysteries of graphs and their immense potential. Whether you’re a student, a researcher, industry specialist or simply curious about the world of graphs, this blog will provide you with valuable insights, practical knowledge, and inspire you to leverage the power of graphs in your own endeavors.
Tech Wise. “Graph Theory 1.2: Special Graphs”. 2023. Medium. https://medium.com/@TechWise/graph-theory-1-2-special-graphs-452768ea5d49.
In this article, we will dive into the field of graph theory and delve into the intricacies of special graph structures. We will discuss a variety of special graphs, such as the complete graph, path graph, cycle graph, and more.
Tech Wise. “Demystifying Graph Theory: Key Concepts And Properties”. 2023. Medium. https://medium.com/@TechWise/demystifying-graph-theory-key-concepts-and-properties-edf74ad6733b.
Welcome to this blog post where we delve into the fundamental concepts of graph theory. We will revisit the definition of a graph and explore essential elements such as loops, edges, and the intriguing realm of simple graphs. By understanding these core concepts, we gain insights into the underlying structures that shape complex systems.
Videos
This video gives an overview of the mathematical definition of a graph. It gives some basic examples and some motivation about why to study graph theory.
In mathematics, graph #theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A #graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph (discrete mathematics) for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.
In this video, I introduce the field of graph theory. We first answer the important question of why someone should even care about studying graph theory through an application perspective. Afterwards, we introduce definitions and essential terminology in graph theory, followed by a discussion of the types of graphs you may encounter. We then define several ways to represent graphs as a data structure and finish off the video with a discussion of what types of interesting problems you can ask about graphs to help motivate the ideas in future videos.
Typo correction: at 5:12 the vertex set V should be {0, 1, 2, 3, 4} instead of {0, 1, 2, 3, 4, 5} (there is no vertex 5).
Play this simple math game with your friends to gain insights into fundamental principles of graph theory.
What is a graph? A graph theory graph, in particular, is the subject of discussion today. In graph theory, a graph is an ordered pair consisting of a vertex set, then an edge set. Graphs are often represented as diagrams, with dots representing vertices, and lines representing edges. Each edge joins two vertices, so the lines in the diagram of a graph will go from one vertex to one other vertex. Thus, the edge set of a graph consists of two-element-subsets of the vertex set, because in a simple graph, each edge is entirely defined by the vertices it joins. Oh by the way, we’re only talking about simple graphs, which are the most well-studied types of graphs in graph theory, and are usually just called graphs. Among other restrictions, simple graphs don’t allow for loops, multi-edges, or directed edges. We talk more about these restrictions in the video.
⭐ I suggest that you read the entire reference. Other references can be read in their entirety but I leave that up to you.
Medium Members Only.
The featured image on this page is from the blog Graph Theory — Set & Matrix Notation.
Mathematical Mysteries 