Cycles in graphs and problems related to matroids

点击翻译按钮获取中文摘要

In the everyday world, the concept of a graph has seen an increasing number of applications, as for example in computer and transportation networks. Of central importance to graph theory and many of its applications is the concept of a cycle. Many algorithms and methods rely heavily on its properties, and much more needs to be discovered in order to shed some light on some of the fundamental problems of combinatorics. As one example, a famous problem known as the "travelling salesman problem," asks one to find a "shortest" route for a salesman, starting from home, to visit several cities once, and return home. In combinatorics, problems of this type are modelled by cycles in a graph. While finding a "good algorithm" for a problem like this is unlikely, research on cycles may yield much improved methods.