# 1736 Graph theory

## The book of science

Tom Sharp

 Leonhard Euler mathematics

## 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 travelling 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.