# 1736 Graph theory

## Graph theory

Leonhard Euler proved that a person could not walk through Königsberg to cross each of its seven bridges only once. He abstracted a map of Königsberg to a graph of simple vertices and edges and showed that traversing each edge only once means that each vertex, except for the two that you start and end on, must be connected by an even number of edges. Unfortunately, each of the four land areas in Königsberg had an odd number of bridges that connect it to the others.

## Theory

A graph is not a diagram, although you can diagram a graph. A graph does not depict distances, although its edges may have distance values. A graph is mathematical structure for modeling information, an abstraction for analysis of relations between objects. The signifier is not the signified, even if they look the same. The word ‘word’ is not wordy; for that we have the commentaries.

## Problems

We have a traveling salesman that must visit all towns in Sweden and wants to know the shortest route. We have a map of political regions and must color the regions so that no adjacent regions are the same color. We have an art gallery with several rooms and numerous alcoves and don’t want to hire more guards than we need. We have a non-profit organization with many contributors having different skills and want the smallest board with all needed skills. We have a chemical plant with limited mineral resources and want to produce the elements and compounds with the fewest and cheapest processes. We want to design a processing plant to minimize the distances that employees and product must traverse.

## Identity

In the physical world anything that occupies space and is relatively stable is an object. In the logical world anything that has its own identity is an object. It doesn’t need to be stable. If I have written about this before, then there’s a small chance that this is exactly the same poem.

Graph theory has been extended in many ways to increase its power to model systems and represent many kinds of information. Furthermore, other types of graphical models, such as Bayesian networks, Petri nets, and probabilistic graphical models, can serve different needs.

See also in The book of science: