When people talk about graphs, there are two main kinds, namely directed graphs and undirected graphs. A graph can be thought of as a collection of nodes and edges, and the rule of how the nodes are connected by the edges. A directed graph is a graph where every edge has a specific orientation, going from one node to another. Conversely, an undirected graph is a graph where every edges does not have any specific orientation, the edges simply connect the nodes. So, one can always obtain an undirected graph from a directed graph by forgetting the orientation of every edge, we call it the forgetting process (forgetful functor).
Can we undo the forgetting process? The answer is no. We do not have an inverse exactly, for example, consider a directed graph with two nodes, V_1 and V_2, connected by an edge pointing from V_1 to V_2. After we forget the direction of the edges, the resulting undirected graph simply consists of two nodes connected by an edge, we cannot tell which direction is the edge pointing originally. In general, any edges that are not a loops (edges pointing from one node to itself) have two possible directions to be assigned. Notice that the inverse to the forgetting process is another process that if composed with the forgetting process, the result is the identity (nothing has been done). So, knowing that inverse does not exist, can we find an process that compose with the forgetting process will result in something almost like an identity? Unluckily, the answer is no again. The reason is a bit technical to explain. Roughly speaking, the constraint of maps between directed graphs is a little bit stronger than the maps between undirected graphs. This result in the increase in number of map between two directed graphs when we forget the orientation of edges, which prohibit the process we are finding to exist. However, we do have a process that convert an undirected graph back to a directed graph which interact less nicely than an inverse or almost an inverse. With that being said, it is good enough in many situation, such relation with the forgetting process (forgetful functor) is called an adjunction. The margin here is too small to contain the entire explanation, please see my report for more details.
Chun Hei Lee
The University of Adelaide
