Teorema de Nash-Williams

En teoría de grafos , el teorema de Nash-Williams es un teorema de empaquetamiento de árboles que describe cuántos árboles de expansión disjuntos en aristas (y, más generalmente, bosques ) puede tener un grafo:

Un grafo G tiene t árboles de expansión disjuntos por aristas si y solo si para cada partición${\textstyle V_{1},\ldots,V_{k}\subset V(G)}$dónde${\displaystyle V_{i}\neq \emptyset }$Hay al menos t ( k  −  1) aristas que se cruzan.

El teorema fue demostrado independientemente por Tutte ^{[ 1 ]} y Nash-Williams , ^{[ 2 ]} ambos en 1961. En 2012, Kaiser ^{[ 3 ]} dio una breve demostración elemental.

En este artículo, decimos que un grafo de este tipo tiene arboricidad t  o es t - arbórico . (La definición real de arboricidad es ligeramente diferente y se aplica a los bosques, no a los árboles).

Un grafo k -arbórico es necesariamente k -arista conexo . Lo contrario no es cierto.

Como corolario del teorema de Nash-Williams, todo grafo 2k - aristas conexo es k -arbórico.

Tanto el teorema de Nash-Williams como el teorema de Menger caracterizan cuándo un grafo tiene k caminos disjuntos en aristas entre dos vértices.

En 1964, Nash-Williams ^{[ 4 ]} generalizó el resultado anterior a los bosques:

Un gráfico${\displaystyle G}$se puede dividir en${\displaystyle t}$bosques disjuntos en los bordes si y solo si para cada${\displaystyle U\subset V(G)}$, el subgrafo inducido${\displaystyle G[U]}$tiene como máximo${\displaystyle t(|U|-1)}$bordes.

Aquí se presentan otras pruebas. ^{[ 5 ] [ 6 ]}

Así es como la gente suele definir lo que significa que un grafo sea t -arbórico.

En otras palabras, para cada subgrafo${\displaystyle S=G[U]}$, tenemos${\displaystyle t\geq \lceil E(S)/(V(S)-1)\rceil }$Es ajustado porque hay un subgrafo${\displaystyle S}$que satura la desigualdad (o bien podemos elegir una más pequeña)${\displaystyle t}$). Esto conduce a la siguiente fórmula

${\displaystyle t=\lceil \max _{S\subset G}{\frac {E(S)}{V(S)-1}}\rceil }$,

También conocida como la fórmula de Nash-Williams.

El problema general consiste en preguntarse cuándo un grafo puede cubrirse mediante subgrafos disjuntos en aristas.

• Arboricidad
• Puente (borde cortado)
• Particionamiento de matroides
• Teorema de Menger
• Conjetura sobre el empaquetamiento de árboles

• Paulson, Lawrence C. El teorema de partición de Nash-Williams (Desarrollo de la demostración formal en Isabelle/HOL, Archivo de Demostraciones Formales)