View source for The Mathematics of Graph Theory and its Applications

== Introduction ==

[[Graph theory]] is a branch of [[mathematics]] that studies the properties and applications of graphs. A graph, in this context, is a collection of vertices (or nodes) and edges that connect pairs of vertices. Graph theory has a wide range of applications in various fields such as computer science, physics, and social sciences.

[[Image:Detail-18620.jpg|thumb|center|A photograph of a graph drawn on a chalkboard, showing vertices connected by edges.|class=only_on_mobile]]
[[Image:Detail-18621.jpg|thumb|center|A photograph of a graph drawn on a chalkboard, showing vertices connected by edges.|class=only_on_desktop]]

== History of Graph Theory ==

The origin of graph theory can be traced back to 1736 when [[Leonhard Euler]] solved the [[Seven Bridges of Königsberg]] problem. This problem asked whether it was possible to walk through the city of Königsberg, crossing each of its seven bridges exactly once. Euler proved that it was not possible, and in the process, laid the foundation for graph theory.

== Basic Concepts ==

Graph theory revolves around the study of graphs. A graph G 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.

=== Vertices ===

A vertex (also called a node) is a fundamental unit of which graphs are formed. In a diagram of a graph, a vertex is usually represented as a dot.

=== Edges ===

An edge (also called a link) is another fundamental unit of the graph. An edge connects two vertices to signify that there is a relationship between them. Each edge may be a line segment, curve, or full line.

[[Image:Detail-18622.jpg|thumb|center|A photograph of a simple graph with three vertices and three edges.|class=only_on_mobile]]
[[Image:Detail-18623.jpg|thumb|center|A photograph of a simple graph with three vertices and three edges.|class=only_on_desktop]]

=== Degree ===

The degree of a vertex is the number of edges that connect to it. In a directed graph, the degree can be divided into the outdegree and the indegree. The outdegree of a vertex is the number of edges leaving it, while the indegree of a vertex is the number of edges coming to it.

=== Paths ===

A path in a graph is a sequence of vertices where each adjacent pair is connected by an edge. The length of the path is determined by the number of edges in the path.

== Types of Graphs ==

There are several types of graphs, each with its own unique properties and uses.

=== Simple Graph ===

A simple graph is a graph in which each pair of vertices is connected by at most one edge. Furthermore, no vertex connects to itself.

=== Directed and Undirected Graphs ===

In an undirected graph, the edges do not have a direction. That is, they do not point from one vertex to another. In a directed graph (or digraph), edges have a direction. In other words, they point from one vertex to another.

=== Weighted Graph ===

In a weighted graph, each edge is assigned a numerical value, or weight. Weighted graphs are commonly used in programs that require optimization, such as finding the shortest path between two points.

[[Image:Detail-18624.jpg|thumb|center|A photograph of a weighted graph with numbers on the edges representing weights.|class=only_on_mobile]]
[[Image:Detail-18625.jpg|thumb|center|A photograph of a weighted graph with numbers on the edges representing weights.|class=only_on_desktop]]

=== Connected and Disconnected Graphs ===

In a connected graph, there is a path from any vertex to any other vertex. In a disconnected graph, at least two vertices exist such that no path connects them.

=== Cyclic and Acyclic Graphs ===

A graph is cyclic if there exists a path in the graph which starts and ends at the same vertex and includes at least one other vertex. If no such path exists, the graph is acyclic.

== Graph Theory Algorithms ==

Graph theory has given rise to a number of useful algorithms that solve problems in computer science and other fields.

=== Depth-First Search ===

The [[Depth-First Search]] (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root and explores as far as possible along each branch before backtracking.

=== Breadth-First Search ===

The [[Breadth-First Search]] (BFS) is another algorithm for searching a graph. It starts at the root and explores all the neighboring nodes at the present depth prior to moving on to nodes at the next depth level.

=== Dijkstra's Algorithm ===

[[Dijkstra's Algorithm]] is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.

=== Bellman-Ford Algorithm ===

The [[Bellman-Ford Algorithm]] computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.

== Applications of Graph Theory ==

Graph theory has a wide range of applications in diverse fields.

=== Computer Science ===

In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc.

=== Operational Research ===

Operational researchers use graph theory to solve problems related to logistics, supply chains, and transportation.

=== Chemistry ===

In chemistry, graphs are used to model molecular structures, where vertices represent atoms and edges represent bonds.

=== Social Sciences ===

In the social sciences, graphs can represent relationships between individuals or groups, enabling the analysis of social networks.

== See Also ==

* [[Network Theory]]
* [[Combinatorics]]
* [[Discrete Mathematics]]

[[Category:Mathematics]]
[[Category:Graph Theory]]
[[Category:Computer Science]]
[[Category:random]]