Che tajo, 'sta caratterizzazione dei tagli!

[Tibor Gallai]

E' dato un grafo G ed un sottoinsieme E dei suoi archi. Mostrare che E è un taglio se e solo se, per ogni ciclo, E ha in comune con esso un numero pari di archi.

(Definizione di taglio: data una partizione dei nodi di G in due sottoinsiemi A e B, l'insieme degli archi che hanno un estremo in A e l'altro in B è detto taglio.)

[Tibor Gallai]

Hint: dimostrare questo lemma.
Un grafo è bipartito se e solo se ogni suo ciclo ha lunghezza pari.
(bipartito significa che esiste una partizione dei nodi in due sottoinsiemi A e B tali che tutti gli archi del grafo hanno un estremo in A e l'altro estremo in B)

[federiko97]

Toh, che problema simpatico... Anche se mi ci è voluto qlk giorno e un hint per trovare la soluzione...

wlog il grafo è connesso. Fisso un punto A e chiamo f(P) per ogni punto P del grafo la parità del numero di archi di E su cui passo per andare da A a P (non dipende dal percorso per ipotesi). Ora $ f^{-1}(1) $ e $ f^{-1}(0) $ è la partizione che dà come taglio (e che taglio!) E.

[Tibor Gallai]

Hehe! Devo dire che ho messo il titolo in romanesco in omaggio a piever, che sta trattando bene tutti i miei problemi di teoria dei grafi. Quindi è appropriato che a risolverlo sia stato un altro romano.
Mancano un po' (molti) dettagli, ma la soluzione è sostanzialmente giusta. Bravo!! Se hai voglia, esplicita un po' meglio il tutto, a beneficio del forum. Ad esempio: un'implicazione è banale, perché? Come si dimostra il lemma? Perché la tua costruzione risolve l'implicazione non banale? Etc etc...

[federiko97]

Orgoglioso di essere romano (mi pare fosse un vecchio manifesto pubblicitario di Veltroni: ricorda molto il "Fiero di essere Lensese - sangue e onore!" di una bandiera di una inverosimile e probabilmente non fortissima squadra di calcio francese) aggiungo volentieri i dettagli che mancano...

Prima di tutto, se E è un taglio, ogni ciclo del grafo contiene un numero pari di archi di E: infatti ogni volta che passo su un arco di E vado da un blocco all'altro dei vertici del grafo, visto che devo tornare al blocco di partenza, farò questa cosa un numero pari di volte...

Lemma: se un grafo non ha cicli di lunghezza dispari, allora è bipartito (l'altra freccia è banale). Wlog il grafo è connesso (sennò analizzo singolarmente ciascuna componente conenssa). Fisso un nodo A e dico che un nodo P è bello se il cammino AP ha lunghezza pari (il cammino non è unico, ma se ce ne fossero due di parità diversa, si formerebbe per forza un ciclo di lunghezza dispari). Invece dico che un nodo Q è brutto se AQ ha lunghezza dispari. Ora chiaramente due nodi belli B e C non possono essere collegati tra loro, altrimenti per andare da A a C potrei prima passare per B e poi fare un altro passo fina a C, ottenendo un cammino di lunghezza dispari. Allo stesso modo due nodi brutti non possono essere collegati. Quindi se divido il grafo in nodi belli e nodi brutti lo ho bipartito.

Ora, tornando al problema, se considero del percorso AP non la parità del numero di archi totale (che varia a seconda di che percorso scelgo), bensì la parità del numero di archi di E che incontro, divido il grafo in nodi belli e nodi brutti in questo nuovo modo e noto che:

1) due nodi esteticamente simili non possono essere collegati da un arco di E (stesso ragionamento di sopra)

2) due nodi esteticamente diversi B e C non possono essere collegati da un arco non di E: se lo fossero, vado da A a B, poi da B prendo l'arco non di E che lo collega a C e noto che qualcosa non va (fair is foul and foul is fair - citando le tre streghe di Macbeth).

p.s. sono finalmente finiti finiti i tempi in cui se dicevi "che taglio!" a uno stage, un buon 95% della gente si girava e ti guardava con aria perplessa

[Tibor Gallai]

p.s. sono finalmente finiti finiti i tempi in cui se dicevi "che taglio!" a uno stage, un buon 95% della gente si girava e ti guardava con aria perplessa

Cambia poco, perché d'ora in poi ti diranno: "di che grafo?!?", con la stessa aria perplessa.

Benissimo per la dimostrazione.
2 note stilistiche: tradizionalmente la dimostrazione del lemma si fa considerando un albero di copertura radicato del grafo, perché viene più pulita la parte in cui dimostri che è ben definita la parità dei nodi (semplicemente la definisci come parità della profondità del nodo), ed anche la parte successiva è meno problematica.
E la freccia non banale del teorema viene bene contraendo gli archi di G che non sono in E. Il multigrafo risultante è bipartito per il lemma (che vale anche per i multigrafi, con dimostrazione identica...).