Dimostra che esistono k cammini AB indipendenti tra due insiemi disgiunti
Questo è un esercizio nel capitolo 1 di Extremal Graph Theory di Bela Bollobas. Questa domanda è basata su un teorema nel documento di GADirac Extensions of Menger's Theorem . Link alla carta
Domanda nel libro:
Permettere$A$=$\{a_1,...,a_p\}$e$B$=$\{b_1,...,b_q\}$essere insiemi disgiunti di vertici di$G$tale che
$\kappa(a_i,b_j)\geq k$per tutti$i,j$,$1\leq i \leq p$,$1\leq j \leq q$.
Permettere$\lambda_1,...\lambda_p$e$\mu_1,...,\mu_q$essere numeri interi non negativi, tali che$\sum_{1}^{p}\lambda_i=k=\sum_{1}^{q}\mu_j$
Ora la domanda chiede al lettore di dedurre da Menger che esiste$k$indipendente$A-B$percorsi tali che$\lambda_i$di quei percorsi iniziano a$a_i$e$\mu_j$di quei percorsi iniziano a$b_j$.
Il mio approccio :
Ho provato a indurre$k$. Il caso base$k=1$è banale. Supponiamo che esistano tali percorsi per$k=n-1$, quindi per il passo induttivo, ciò che desidero dimostrare è che possiamo aggiungere un cammino appropriato (es$a_i$e$b_j$) in modo da poter aggiungere$1$a qualsiasi$\lambda_i$e$\mu_j$. Ma non potevo dedurre una contraddizione che dovessero esistere percorsi così nuovi.
Ho anche cercato di esplorare il primo incrocio$v$di uno dei$k-1$percorsi, diciamo percorso$a_m,...,b_n$e un sentiero$a_i,...,b_j$in modo che possiamo aggiungere$1$a$\lambda_i$, durante la sottrazione$1$da$\lambda_m$aggiungendo il percorso$a_i,.,v,.,b_n$. Ma questo non fornisce alcun spunto utile.
Dato che sono solo un principiante nella teoria dei grafi, potrebbe essere che mi mancasse qualcosa di ovvio qui o che fossi sulla strada sbagliata. Qualcuno potrebbe fornire qualche suggerimento? Grazie mille!
Risposte
Anche se non ho esaminato il documento, non penso che nessuno di questi sia l'approccio giusto.
Proverei a "modificare" il grafico$G$aggiungendo due nuovi vertici$a^*$e$b^*$in modo tale da$\kappa(a^*, b^*) \geq k$, e così se il nostro nuovo grafico ha$k$indipendente$a^*-b^*$percorsi, quindi$G$deve avere i numeri giusti$\lambda_i$e$\mu_i$di percorsi tra i vertici desiderati.
Se vuoi vedere questo principio in azione, in un contesto più semplice, cerca una dimostrazione del "Fan Lemma". Usa esattamente questa idea per trasformare il teorema di Menger in un'affermazione su un intero insieme di vertici.
Per un suggerimento molto più esplicito, passa con il mouse sopra la casella sottostante. Dà una costruzione che penso dovrebbe funzionare:
Crea un nuovo grafico$G^*$da$G$come segue. Crea duplicati dei vertici di$A$e$B$in modo che ci siano almeno$\lambda_i$copie di ciascun vertice$a_i$, e$\mu_i$copie di ciascun vertice$b_i$, con esattamente gli stessi quartieri degli originali. (Ad esempio: se$\lambda_1 = 3$, poi$G^*$avrà 3 vertici, tutti chiamati$a_1$, tutti con esattamente gli stessi vicini, e if$\mu_2 = 0$o$\mu_2 = 1$, allora vattene$b_2$in$G^*$, ma non duplicarlo). Ora aggiungi i vertici$a^*$e$b^*$, e fare$a^*$adiacente a$\lambda_i$delle copie di ciascun vertice$a_i$, e fare$b^*$adiacente a$\mu_i$copie di ciascuno$b_i$. In particolare, entrambi$a^*$e$b^*$avere esattamente$k$vicinato. Nota che se puoi ottenere$k$indipendente$a^*-b^*$percorsi dentro$G^*$, quindi semplicemente cancellando$a^*$e$b^*$e "fondendo" le copie dei vertici che hai creato, ottieni esattamente il$k$percorsi che vuoi! Per il teorema di Menger, tutto ciò che devi fare è dimostrarlo$\kappa(a^*, b^*) =k$.