Graph walkability

from Wikipedia, the free encyclopedia

There are numerous problems in graph theory that deal with traversing graphs . A distinction is made between problems when traversing the edges and problems when traversing the nodes . The most important problems of this type are briefly presented below.

Euler circle problem

The Euler cycle problem investigates the passability of the edges of a graph. The question here is whether there is a cycle that runs through all edges of the graph exactly once. It will be noted that it is necessary and sufficient, if the graph contiguous and all nodes straight degrees possess. This property can easily be checked in linear time using depth-first search . It is also possible to find such a cycle (if it exists) with a linear running time.

Postman problem

The Chinese Postman Problem , asks for a shortest route over all edges of an edge-weighted graph . For graphs that have an Euler circle, this route obviously corresponds to an Euler circle. In other graphs, edges must necessarily be traversed several times. The length of these edges must be minimized. For this purpose, it is sufficient to find a smallest perfect pairing in the distance graph of all nodes with an odd degree. This is possible in polynomial time. According to the edges of this pairing, the associated edges must be duplicated in the original graph. This creates a graph that has an Euler circle. It is now sufficient to find an Euler circle.

Hamilton cycle problem

The Hamilton cycle problem examines the passability of the nodes of a graph. The question is whether there is a circle that contains every node of the graph. The problem is NP-complete . Some sufficient and necessary conditions for the existence of a Hamilton cycle are known, so that it is possible to efficiently check for some graphs whether they have a Hamilton cycle.

Salesman Problem

The traveling salesperson problem asks for a shortest round trip over all nodes of an edge-weighted complete graph. This problem is also NP-complete. With the help of some reasonable assumptions ( triangle inequality ) it is possible to treat the problem at least approximately .