Graph theory seeks to address different situations or problems in business application or organisational setups. TSP (Traveling Salesman Problem) is usually considered NP-hard (nondeterministic polynomial time) in solving decision problems. This is because there are more than one possible action or directions when deciding to traverse through every city or vertex in a given graph with the goal or returning to the original. Taking some journey down the historical lane, the TSP problem was formulated in1800s by an Irish mathematician W.R Hamiltion and his British counterpart Thomas Kirkman. 

Graphs can be directed or undirected in nature. Articulation points are quite important in a graph as they signal possible vulnerabilities in a given network. Removing a node from a connected undirected graph is likely to split the network into different components of an undirected graph. 

A simple illustration of articulation points 

The undirected graph below contains seven nodes and there are two articulation or critical points. Node B is very important to the network as it directly connects with five nodes. Removing node B will break this graph into three disconnected components. The three disconnected graphs after removing node B will be (A) , (C and D) and (E, F and G). The second articulation point on this graph is node C. A decision to remove node C will lead to two disconnected components which are nodes (A, B, E, F, G) and (D). This clearly shows that node B and C are the two articulation points with B being slightly more critical. Node B is the most critical because if removed it renders the remaining graphs into three disconnected components. On the other hand, removing vertex C splits the graph into two disconnected components.

The shortest path problem is pivotal in graph theory. It aims at discovering the “most efficient’ or ‘best’ way of moving from x to y, where x and y are both nodes in a given graph. The most efficient or best in this context is evaluated by the lowest sum of edge weights between the path of both vertices. The shortest or quickest path is arrived at by summing the lengths of the individual edges. A best-case scenario is a graph with edges having positive weights. There is also the concept of single-source shortest path problem with s as the source node. For clarity, the source node initiates the transversal within the graph.

You might have encountered the words, breadth and depth in real-world scenarios. Breadth implies the complete range of knowledge of any given subject or topic. On the other hand, depth in terms of learning touches on the degree to which a particular subject is magnified or explored. Let’s begin with the breadth first search or the BFS of a given graph. Now BFS does not refer to Best Friends from school but Breadth-First Search. 

Exploring Breadth First Search or Breadth First Traversal 

BFS is an algorithm that is designed to search for a graph or tree data formation. It usually travels in a breadthward motion and utilises a queue as a prompt to identify the next vertex to commence a traversal. If a roadblock is encountered or no adjacent node is found, the tree root or the source node is removed for the queue. The traversal of the graph usually begins with a ‘search key’ or the initialising node. Imagine a hotel with so many floors and rooms as nodes, a breadth-first traversal algorithm is like a cleaning staff that will clean rooms floor by floor. All neighbouring nodes at the current depth or floor with the example above will be visited to clean before moving to the vertices or rooms on the next floor. No node is expected to be revisited as one would not expect hotel staff to clean the same room twice in the same period. Once a room is cleaned, it is ticked on a sheet as a visited while with BFS, the neighbouring reversed node is enqueued or marked as visited, 

Networks or graphs are pivotal in so many real-world applications such as fraud prevention systems. search engines, recommendation systems, social networks and a lot more. The search for the mother vertex of a graph aids in understanding the accessibility of a given vertex or collection of vertices. 

What is the meaning of the mother vertex in a given graph?

In a given graph G = (V, E), a mother vertex v has a pathway for all other vertices in the specified graph to enable the connection. All other vertices in the graph can be accessed via the mother vertex. A mother vertex is quite common in directed graphs but is also applicable in undirected networks. We will briefly explore mother vertices in different network examples

Several graph algorithms can help reveal hidden patterns in connected data. These algorithms can be classified into several categories such as approximations (e.g clustering), assortativity (e,g average neighbour degree), communities (e.g K-Clique) and centrality (e.g shortest path). In this blog, we will be looking at one of the most popular shortest path algorithms known as the Dijkstra’s algorithm. We will look at an example table and code implementation for this algorithm. Shortest path algorithm can be relevant in a traffic network situation a user desires to discover the fastest way to move from a source to a destination. It is an iterative algorithm that provides us with the shortest path from an origin node to all other nodes in the graph. This algorithm can work in weighted and unweighted graph scenarios. 

In graph theory, a bridge is an edge whose removal leads to the disconnection of the network. It is usually found in undirected graphs and can also be viewed within the context of disconnected undirected graphs. In these disconnected undirected graphs, removing a bridge leads to a further separation of the subgraphs. Let’s explore some examples below. 

Bridge in an undirected connected graph:

The below graph is undirected but it is connected. There are 9 nodes and 10 edges in this graph. You can determine that one edge is in red and the rest are in grey/black. The edge in red is the bridge and removal will lead to a disconnection of node [L] from the rest of the graph. Assuming all of these nodes were train stations and the edges are London tube lines.  A rail track maintenance work, shortage of control room staff or a broken train on the track are some of the reasons that can cause a train line that connects node [H] to node[L] to become disconnected or temporarily removed from the train network or graph. When this occurs, people living close to the station [L] will become stranded or short of transportation options. This is a connected graph because the disconnected unit is not a sub-graph on its own but a single node stranded and possibly struggling in the network.