Graph Theory

Hamiltonian graphs and hamiltonian cycles.

This article discusses Eulerian circuits and trails in graphs. An Eulerian circuit is a closed trail that contains every edge of a graph, and an Eulerian trail is an open trail that contains all the edges of a graph but doesn’t end in the same start vertex.

This article also explains the Königsberg Bridge Problem and how it’s impossible to find a trail on it. Finally there are two implementations in C++ to find Eulerian trails in directed and underected graphs.

Given a weighted graph $G$ with $V$ vertices and $E$ edges where all the weights are non-negative and given a source vertex $s$, the single source shortest path problem consists in finding the distance from $s$ to all the other vertices.

In this article I describe the problem in a weighted and unweighted graph as well as implementations using BFS for unweighted graphs and Dijkstra's algorithm for weighted graphs using an array and a priority queue.

Introduction to trees in Graph Theory

Strongly connected component of a directed graph is a subgraph in which there exists a path from every vertex to every other vertex in the subgraph.

In this article I implement Tarjan's algorithm to find strongly connected components in a graph.

This article covers minimum spanning tree (MST), MSTs have important applications, MST can be used to minimize the cost of building a communication network, or it can be used to identify important features or patterns in a dataset.

I implement the Prim and Kruskal algorithms to find the minimum spanning tree in a graph with different implementations for sparse and dense graphs, also with the theory covered I also implement an algorithm to find the number of nimal spanning trees in a graph.

A vertex $v$ in a connected graph $G$ is called a cut-vertex if $G - v$ results in a disconnected graph, note that $G - v$ is an induced subgraph of $G$ (meaning that $G - v$ contains all the vertices of $G$ but $v$ and a set of edges $G - V$ where $V$ consists of all the edges incident to $v$).

In this article I implement an algorthm to find the articulation points in an undirected graph, also I explain biconnected components in an undirected graph and explain concepts such as edge connectivity and vertex connectivity.

An edge $e = uv$ of a connected graph $G$ is called a bridge if $G - e$ is disconnected (it increases the number of components).

In this article I implement an algorthm to find the bridges of an undirected graph using DFS. Next I describe an algorithm to find strong bridges in directed graphs.

Topological sorting is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. In other words, it is a way to order the vertices of a DAG such that there are no directed cycles.

In this article I implement the topological sorting algorithm as well as an example of how to use it to find the shortest path in a directed acyclic graph.

There are many ways to traverse a graph. For example through breadth-first search and depth-first search. Exploring it with a breadth-first search has interesting properties like implicitly computing the distance from a source $s$ to all the reachable vertices. Exploring it with a depth-first search has properties about edges like finding back edges, forward edges and cross edges.

This article has implementations for both BFS and DFS.

Graph Theory has numerous applications in real life, it can be used in problems found in social networks, transportation networks, the internet, chemistry, computer sciense, electrical networks among others.

In general, any problem that involves relationships between objects can be modeled as a graph.