We all understand graphs or networks are composed of nodes and edges. Some of these nodes can exist in a directed or undirected structure. In a directed graph, their edges can be either incoming or outgoing from a given node. A sink refers to a node in a directed graph with no outgoing edges. Simply, you can view a sink as someone who receives a lot but never chooses to give. Or, is obsessed with hoarding.

In a social network, a sink or from a friendship node will be poor in passing on important information to the group. On the other hand, they might be great at keeping secrets and avoiding allowing things to slip up. A sink could either be local or global. Local sinks are also referred to as a terminal and are directed graphs with no departing edge. A global sink is usually viewed as a sink and is a node that is reached by all the nodes in a given directed graph. 

Continue reading →

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.  

Continue reading →

Negative cycles usually occur in weighted directed graphs. What then is a negative cycle? A negative cycle takes place when the total sum of the cycle in a graph is negative. Negative weights are required for these cycles to exist. It will be great to explore the meaning and scenarios of negative weights. 

Negative weights of a graph: 

In an earlier article, I touched on the different types of weights in a graph. We’ve got flow, capacity, frequency, distance, time, resistance and cost weights. Negative edges and cycles are not always common in graphs. Their existence determines the most suitable algorithm to either detect or print the negative cycle. Before looking into the best algorithmic implementation of the negative cycles in a graph, it will be great to explore some scenarios or examples of negative edges. 

Logistics Example: Let’s assume you are a delivery driver contracting for an eCommerce company and the weight of your edges W(a,b,c) of an edge a,b,c is the cost of petrol or diesel from the depot to the customer destination. Nodes x,y,z form a negative cycle as these are last-minute delivery destinations that the contracting driver has just accepted from a different supplier. 

Continue reading →

Graph theory seeks to address different situations or problems in a 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 to return to the original. Taking some journey down the historical lane, the TSP problem was formulated in1800s by an Irish mathematician W.R Hamilton and his British counterpart Thomas Kirkman. 

Combinatorial Optimisation Problem

TSP belongs to a large class known as combinatorial optimisation problems. Combinatorial optimisation is aimed at discovering the best object (or city in a map situation) from a finite set of objects (or list of cities). The best solution or decision in selecting the route between objects or cities is believed to be discrete or at least reduced to discrete. Hence, the problem becomes NP-hard as the ultimate goal of most combinatorial optimisation problems seeks to find an efficient way of allocating resources such as time or money depending on the scenario. 

The difficulty of the Traveling Salesman problem in Artificial Intelligence

Solving TSP is considered to be computationally challenging even in modern times. It becomes quite challenging when a salesman desires to find the shortest route through several cities to safely return home. Regardless of the challenges, some algorithms and methods have been modified or designed to solve this problem. The popular Depth First Search (DFS) and Breadth-First Search (BFS) algorithms are two possible ways for tackling TSP. 

Continue reading →

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.

Continue reading →

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.

Continue reading →

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, 

Rules are important to ensure procedures are followed or order is maintained. There are relevant rules for a BFS algorithm. 

Continue reading →

Finding the shortest path in a network is not always the fewest nodes that need to be travelled through to a given destination. This is only applicable to an unweighted graph. For a weighted graph, the shortest path between two nodes is the least total of weight that exists between these nodes. The weights attributed to the edges of these graphs are numerical in nature and positive figures. Negative weights will prevent the determination of a minimal path. A weighted graph is viewed as a labeled graph due to the numbers assigned to each edge. 

In mathematics, a weight is used to express a set of multiplicative constants allocated in front of terms in an edge of a tree. For example, the weight of a graph at a point [n] is the maximum number of edges in a given branch [n]. The weights of a graph are computed and analysed in light of the problem investigated. Weighted graphs are believed to be present in different graph scenarios such as shortest path, centrality and travelling salesman problems.

The weight of a graph assigns value to either the node or the relationship between nodes. These values determine the shortest path or most central node in a given network. The nature or type of weight is more relevant in the type of network. For example, a weight type flow may be more applicable to traffic in a computer network, fluids in a water pipe, currents in an electrical circuit or demand movements. We will look into the flow network as it pertains to weight in the subsequent section. 

Continue reading →