Graph theory

Introduction

Graph theory is a branch of mathematics that studies 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 (or arcs or lines).

History

The paper written by Euler on the Seven Bridges of Königsberg and published in 1736 is regarded as the first paper in the history of graph theory. This paper, along with the work of Cauchy and Fermat, gave birth to topology.

A historical town with seven bridges crossing a river.

Definitions and Concepts

In graph theory, a graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes together with a set E of edges or arcs. Each edge is a 2-element subset of V. The vertex set of G is denoted V(G), or V if there is no ambiguity. The edge set of G is denoted E(G), or E if there is no ambiguity.

Types of Graphs

Graphs can be categorized in different ways:

Undirected Graph: An undirected graph is a graph in which edges have no orientation. The edge (x, y) is identical to the edge (y, x), i.e., they are not ordered pairs, but sets {x, y} of vertices.

Directed Graph or Digraph: A directed graph or digraph is a graph in which edges have orientations.

Weighted Graph: A weighted graph is a graph in which each edge is assigned a numerical value or weight.

Cyclic Graph: A cyclic graph is a graph containing at least one graph cycle.

Acyclic Graph: An acyclic graph is a graph with no graph cycles. A tree is an example of an acyclic graph.

Complete Graph: A complete graph is a graph in which each pair of graph vertices is connected by an edge.

Regular Graph: A regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree.

Subgraph: A subgraph is a portion of a graph, which includes some of the vertices and some (or possibly all) of the edges that connect them.

Graph Properties and Measures

Graphs have several properties and measures which are used to define the characteristics of graphs or to compare different graphs. They include:

Degree: The degree of a vertex is the number of edges that connect to it. In an undirected graph, the degree of a vertex v is denoted deg(v).

Path: A path is a sequence of edges that connects a sequence of vertices.

Cycle: A cycle is a path that starts and ends at the same vertex.

Connectedness: A graph is connected if there is a path from any vertex to any other vertex.

Clustering Coefficient: The clustering coefficient of a vertex in a graph quantifies how close its neighbours are to being a complete graph.

Centrality: Centrality measures identify the most important vertices within a graph. Examples of centrality measures include betweenness centrality, closeness centrality, eigenvector centrality, alpha centrality, and degree centrality.

Graph Theory Applications

Graph theory is used in many fields including computer science, physics, sociology, chemistry and operations research. Some of the applications of graph theory are:

Computer Science: Graph theory is used for the study of algorithms like Dijkstra’s algorithm for finding the shortest path in a graph. Other algorithms explored in graph theory include the Kruskal’s algorithm and the Prim’s algorithm.

Physics: Graph theory is used in physics to solve many problems, including the analysis of molecular structure in chemistry.

Social Sciences: In social networks, graph theory is used to measure individuals' prestige or to identify opinion leaders, or to explore rumor spreading, notably through the use of social network analysis software.

Operational Research: Graph theory is used in modeling and solving problems in areas like logistics, where the problem of routing is significant.