Problemino sui grafi
- Karl Zsigmondy
- Messaggi: 138
- Iscritto il: 09 lug 2011, 14:32
- Località: Città di Altrove, Kansas
Problemino sui grafi
Sia G un grafo tale che la valenza/il grado di ogni vertice (il numero di archi uscenti da ogni vertice) sia maggiore o uguale a 3. Allora G contiene almeno un ciclo di lunghezza pari.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"
"Life is very short and there's no time for fussing and fighting, my friend!"
Re: Problemino sui grafi
Forse un grafo finito
(anche se probabilmente per molti sta dentro la definizione di grafo)
![Smile :)](./images/smilies/icon_smile.gif)
- Karl Zsigmondy
- Messaggi: 138
- Iscritto il: 09 lug 2011, 14:32
- Località: Città di Altrove, Kansas
Re: Problemino sui grafi
Sisi, finito!EvaristeG ha scritto:Forse un grafo finito(anche se probabilmente per molti sta dentro la definizione di grafo)
![Smile :)](./images/smilies/icon_smile.gif)
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"
"Life is very short and there's no time for fussing and fighting, my friend!"
Re: Problemino sui grafi
È un esercizio carino! E non difficile!
Mi auguro che qualcuno con non molta esperienza si cimenti a risolverlo!
Ah, piccolo hint generale:
Mi auguro che qualcuno con non molta esperienza si cimenti a risolverlo!
Ah, piccolo hint generale:
Testo nascosto:
-
- Messaggi: 308
- Iscritto il: 11 feb 2012, 14:37
- Località: Hangar 18
Re: Problemino sui grafi
Bagonzo io invece avevo seguito un'altra strada
Testo nascosto:
https://www.youtube.com/watch?v=35bqkTIcljs
Mare Adriatico: fatto
tetto del Di Stefano: fatto
finestra del Verdi: fatto
lavandino del Cecile: fatto
Arno: fatto
Mar Tirreno: fatto
Mar Ionio: fatto
tetto del Carducci: fatto
mura di Pisa: fatto
ho fatto più allo scritto in normale che alla maturità \m/
non aprire questo link
un pentacolo fatto col mio sangue
Mare Adriatico: fatto
tetto del Di Stefano: fatto
finestra del Verdi: fatto
lavandino del Cecile: fatto
Arno: fatto
Mar Tirreno: fatto
Mar Ionio: fatto
tetto del Carducci: fatto
mura di Pisa: fatto
ho fatto più allo scritto in normale che alla maturità \m/
non aprire questo link
un pentacolo fatto col mio sangue
Testo nascosto:
Re: Problemino sui grafi
È vero, forse si può fare tutto in una volta!
Però, guardando sotto un punto di vista diciamo più formale,
Però, guardando sotto un punto di vista diciamo più formale,
Testo nascosto:
Re: Problemino sui grafi
Esiste almeno un ciclo. Inizio a camminare da un punto a caso e segno i vertici su cui passo, dato che ogni volta che entro in un vertice ho almeno due modi per uscirne, ed essendo il grafo finito, dopo un po' passo per un vertice già segnato, quindi ho trovato un ciclo.
Considero due vertici a caso nel ciclo, diciamo A e B. Se esiste un cammino AB* che porta da A a B diverso da quello del ciclo ho vinto, infatti se la distanza sul ciclo fra A e B è pari e AB* è dispari posso a cambiare (passando per AB*) la parità del ciclo iniziale, se è pari passo per A e B sul ciclo iniziale e poi percorro AB*. Il caso in cui la distanza AB sul ciclo sia dispari è analogo.
Supponiamo ora che partendo da ogni vertice non si possa mai raggiungerne un altro. Prendo un vertice V e separo i vertici in X (i vertici raggiungibili da V) e Y (i vertici non raggiungibili da V ) chiaramente X ed Y non sono vuoti e non posso raggiungere un elemento di X da uno di Y. In X U {V} c'è almeno un ciclo (anche se V ha grado esattamente 3, lo si dimostra come prima) a questo punto ho tutte le ipotesi che avevo sul primo ciclo che è distinto da questo. Se anche i vertici del nuovo ciclo non sono mai raggiungibili ne scelgo uno diverso da V e riapplico lo stesso ragionamento, che chiaramente non può essere portato avanti all'infinito perché sto separando i vertici in infiniti sottinisiemi disgiunti.
Sarà vero?
Considero due vertici a caso nel ciclo, diciamo A e B. Se esiste un cammino AB* che porta da A a B diverso da quello del ciclo ho vinto, infatti se la distanza sul ciclo fra A e B è pari e AB* è dispari posso a cambiare (passando per AB*) la parità del ciclo iniziale, se è pari passo per A e B sul ciclo iniziale e poi percorro AB*. Il caso in cui la distanza AB sul ciclo sia dispari è analogo.
Supponiamo ora che partendo da ogni vertice non si possa mai raggiungerne un altro. Prendo un vertice V e separo i vertici in X (i vertici raggiungibili da V) e Y (i vertici non raggiungibili da V ) chiaramente X ed Y non sono vuoti e non posso raggiungere un elemento di X da uno di Y. In X U {V} c'è almeno un ciclo (anche se V ha grado esattamente 3, lo si dimostra come prima) a questo punto ho tutte le ipotesi che avevo sul primo ciclo che è distinto da questo. Se anche i vertici del nuovo ciclo non sono mai raggiungibili ne scelgo uno diverso da V e riapplico lo stesso ragionamento, che chiaramente non può essere portato avanti all'infinito perché sto separando i vertici in infiniti sottinisiemi disgiunti.
Sarà vero?
Spargi il defoliante
sulla cassa dirigente
[anonimo]
sulla cassa dirigente
[anonimo]
Re: Problemino sui grafi
Servirebbe un po' più di formalità. In particolare non capisco bene l'ultimo paragrafo:
Quando alla fine parli di un ragionamento "che non può essere portato avanti all'infinito", direi che è arrivata l'ora di usare il termine "induzione".
Se la riscivi, vedrò di rispondere alla tua domanda!![Wink :wink:](./images/smilies/icon_wink.gif)
Stai considerando da "vertice nel ciclo" a "vertice nel ciclo"? Se no, non vedo che vuol dire... Se sì, devi spiegare meglio anche il resto del paragrafo!machete ha scritto:Supponiamo ora che partendo da ogni vertice non si possa mai raggiungerne un altro
Quando alla fine parli di un ragionamento "che non può essere portato avanti all'infinito", direi che è arrivata l'ora di usare il termine "induzione".
Se la riscivi, vedrò di rispondere alla tua domanda!
![Wink :wink:](./images/smilies/icon_wink.gif)
Re: Problemino sui grafi
Sì in effetti sono stato frettoloso. . . vediamo di far meglio:
Lemma: Se in un grafo finito ogni vertice ha grado maggiore o uguale a due allora esiste almeno un ciclo.
dim. Inizio a camminare da un punto a caso e segno i vertici su cui passo, dato che ogni volta che entro in un vertice su cui non sono stato ho almeno un modo per uscirne, ed essendo il grafo finito, in un numero finito di passi arrivo in un vertice già segnato, quindi ho trovato un ciclo.
In particolare nel nostro problema esiste un ciclo $ c $. Se questo ciclo è pari ho finito, supponiamo sia dispari e distinguiamo due casi:
(i) Esistono due vertici $ A,\ B $ su $ c $ tali che esiste un cammino diverso da quello per $ c $ che li congiunge. Sia $ AB^* $ tale cammino e $ AB $ quello su $ c $. A questo punto se $ AB $ e $ AB^* $ hanno la stessa parità ho trovato un nuovo ciclo di lunghezza pari, se invece hanno parità diverse considero il ciclo $ c $ solo che invece di passare per $ AB $ passo per $ AB^* $, in questo modo ottengo un ciclo che ha parità diversa da quella di $ c $, cioè è pari.
(ii) Comunque io scelga una coppia di vertici $ A,\ B $ su $ c $ non esiste un percorso (diverso da $ c $ stesso) che li congiunga. Consideriamo quindi un qualsiasi vertice $ V $ di $ c $. A questo punto divido l' insieme dei vertici del mio grafo in due sottinsiemi $ X, Y $. In $ X $ metto i vertici che sono raggiungibili da $ V $ senza passsare per $ c $, in $ Y $ metto i vertici che sono raggiungibili da $ V $ solamente passando per $ c $. Dato che $ V $ ha grado $ \geq 3 $ posso muovermi da questo vertice senza stare su $ c $ quindi $ X $ è non vuoto. In $ Y $ ci sono per ipotesi almeno i vertici di $ c $ diversi da $ V $. Osserviamo poi che nessun elemento di $ X $ sta in $ Y $, altrimenti potrei connettere due vertici di $ c $ senza passare per $ c $ stesso.
A questo punto considero il grafo che ha come vertici $ X\cup \{ V\} $ e come archi gli archi del grafo iniziale tranne quelli che collegavano $ V $ a $ c $. Se il grado di $ V $ nel nuovo grafo è esattamente $ 1 $ tolgo $ V $ e posso applicare il Lemma per trovare un nuovo ciclo (interno a $ X\cup \{ V\} $), se il grado di $ V $ è maggiore di $ 1 $ applico subito il Lemma. Ho quindi trovato un nuovo ciclo $ c' $ contenuto in un sottoinsieme proprio dei vertici e degli archi del grafo iniziale.
A questo punto non so quale sia il modo migliore per concludere (sempre se si può concludere) ma io direi così:
Mi sono ricondotto al problema iniziale: se per $ c' $ non si verifica il caso (i) posso scegliere un nuovo vertice $ V'\neq V $ di $ c' $ da cui fare lo stesso ragionamento, e costruire un nuovo ciclo $ c'' $ strettamente contenuto in $ X\cup \{ V\} $. In ogni passaggio però considero un sottoinsieme proprio del grafo precedente e tale inclusione non può andare avanti all' infinito.
Probabilmente c'è un modo più rapido ed elegante per farlo (con un' induzione azzecata forse?) ma ci tenevo comunque a sapere se questo ragionamento regge!
Lemma: Se in un grafo finito ogni vertice ha grado maggiore o uguale a due allora esiste almeno un ciclo.
dim. Inizio a camminare da un punto a caso e segno i vertici su cui passo, dato che ogni volta che entro in un vertice su cui non sono stato ho almeno un modo per uscirne, ed essendo il grafo finito, in un numero finito di passi arrivo in un vertice già segnato, quindi ho trovato un ciclo.
In particolare nel nostro problema esiste un ciclo $ c $. Se questo ciclo è pari ho finito, supponiamo sia dispari e distinguiamo due casi:
(i) Esistono due vertici $ A,\ B $ su $ c $ tali che esiste un cammino diverso da quello per $ c $ che li congiunge. Sia $ AB^* $ tale cammino e $ AB $ quello su $ c $. A questo punto se $ AB $ e $ AB^* $ hanno la stessa parità ho trovato un nuovo ciclo di lunghezza pari, se invece hanno parità diverse considero il ciclo $ c $ solo che invece di passare per $ AB $ passo per $ AB^* $, in questo modo ottengo un ciclo che ha parità diversa da quella di $ c $, cioè è pari.
(ii) Comunque io scelga una coppia di vertici $ A,\ B $ su $ c $ non esiste un percorso (diverso da $ c $ stesso) che li congiunga. Consideriamo quindi un qualsiasi vertice $ V $ di $ c $. A questo punto divido l' insieme dei vertici del mio grafo in due sottinsiemi $ X, Y $. In $ X $ metto i vertici che sono raggiungibili da $ V $ senza passsare per $ c $, in $ Y $ metto i vertici che sono raggiungibili da $ V $ solamente passando per $ c $. Dato che $ V $ ha grado $ \geq 3 $ posso muovermi da questo vertice senza stare su $ c $ quindi $ X $ è non vuoto. In $ Y $ ci sono per ipotesi almeno i vertici di $ c $ diversi da $ V $. Osserviamo poi che nessun elemento di $ X $ sta in $ Y $, altrimenti potrei connettere due vertici di $ c $ senza passare per $ c $ stesso.
A questo punto considero il grafo che ha come vertici $ X\cup \{ V\} $ e come archi gli archi del grafo iniziale tranne quelli che collegavano $ V $ a $ c $. Se il grado di $ V $ nel nuovo grafo è esattamente $ 1 $ tolgo $ V $ e posso applicare il Lemma per trovare un nuovo ciclo (interno a $ X\cup \{ V\} $), se il grado di $ V $ è maggiore di $ 1 $ applico subito il Lemma. Ho quindi trovato un nuovo ciclo $ c' $ contenuto in un sottoinsieme proprio dei vertici e degli archi del grafo iniziale.
A questo punto non so quale sia il modo migliore per concludere (sempre se si può concludere) ma io direi così:
Mi sono ricondotto al problema iniziale: se per $ c' $ non si verifica il caso (i) posso scegliere un nuovo vertice $ V'\neq V $ di $ c' $ da cui fare lo stesso ragionamento, e costruire un nuovo ciclo $ c'' $ strettamente contenuto in $ X\cup \{ V\} $. In ogni passaggio però considero un sottoinsieme proprio del grafo precedente e tale inclusione non può andare avanti all' infinito.
Probabilmente c'è un modo più rapido ed elegante per farlo (con un' induzione azzecata forse?) ma ci tenevo comunque a sapere se questo ragionamento regge!
Spargi il defoliante
sulla cassa dirigente
[anonimo]
sulla cassa dirigente
[anonimo]
Re: Problemino sui grafi
Diciamo che fin prima della "conclusione" va bene.
Io la conclusione l'avevo pensata via induzione non su tutti i grafi con tutti i vertici di grado almeno 3, ma su i grafi cheper un vertice hanno grado almeno 2 e gli altri con grado almeno 3. A questo punto "rifare il ragionamento" si traduce in un "ricondursi ad un'ipotesi induttiva" (e l'induzione sarebbe ovviamente estesa).
Quello che potrebbe sembrar strano è il passo base: grafi troppo piccoli infatti, non hanno quella proprietà. Il passo base potrebbe essere il $K_4$.
![Wink :wink:](./images/smilies/icon_wink.gif)
Io la conclusione l'avevo pensata via induzione non su tutti i grafi con tutti i vertici di grado almeno 3, ma su i grafi cheper un vertice hanno grado almeno 2 e gli altri con grado almeno 3. A questo punto "rifare il ragionamento" si traduce in un "ricondursi ad un'ipotesi induttiva" (e l'induzione sarebbe ovviamente estesa).
Quello che potrebbe sembrar strano è il passo base: grafi troppo piccoli infatti, non hanno quella proprietà. Il passo base potrebbe essere il $K_4$.
- Karl Zsigmondy
- Messaggi: 138
- Iscritto il: 09 lug 2011, 14:32
- Località: Città di Altrove, Kansas
Re: Problemino sui grafi
Comunque si finisce così, manca poco!
Non so se quest'altra è giusta, ma mi torna più o meno ed è un pochino diversa. Potete dare un parere (vedere se è giusta) se volete.
![Smile :)](./images/smilies/icon_smile.gif)
Non so se quest'altra è giusta, ma mi torna più o meno ed è un pochino diversa. Potete dare un parere (vedere se è giusta) se volete.
Testo nascosto:
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"
"Life is very short and there's no time for fussing and fighting, my friend!"
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Problemino sui grafi
@Karl Zsigmondy: la dimostrazione funziona. Bella, molto pulita!
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe