Optimum and graph theory
The notion of optimum often evokes that of maximum or minimum of a function which, like a fluid, would evolve in a continuous manner, and even differentiable. The arsenal of analysis and differential calculus then comes to mind. But optimization also often concerns quantities that can take only a finite or countable number of values. If the range of techniques from analysis is then of no use, discrete mathematics and graph theory take over. It is the computer, a sequential machine best suited to combinatorial environments, that will then most often be called upon to solve optimum problems.
All articles in this folder
Coloring problems for all ages
Assigning colors—and their associated sets of constraints—to the vertices of a graph opens up the fascinating world of graph-coloring problems.
Shortest paths: graph algorithms | Tangente
Is the shortest path from A to B always a straight line? Usually, yes. But when we must follow the network of roads and intersections in a city, we need a different perspective. That is where Dijkstra's algorithm comes to the rescue!
Randomness to the rescue of satisfiability
The Boolean universe is a small mathematical world in which only two values exist: True and False. Yet achieving satisfaction is already complicated! Fortunately, randomness comes to our rescue: choosing by a coin toss can sometimes bring us surprisingly close to the maximum we seek.
Graph vertex degree constraints | Tangente
What is the smallest graph with a given set of degrees? Forty years ago, an article provided an elegant, constructive answer to this question.
The art of avoiding crossings
Artists using mathematics: nothing new there. But artists posing optimization problems that mathematicians still cannot solve: now that is surprising! One seemingly innocuous conjecture about drawing graphs has resisted all attempts at proof for fifty years.