So many things in the world would have never come to existence if there hadn’t been a problem that needed solving. Someone needed to keep track of the order of things and created different data structures, someone else needed a good way of representing data so they played around with a different numbers of systems, etc. Of course, computer science isn’t the only field to innovate and build upon what came before it, but I do think that it’s unique in one way: computer science’s innovations rely on and build upon its abstractions.
Graph theory and the idea of topology was first described by the Swiss mathematician Leonard Euler as applied to the problem of the seven bridges of Königsberg. Königsberg consisted of four islands connected by seven bridges (See figure). No one had ever found a path that visited all four islands and crossed each of the seven bridges only once. Naturally, people assumed that no such path existed, but there was no mathematical proof of this.
Euler showed that to solve the problem, only the relations between the landmasses are relevant, not the shape or actual distances on the map. These relationships can be represented in the form of a graph where the landmasses are the nodes and the bridges are the edges of the graph. Euler used this graph and its topological features to prove that the path did not exist.
Euler’s formulation of this problem provided the basis of a whole area of mathematics and it is the foundation of all the tools and concepts we will come across in the field of graph theory.
Computer science loves to borrow stuff. More specifically, it has borrowed a lot of concepts from logic and mathematics. As it turns out, this is the case with graphs. In mathematics, graphs are a way to formally represent a network, which is just a collection of objects that are all interconnected.
The graph is a set of points in a plane or in a space and a set of a line segment of the curve each of which either joins two points or join to itself. Wikipedia defines graph theory as the study of graphs, which are mathematical structures used to model pairwise relations between objects.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices. Look at the following graph:
Applications of Graph Theory
- Electrical Engineering − The concepts of graph theory is used extensively in designing circuit connections.
- Computer Science − Graph theory is used for the study of algorithms.
- Computer Networks − The relationships among interconnected computers in the network follow the principles of graph theory.
- Science − The molecular structure and chemical structure of a substance, the DNA structure of an organism, etc., are represented by graphs.
- Linguistics − The parsing tree of a language and grammar of a language uses graphs.
- General − Routes between the cities can be represented using graphs.
Common Graph Theory Terms
Vertices
A vertex, sometimes called a node, is a point or circle. It is the fundamental unit from which graphs are made. For graph theory, vertices are treated as featureless and indivisible objects, although they may have additional structure depending on the application from which the graph arises.
Edges
An edge is (together with vertices) one of the two basic units out of which graphs are constructed. Each edge has two (or in hypergraphs, more) vertices to which it is attached, called its endpoints. Edges may be directed or undirected; undirected edges are also called lines and directed edges are also called arcs or arrows.
Parallel edges
In a graph, if a pair of vertices is connected by more than one edge, then those edges are called parallel edges.
Self-loops
In a graph, if an edge is drawn from the vertex to itself, it is called a loop.
Walks
A walk is a finite or infinite sequence of edges which joins a sequence of vertices. Walks are also sometimes called chains. A walk is open if its first and last vertices are distinct, and closed if they are repeated.
Trails
A trail is a walk in which all edges are distinct.
Paths
A path is a trail in which all vertices (and therefore also all edges) are distinct.
Graph Isomorphism
A graph isomorphism is a one-to-one incidence preserving correspondence of the vertices and edges of one graph to the vertices and edges of another graph. Two graphs related in this way are said to be isomorphic.
Both the below graphs are isomorphic to one another.
Types of Graph
Acyclic Graphs
A graph not containing any cycle in it is called as an acyclic graph.
Cyclic Graphs
A graph containing at least one cycle in it is called an acyclic graph.
Complete Graphs
A graph in which exactly one edge is present between every pair of vertices is called a complete graph.
Random Graphs
A random graph is a graph where nodes or edges or both are created by some random procedure. Random graphs may be described simply by a probability distribution, or by a random process which generates them.
Directed Graphs
A graph in which all the edges are directed is called a directed graph. In other words, all the edges of a directed graph contain some direction. Directed graphs are also called as digraphs.
Undirected Graphs
A graph in which all the edges are undirected is called as a non-directed graph. In other words, the edges of an undirected graph do not contain any direction.
Special Case of Graph: Tree
In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path.
Trees come up everywhere like when analyzing games or representing family relationships etc.
Thank You