Vadim Kostrykin and Robert Schrader
The Inverse Scattering Problem for Metric Graphs and the Traveling Salesman Problem
(276K, LaTeX2e)

ABSTRACT.  We present a solution to the inverse scattering problem for differential Laplace operators on metric noncompact graphs. We prove that for almost all boundary conditions (i) the scattering matrix uniquely determines the graph and its metric structure, (ii) the boundary conditions are determined uniquely up to trivial gauge transformations. The main ingredient of our approach is a combinatorial Fourier expansion of the scattering matrix which encodes the topology of the graph into analytic properties of the 
scattering matrix. Using the technique developed in this work, we also 
propose an analytic approach to solving some combinatorial problems on 
graphs, in particular, the Traveling Salesman Problem.