Città e strade

[Anér]

Nel regno incantato di Grafolandia regnano la pace e la concordia. Il regno è costituito da un numero finito di città (che chiameremo $n$) fra le quali vi sono due capitali, Apoli e Bipoli (che nella lingua del popolo si chiamano A e B). Esistono anche alcune strade che collegano coppie di città in una o in entrambe le direzioni; fra due città possono esistere anche più strade con caratteristiche di percorribilità anche diverse. Purtroppo il regno è infestato da creature mostruose che la notte di capodanno distruggono al più $k$ strade, con $k\in \mathbb{N}$, e occorre un anno intero per ricostruirle. Tuttavia gli abitanti del regno sanno che il primo gennaio è sempre possibile andare da A a B, qualsiasi siano le strade distrutte durante la notte, purché siano al più $k$. Dimostrare che è possibile individuare $k+1$ percorsi da A a B che a due a due non hanno strade in comune.

Variante 1: A e B sono insiemi di città e il 1 gennaio è sempre possibile individuare una città di A e una di B per le quali è possibile andare dalla prima alla seconda; allora esistono $k+1$ percorsi senza strade in comune da una città di A a una città di B.

Variante 2: Le strade hanno un peso reale positivo, le creature mostruose distruggeranno strade per un peso complessivo minore o uguale a $x$, con $x\in \mathbb{R}^+$, e tuttavia sarà sicuramente possibile andare da A a B. Allora è possibile individuare alcuni percorsi (diciamo $h$ percorsi) ed assegnare ad ognuno un valore $x_i$ in modo che $\sum_{i=1}^h x_i>x$ e ogni strada ha un peso maggiore o uguale alla somma dei valori dei percorsi che passano per la strada stessa.

[Anér]

In realtà funziona tutto bene anche se sono le città ad essere distrutte: supponiamo che ogni città abbia un peso maggiore di zero, eventualmente infinito, e che i mostri distruggano città per un peso complessivo di al più x, e che comunque lo facciano rimane un percorso da A a B; allora esistono un certo numero di percorsi, diciamo h, a ognuno dei quali possiamo associare un peso $x_i$ in modo che $\sum_{i=1}^h x_i>x$ e ogni città è attraversata da percorsi per un peso complessivo minore o uguale al suo peso.
Nel caso in cui ogni città pesa 1 tranne A e B che hanno peso infinito, se distruggere k città non basta a sconnettere A e B vuol dire che esistono k+1 percorsi da A a B senza città in comune, a parte le capitali.

[Tess]

Per risolvere il problema base potrebbe funzionare fare qualcosa di questo tipo?
-Ad ogni strada associo un indice di quanti sono i percorsi distinti* che passano per quella strada e collegano A con B;
-Tolgo una strada a caso tra quelle che hanno indice massimo;
-Ricalcolo gli indici di tutte le altre strade (tenendo conto che ho eliminato questa);
-Procedo così con la cancellazione di altre strade con questo metodo in modo che abbia cancellato in tutto k strade.

*distinti: intendo due percorsi distinti se esiste almeno una strada appartenente ad uno, ma non appartenente all'altro.

Così in teoria dovrei avere alla fine almeno un percorso (per ipotesi del problema), poi riaggiungendo le strade che ho tolto dall'ultima indietro dovrei riuscire a scovare un percorso passante per quella strada che non si intersechi con nessun altro percorso, e questo dovrebbe essere vero perché l'indice con cui avevo tolto prima quella strada è abbastanza grande.

[Anér]

Mmh, forse si aggiusta in qualche modo, però così non funziona: prendi 4 città, che sono A, B, X e Y; tutte sono collegate da una strada con entrambi i versi di percorrenza, tranne A e B che non sono collegate da alcuna strada. Allora esistono 2 percorsi disgiunti da A a B (AXB e AYB) e se tagli le strade AX e AY disconnetti A e B. Tuttavia l'indice massimo è 2 e anche XY ha indice 2, dunque potresti tagliare proprio XY, e puoi vedere facilmente che XY è una strada poco utile.

[Tess]

Beh, direi di separare i versi di percorrenza... se sia lecito farlo...
Allora, vedo di definire bene tutto quello che mi serve:
Ogni strada a doppia percorrenza la separo in due strade a percorrenze opposte, ma mi ricordo che tali 2 erano una sola strada nel caso volessi scegliere uno dei 2 versi di percorrenza da eliminare.
Un percorso è sensato se parte da A, arriva in B e non contiene cicli al suo interno.
Come prima 2 percorsi sensati sono distinti se uno visita una strada che l'altro non visita.
Per ogni strada a senso unico definisco indice di quella strada il numero di percorsi sensati e distinti che passano per quella strada.
Continuo con il procedimento descritto sopra.

Quindi nell'esempio che dici ho indice 1 da X a Y e indice 1 da Y a X, quindi non considero nessuna delle due strade da togliere.

[Anér]

Non so se funziona ma così sembra una buona strada, continua a pensarci!

[Tess]

ma così sembra una buona strada

È vero, sembrava proprio una bella strada... peccato non funzioni sempre!
Allora ho pensato a questo:
-per ogni città direttamente raggiungibile da A prendo la porzione di grafo raggiungibile a partire da questa;
-scarto direttamente città e sottografo se in questo non c'è B;
-se due di questi sottografi sono tali che la loro unione possiede un ponte per arrivare a B, li scarto e prendo al loro posto il grafo raggiunto a partire dal primo di questi ponti (un ponte è una strada che appartiene ad ogni percorso dalla città che genera il sottografo alla città B);
-quando ho finito di scartare sottografi con questa ultima procedura, ne ho comunque almeno $k+1$, per ciascuno dei quali posso costruire un percorso indipendente dagli altri.
Mi pare che questo metodo funzioni un po' di più!
Quel che è da dimostrare è che:
-alla fine i sottografi sono almeno $k+1$, questo perché, se per assurdo ne ho al più $k$, potrei cancellare per ciascuno di essi l'unica strada che porta alla città che lo genera, bloccando in questo modo il passaggio da A a B. Il blocco è dovuto al fatto che qualsiasi percorso che congiunge A e B passa per quella strada.
-se due città generano sottografi la cui unione non possiede ponti, riesco a disegnare un percorso da ciascuna che porta a B in modo che siano disgiunti (che si fa, ma non ho tempo adesso di scriverla).
-...
Funziona fino ad un certo punto... ancora non è detto che i percorsi che disegno siano del tutto indipendenti... ma forse credo basti cambiare il 3° punto del procedimento sopra descritto, in modo che se $n+1$ di questi sottografi hanno un sistema di $n$ ponti, allora li sostituisco con $n$ sottografi...
Vedrò di finirla per domani!