Teorema de Menger
En la disciplina matemàtica de la teoria de grafos, la Teorema de Menger diu que en un gràfic finito, el tamany d'un conjunt de tall mínim és igual al número màxim de camins disjuntos que es poden trobar entre qualsevol parell de vèrtiços. Provat per Karl Menger en 1927, caracterisa la conectivitat d'un gràfic. Es generalisa per mig de la teorema de tall mínim de fluix màxim, que és una versió de vora ponderada i que a la seua volta és un cas especial de la teorema de dualitat forta per a programes llineals.
Conectivitat de vora
[editar | editar còdic]La versió de conectivitat de vora de la teorema de Menger és la següent:
- Siga G un gràfic finito no dirigit i x i i dos vèrtiços distints. Llavors, el tamany del tall de vora mínima per a x i i (el número mínim de vores l'eliminació de les quals desconecta x i i) és igual al número màxim de camins independents de les vores per parells de x a i.
- Estés a tots els parells: un gràfic està conectat a k-brodes (permaneix conectat despuix d'eliminar menys de k-brodes) sí i solament si cada parell de vèrtiços té k camins disjuntos de vores en el mig.
Conectivitat de vèrtiços
[editar | editar còdic]La declaració de conectivitat de vèrtiços de la teorema de Menger és la següent:
- Siga G un gràfic finito no dirigit i x i i dos vèrtiços no adjacents. Llavors, el tamany del tall de vèrtiç mínim per a x i i (el número mínim de vèrtiços, distint de x i i, l'eliminació de la qual desconecta x i i) és igual al número màxim de camins disyectos de vèrtiç interns de x a i.
- Estés a tots els parells: un gràfic està conectat al vèrtiç k (té més de k vèrtiços i permaneix conectat despuix d'eliminar menys de k vèrtiços) si i solament si cada parell de vèrtiços té a lo manco k trayectòries disjuntas de vèrtiços internes en el mig.
Totes estes declaracions (tant en les versions de vora com de vèrtiç) seguixen sent certes en gràfics dirigits (quan es consideren les rutes dirigides).
Bibliografia
[editar | editar còdic]- Menger, Karl (1927). “Zur allgemeinen Kurventheorie”. Fund. Math. 10: 96–115. doi:.
- “Menger's theorem for infinite graphs” (2008). Inventiones Mathematicae 176 (1): 1–62. doi:. Bibcode: 2009InMat.176....1A.
- “A note on Menger's theorem for infinite locally finite graphs” (1974). Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 40: 111–114. doi:.
- Este artícul conté una traducció derivada de «Teorema de Menger» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.