Dimostrare che i nodi di un grafo possono essere partizionati in 2 sottoinsiemi (possibilmente vuoti), tali che ogni nodo di ciascun sottoinsieme abbia un numero pari di vicini nello stesso sottoinsieme.
Esempio: il grafo completo con 6 nodi può essere partizionato mettendo 3 nodi da una parte, ed i rimanenti 3 dall'altra. Così, all'interno di ciascun sottoinsieme, ogni nodo ha 2 vicini. Una partizione altrettanto valida è quella che mette 1 nodo da una parte (0 vicini), e gli altri 5 dall'altra (4 vicini).
Partizionamento particolare di un grafo
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Facendo parte di un piano di spionaggio internazionale su vasta scala, ho scoperto il modo in cui i francesi fanno i problemi delle olimpiadi: imparano 1 o 2 metodi che a volte funzionano e provano a usarli sempre. Questo ha alcune evidenti conseguenze, ad esempio il fatto che il punteggio della francia alle IMO dipende esclusivamente da quali problemi vengono scelti, non da quali francesi partecipano o da quante idee hanno in gara...
Ho fatto questo piccolo sproloquio introduttivo perché mi sembra che questo problema rientri nella ristretta cerchia dei "problemi risolvibili alla francese"...
Siano $ v_1,\dots ,v_k $ i vertici e $ s_1,\dots ,s_n $ gli spigoli del nostro caro grafo. Posso costruire una matrice dove $ a_{i,j}=1 $ se il vertice $ v_i $ è un estremo dello spigolo $ s_j $ e $ a_{i,j}=0 $ altrimenti.
Posso chiamare $ R_i $ (vettore di lunghezza n) l'i-esima riga (cioè il vettore dove il primo termine è 1 se il vertice i è un estremo dello spigolo 1 e così via). La tesi diventa: esiste $ I\subseteq \{1,\dots ,k\} $ tale che, per ogni m, $ \displaystyle R_m\cdot R_m\equiv\sum_{i\in I} R_m\cdot R_i\pmod 2 $ (il per è un prodotto scalare).
Questa tesi però, posso dimostrarla per tutte le matrici con coefficienti in $ \mathbb{F}_2 $, non solo per quelle a cui corrisponde un grafo. Lo faccio per induzione sul numero di righe.
Per comodità invece che modulo 2 dovendo mettere simboli di congruenza ovunque, ragiono in $ \mathbb{F}_2 $
E' chiaro che se nella mia matrice ad una riga ne aggiungo un'altra, ottenendo un'altra matrica, se la tesi è vera nella prima matrice è vera anche nella seconda, e viceversa. Infatti l'unica cosa che conta è il gruppo generato dai vettori riga, non quali siano esattamente i vettori riga.
Prendiamo una matrice con k righe e supponiamo che la tesi sia vera con matrici di k-1 righe. Scelgo nella mia matrice una riga che ha un numero dispari di 1 (se non ce ne sono prendo $ I=\emptyset $ e ho vinto). Wlog quella riga è $ R_k $. Ora considero tutte le righe $ R_i $ tali che $ R_i\cdot R_k=1 $. A ciascuna di queste righe aggiungo $ R_k $, ottenendo così una nuova matrice (le cui righe chiamo $ P_1,\dots , P_k $) in cui per $ \forall m\in\{1,\dots, k-1\} $ si ha $ P_i\cdot P_k=0 $. Per quanto detto sopra ci basta dimostrare la tesi in questa matrice.
Adesso tolgo a questa matrice l'ultima riga. Per ipotesi induttiva esiste $ J\subseteq \{1,\dots, k-1\} $ tale che $ \forall m\in\{1,\dots, k-1\} $ si ha: $ \displaystyle P_m\cdot P_m=\sum_{i\in J} P_m\cdot P_i $
Adesso riaggiungo la k-esima riga e pongo $ I=J\cup \{k\} $
Se m è più piccolo di k, ho che $ \displaystyle P_m\cdot P_m=\sum_{i\in J} P_m\cdot P_i=\sum_{i\in J} P_m\cdot P_i + P_m\cdot P_k=\sum_{i\in I} P_m\cdot P_i $ in quanto $ P_i\cdot P_k=0 $
Inoltre $ \displaystyle\sum_{i\in I} P_k\cdot P_i=\sum_{i\in J} P_k\cdot P_i + P_k\cdot P_k=P_k\cdot P_k $
Quindi il sottoinsieme I è effettivamente adatto. Fine.
Ho fatto questo piccolo sproloquio introduttivo perché mi sembra che questo problema rientri nella ristretta cerchia dei "problemi risolvibili alla francese"...
Siano $ v_1,\dots ,v_k $ i vertici e $ s_1,\dots ,s_n $ gli spigoli del nostro caro grafo. Posso costruire una matrice dove $ a_{i,j}=1 $ se il vertice $ v_i $ è un estremo dello spigolo $ s_j $ e $ a_{i,j}=0 $ altrimenti.
Posso chiamare $ R_i $ (vettore di lunghezza n) l'i-esima riga (cioè il vettore dove il primo termine è 1 se il vertice i è un estremo dello spigolo 1 e così via). La tesi diventa: esiste $ I\subseteq \{1,\dots ,k\} $ tale che, per ogni m, $ \displaystyle R_m\cdot R_m\equiv\sum_{i\in I} R_m\cdot R_i\pmod 2 $ (il per è un prodotto scalare).
Questa tesi però, posso dimostrarla per tutte le matrici con coefficienti in $ \mathbb{F}_2 $, non solo per quelle a cui corrisponde un grafo. Lo faccio per induzione sul numero di righe.
Per comodità invece che modulo 2 dovendo mettere simboli di congruenza ovunque, ragiono in $ \mathbb{F}_2 $
E' chiaro che se nella mia matrice ad una riga ne aggiungo un'altra, ottenendo un'altra matrica, se la tesi è vera nella prima matrice è vera anche nella seconda, e viceversa. Infatti l'unica cosa che conta è il gruppo generato dai vettori riga, non quali siano esattamente i vettori riga.
Prendiamo una matrice con k righe e supponiamo che la tesi sia vera con matrici di k-1 righe. Scelgo nella mia matrice una riga che ha un numero dispari di 1 (se non ce ne sono prendo $ I=\emptyset $ e ho vinto). Wlog quella riga è $ R_k $. Ora considero tutte le righe $ R_i $ tali che $ R_i\cdot R_k=1 $. A ciascuna di queste righe aggiungo $ R_k $, ottenendo così una nuova matrice (le cui righe chiamo $ P_1,\dots , P_k $) in cui per $ \forall m\in\{1,\dots, k-1\} $ si ha $ P_i\cdot P_k=0 $. Per quanto detto sopra ci basta dimostrare la tesi in questa matrice.
Adesso tolgo a questa matrice l'ultima riga. Per ipotesi induttiva esiste $ J\subseteq \{1,\dots, k-1\} $ tale che $ \forall m\in\{1,\dots, k-1\} $ si ha: $ \displaystyle P_m\cdot P_m=\sum_{i\in J} P_m\cdot P_i $
Adesso riaggiungo la k-esima riga e pongo $ I=J\cup \{k\} $
Se m è più piccolo di k, ho che $ \displaystyle P_m\cdot P_m=\sum_{i\in J} P_m\cdot P_i=\sum_{i\in J} P_m\cdot P_i + P_m\cdot P_k=\sum_{i\in I} P_m\cdot P_i $ in quanto $ P_i\cdot P_k=0 $
Inoltre $ \displaystyle\sum_{i\in I} P_k\cdot P_i=\sum_{i\in J} P_k\cdot P_i + P_k\cdot P_k=P_k\cdot P_k $
Quindi il sottoinsieme I è effettivamente adatto. Fine.
"Sei la Barbara della situazione!" (Tap)
E adesso due domande di rito al propositore di questo simpatico problema:
1) la dimostrazione scritta sopra è comprensibile/funziona? In caso non funzionasse, dimmelo con tatto che avendo penato per ore su questo problema, potrei avere un violento attacco di frustrazione...
2) esiste una dimostrazione più decente?
1) la dimostrazione scritta sopra è comprensibile/funziona? In caso non funzionasse, dimmelo con tatto che avendo penato per ore su questo problema, potrei avere un violento attacco di frustrazione...
2) esiste una dimostrazione più decente?
"Sei la Barbara della situazione!" (Tap)
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Grazie per l'introduzione, non posso fare a meno di riconoscere la tipica forma mentis del baguettaro mangiaranocchie, nell'affresco che ci hai magistralmente dipinto. Hai dimenticato di citare l'esagerato orgoglio nazionale di cui il francese medio dà prova senza ritegno e senza posa al minimo pretesto: è strano che questo non traspaia anche nel loro modo di risolvere i problemi... che so, magari al posto di QED scrivono VLF, o simili (che non è "viva la figa", ricordiamoci che sono delle mezze checche).
Per rispondere alle domande, non ho trovato errori nella tua dimostrazione, ma quella che avevo in mente usa solo il linguaggio della teoria dei grafi, e si scrive in brevi righe. Non è esattamente una "traduzione" della tua, anche perché tu dimostri una tesi un po' più generale, e le somme di righe che fai perdono significato nell'ambito del grafo. Appena ho qualche minuto, la scrivo.
Per intanto, posso proporre una bonus question: mostrare che il numero di queste partizioni è sempre una potenza di 2. Precisamente, l'esponente è la dimensione dell'intersezione dello spazio dei cicli e dello spazio dei tagli del grafo (per chi sa cosa sono...). Ritornando all'esempio del grafo completo con 6 nodi, lì abbiamo 16 partizioni buone (10 da 3-3 e 6 da 1-5).
Per rispondere alle domande, non ho trovato errori nella tua dimostrazione, ma quella che avevo in mente usa solo il linguaggio della teoria dei grafi, e si scrive in brevi righe. Non è esattamente una "traduzione" della tua, anche perché tu dimostri una tesi un po' più generale, e le somme di righe che fai perdono significato nell'ambito del grafo. Appena ho qualche minuto, la scrivo.
Per intanto, posso proporre una bonus question: mostrare che il numero di queste partizioni è sempre una potenza di 2. Precisamente, l'esponente è la dimensione dell'intersezione dello spazio dei cicli e dello spazio dei tagli del grafo (per chi sa cosa sono...). Ritornando all'esempio del grafo completo con 6 nodi, lì abbiamo 16 partizioni buone (10 da 3-3 e 6 da 1-5).
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Ecco la dimostrazione alternativa (che secondo me è la book proof).
Induzione sul numero di nodi: se tutti i nodi hanno grado pari c'è la partizione banale, altrimenti esiste un nodo v di grado dispari. Faccio il complementare del sottografo dei vicini di v, tolgo v ed applico l'ipotesi induttiva. La partizione che ottengo ha da una parte un numero dispari di vicini di v, dall'altra un numero pari. Aggiungo v a quest'ultima parte, ed ho una partizione che risolve il problema sul grafo originario.
Induzione sul numero di nodi: se tutti i nodi hanno grado pari c'è la partizione banale, altrimenti esiste un nodo v di grado dispari. Faccio il complementare del sottografo dei vicini di v, tolgo v ed applico l'ipotesi induttiva. La partizione che ottengo ha da una parte un numero dispari di vicini di v, dall'altra un numero pari. Aggiungo v a quest'ultima parte, ed ho una partizione che risolve il problema sul grafo originario.
BELLO BAO! (come direbbe gente meno urbanizzata e più toscana di me). Presto mi arrenderò all'evidenza che tutti i problemi risolvibili alla francese hanno una soluzione alternativa di tre righe...Tibor Gallai ha scritto:Induzione sul numero di nodi: se tutti i nodi hanno grado pari c'è la partizione banale, altrimenti esiste un nodo v di grado dispari. Faccio il complementare del sottografo dei vicini di v, tolgo v ed applico l'ipotesi induttiva. La partizione che ottengo ha da una parte un numero dispari di vicini di v, dall'altra un numero pari. Aggiungo v a quest'ultima parte, ed ho una partizione che risolve il problema sul grafo originario.
"Sei la Barbara della situazione!" (Tap)