18.2.4. Airline Routing as a Graph Problem

So, another problem that we have seen which is easily representable as a graph is that of an airline routing. So, in we have airline routing, you might ask given the routes of an airline which are represented and this kind of format by cites and arrows between them indicating flights in one direction, you might ask questions about connectivity. Then, I go from New Delhi to Trivandrum without changing airlines.

This chunk introduces the concept of airline routing as a graph problem. In this context, cities represent the vertices of the graph, while the flights between these cities represent the directed edges. When we think of airline routing in terms of graphs, we can focus on whether there is a direct flight (edge) from one city (vertex) to another. This representation allows us to simplify the routing problem by abstracting away the actual geography and distances, concentrating solely on connectivity.

Imagine a map of train routes where the destinations are represented as dots. Instead of worrying about the specific distances or landscapes, you only need to know if there's a train that goes directly between two cities. If there's a direct connection (like a direct flight), you can easily determine your travel options without needing to know the nuances of the geography.

So, formally a graph just consists of two parts, it is a set of vertices or nodes which is normally written V and there are set of edges which are pairs of vertices. So, each edge is the pair v comma v pair. Now, if you have a graph of the kind that we had for the map there we have coloring it, then we do not distinguish whether v is before v prime or v prime is before v. When, we say that two states share a common boundary, it does not matter which order we mention there mean.

In this chunk, we delve into the formal structure of a graph. A graph is made up of vertices (or nodes, denoted as V) and edges, which are pairs of vertices indicating a connection. In undirected graphs, the order of vertices in an edge does not matter (i.e., an edge between A and B is the same as between B and A). This provides a simplified model for connectivity as we do not need to worry about the direction unless we are dealing with directed graphs.

Consider a group of friends where each person represents a vertex and a friendship between any two people is an edge. Whether you say 'John is friends with Mary' or 'Mary is friends with John,' it's the same relationship—this is akin to an undirected graph where connections are mutual.

On the other hand, in the airline graph we had directions, we might have a flight from one city to other city, but not bad. We have this triangular kind of things, where we could go from one city to other there and back. So, this does not mean that you cannot go back directly on this direction, so this is not directed graph.

This chunk highlights the distinction between directed and undirected graphs. In a directed graph, the edges have a direction (like a flight path from City A to City B may not necessarily allow a direct return flight from B to A). This means we can have connections that do not allow for reciprocation. Therefore, understanding the nature of the graph is crucial for analyzing the routes in airline theory.

Think of a one-way street in a city. If you're traveling from point A to point B (the direction of the street), you can’t directly go back to A without taking a detour. In contrast, if the street is two-way, you can easily travel back and forth without changing your route.

Similarly, we can express the problem of finding a root in the mathematical science, initially our problem is a directed graph. Then, we identify the vertices corresponding to the cities, where we want to find the nodes.

This chunk discusses the goal of finding a route between two vertices in a directed graph (e.g., finding a flight path from New Delhi to Trivandrum). The problem can be defined mathematically by identifying the vertices (cities) and the edges (flights). The goal is to find a sequence of vertices that form a path from the starting point to the destination, analyzing connectivity and possible routes within the given structure.

Imagine you're trying to navigate from your home (vertex A) to your friend's house (vertex B) using a map app. The app shows the streets (edges) that connect various places. Your task is basically to find the most efficient path from A to B based on the available roads and any one-way streets, representing the concept we see in airline routing.

--