By Bernhard Korte

Cet ouvrage décrit de manière détaillée les résultats théoriques et les algorithmes efficaces de l’optimisation combinatoire. Il présente des démonstrations concises mais complètes de nombreux résultats dont certains n’avaient jamais été exposés auparavant.

De l. a. théorie des graphes � l. a. programmation linéaire, des problèmes de mariage aux théories des matroïdes et de l. a. complexité, le propos couvre l’ensemble des thématiques classiques et contemporaines de ce champ qui compte parmi les plus actifs des mathématiques discrètes.

Cette traduction française de los angeles quatrième édition anglaise (la plus récente � los angeles date de e-book) intègre les dernières corrections des auteurs ainsi que des développements récents sur de nombreux sujets.

Véritable référence de l’optimisation combinatoire, ce livre s’adresse principalement aux étudiants en mathématiques et en informatique des 2e et 3e cycles universitaires, ainsi qu’aux ingénieurs et aux chercheurs confrontés � des problèmes d’optimisation.

Show description

Read or Download Optimisation combinatoire: Théorie et algorithmes PDF

Best combinatorics books

Proofs from THE BOOK

This revised and enlarged 5th variation positive factors 4 new chapters, which include hugely unique and pleasant proofs for classics resembling the spectral theorem from linear algebra, a few newer jewels just like the non-existence of the Borromean earrings and different surprises. From the Reviews". .. inside of PFTB (Proofs from The booklet) is certainly a glimpse of mathematical heaven, the place shrewdpermanent insights and lovely rules mix in stunning and excellent methods.

Combinatorial Algebraic Geometry: Levico Terme, Italy 2013, Editors: Sandra Di Rocco, Bernd Sturmfels

Combinatorics and Algebraic Geometry have loved a fruitful interaction because the 19th century. Classical interactions contain invariant thought, theta services and enumerative geometry. the purpose of this quantity is to introduce fresh advancements in combinatorial algebraic geometry and to process algebraic geometry with a view in the direction of functions, akin to tensor calculus and algebraic information.

Finite Geometry and Combinatorial Applications

The projective and polar geometries that come up from a vector house over a finite box are relatively helpful within the building of combinatorial gadgets, resembling latin squares, designs, codes and graphs. This ebook presents an advent to those geometries and their many functions to different components of combinatorics.

Extra resources for Optimisation combinatoire: Théorie et algorithmes

Sample text

Consid´erons la famille F := {Ce : e ∈ E(T )}, o`u Ce est la composante connexe de T − e contenant y si e = (x, y) ∈ E(T ) ; δ(Ce ) est donc la coupe fondamentale de e par rapport a` T . Si T est une arborescence, deux e´ l´ements quelconques de F sont deux ensembles disjoints ou alors un des deux est un sous-ensemble de l’autre. En g´en´eral F est sans croisements. 12. Un syst`eme d’ensembles est une paire (U, F), o`u U est un ensemble fini non vide et F est une famille de sous-ensembles de U .

On est int´eress´e parfois par des notions de connexit´e plus fortes que les pr´ec´edentes. Soit k ≥ 2. Un graphe non orient´e ayant au moins k sommets et qui reste connexe quand on retire k − 1 sommets quelconques sera appel´e k-connexe. Un graphe ayant au moins deux sommets et qui reste connexe quand on supprime k − 1 arˆetes quelconques sera dit k-arˆete-connexe Ainsi un graphe connexe avec au moins trois sommets est 2-connexe (resp. 2arˆete-connexe) si et seulement s’il n’a pas de sommet d’articulation (resp.

A E(G) d´efini par ζ(C)e = 0 si e ∈ / E(C) et par ζ(C)e ∈ {−1, 1} si {−1, 0, 1} e ∈ E(C) de telle sorte qu’en inversant l’orientation de tous les arcs e tels que ζ(C)e = −1 nous obtenions un circuit. De mˆeme, associons a` toute coupe D = / D, et δ(X) de G un vecteur ζ(D) ∈ {−1, 0, 1}E(G) d´efini par ζ(D)e = 0 si e ∈ par ζ(D)e = −1 si e ∈ δ − (X) et ζ(D)e = 1 si e ∈ δ + (X). Ces vecteurs sont d´efinis a` une multiplication par −1 pr`es. Donc les sous-espaces vectoriels de RE(G) engendr´es par les vecteurs associ´es aux cycles de G d’une part et par les vecteurs associ´es aux coupes de G d’autre part sont bien d´efinis ; ils d´efinissent ce que nous nommerons respectivement l’espace des cycles et l’espace des cocycles de G.

Download PDF sample

Rated 4.06 of 5 – based on 32 votes