Worldlex Wiki Une matrice m par n est dite être un tableau de Monge si, pour tout tel que l'on obtient En d'autres termes, pour deux lignes et deux colonnes quelconques d'un tableau de Monge, les quatre éléments aux points d'intersection (une sous-matrice 2 × 2) ont la propriété que la somme des éléments en haut à gauche et en bas à droite (sur la diagonale principale ) est inférieure ou égale à la somme des éléments en bas à gauche et en haut à droite (sur l' antidiagonale ).
Cette matrice est un tableau de Monge :
Par exemple, prenez l'intersection des lignes 2 et 4 avec les colonnes 1 et 5. Les quatre éléments sont La somme des éléments en haut à gauche et en bas à droite (17 + 7 = 24) n'est pas supérieure à la somme des éléments en bas à gauche et en haut à droite (23 + 11 = 34).
Propriétés
- La définition ci-dessus est équivalente à l'énoncé
- Une matrice est un tableau de Monge si et seulement si pour tout et .
- Tout sous-tableau obtenu en sélectionnant certaines lignes et colonnes d'un tableau Monge original sera lui-même un tableau Monge.
- Toute combinaison linéaire de tableaux de Monge dont les coefficients sont non négatifs est elle-même un tableau de Monge.
- Tout tableau de Monge est parfaitement monotone, ce qui signifie que les minima de ses lignes apparaissent dans une séquence non décroissante de colonnes, et que cette propriété est valable pour tout sous-tableau. Grâce à cette propriété, les minima des lignes peuvent être trouvés rapidement à l'aide de l' algorithme SMAWK . Si vous marquez d'un cercle le minimum le plus à gauche de chaque ligne, vous constaterez que les cercles se déplacent de bas en haut vers la droite ; autrement dit, si , alors pour tout . Symétriquement, si vous marquez le minimum le plus haut de chaque colonne, les cercles se déplaceront de haut en bas vers la droite. Les maxima des lignes et des colonnes se déplacent dans la direction opposée : de haut en bas vers la droite et de bas en bas vers la gauche.
- La notion de tableaux de Monge faibles a été proposée ; un tableau de Monge faible est une matrice carrée n x n qui satisfait la propriété de Monge uniquement pour tous les .
- Une matrice de Monge est simplement un autre nom pour une fonction sous-modulaire de deux variables discrètes. Plus précisément, A est une matrice de Monge si et seulement si A [ i , j ] est une fonction sous-modulaire des variables i , j .
Applications
Les matrices de Monge ont des applications dans les problèmes d'optimisation combinatoire :
- Lorsque le problème du voyageur de commerce possède une matrice de coûts qui est une matrice de Monge, il peut être résolu en temps quadratique.
- Une matrice de Monge carrée, symétrique par rapport à sa diagonale principale, est appelée matrice de Supnick (d'après Woeginger, Gerhard J. (octobre 2006). « Quelques problèmes liés au voyageur de commerce, aux cibles de fléchettes et aux pièces en euros » (PDF) . Bulletin de l’Association européenne d’informatique théorique , vol. 90 , EATCS : 43-52 . ISSN 0252-9742 .