Problemino sui grafi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Problemino sui grafi

Messaggio da Karl Zsigmondy »

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!"
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Problemino sui grafi

Messaggio da EvaristeG »

Forse un grafo finito :) (anche se probabilmente per molti sta dentro la definizione di grafo)
Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Re: Problemino sui grafi

Messaggio da Karl Zsigmondy »

EvaristeG ha scritto:Forse un grafo finito :) (anche se probabilmente per molti sta dentro la definizione di grafo)
Sisi, finito! :)
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"
Avatar utente
Tess
Messaggi: 272
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: Problemino sui grafi

Messaggio da Tess »

È un esercizio carino! E non difficile!
Mi auguro che qualcuno con non molta esperienza si cimenti a risolverlo!

Ah, piccolo hint generale:
Testo nascosto:
Problema coi grafi $\rightarrow$ induzione, magari estesa.
Bisogna solo capire su cosa fare induzione...
Chuck Schuldiner
Messaggi: 308
Iscritto il: 11 feb 2012, 14:37
Località: Hangar 18

Re: Problemino sui grafi

Messaggio da Chuck Schuldiner »

Bagonzo io invece avevo seguito un'altra strada
Testo nascosto:
se per assurdo i cicli son tutti dispari, come sono disposti tra loro? e che succede se uccido tutti gli archi che compongono quei cicli?
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
Testo nascosto:
Immagine
Avatar utente
Tess
Messaggi: 272
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: Problemino sui grafi

Messaggio da Tess »

È vero, forse si può fare tutto in una volta!
Però, guardando sotto un punto di vista diciamo più formale,
Testo nascosto:
fai un'induzione in cui il passo induttivo è proprio quello che dici! :wink:
machete
Messaggi: 52
Iscritto il: 28 ago 2012, 15:44

Re: Problemino sui grafi

Messaggio da machete »

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?
Spargi il defoliante
sulla cassa dirigente
[anonimo]
Avatar utente
Tess
Messaggi: 272
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: Problemino sui grafi

Messaggio da Tess »

Servirebbe un po' più di formalità. In particolare non capisco bene l'ultimo paragrafo:
machete ha scritto:Supponiamo ora che partendo da ogni vertice non si possa mai raggiungerne un altro
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!

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:
machete
Messaggi: 52
Iscritto il: 28 ago 2012, 15:44

Re: Problemino sui grafi

Messaggio da machete »

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!
Spargi il defoliante
sulla cassa dirigente
[anonimo]
Avatar utente
Tess
Messaggi: 272
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: Problemino sui grafi

Messaggio da Tess »

Diciamo che fin prima della "conclusione" va bene. :wink:
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$.
Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Re: Problemino sui grafi

Messaggio da Karl Zsigmondy »

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.
Testo nascosto:
Sia k il numero totale di archi presenti in G.

LEMMA 1
Posso considerare wlog G connesso.
Dimostrazione: se non lo è, le sue componenti connesse hanno tutte vertici con grado maggiore uguale a 3 e mi rivolgo a quelle.

LEMMA 2
Ogni grafo G connesso ha al suo interno uno spanning tree (è possibile eliminare alcuni vertici di G facendo sì che rimanga solo un albero).
Dimostrazione: è nella lezione C2 medium del senior 2009, se volete posso metterla.

LEMMA 3
Il numero C di cicli presenti nel grafo è tale che: $ C \leq \frac{k}{3} $.
Dimostrazione: se due cicli dispari condividono un arco allora si può vedere che abbiamo un ciclo pari. Quindi i cicli dispari sono tutti disgiunti, e dal momento che sono lunghi almeno 3, il loro numero non può essere superiore a k/3.

LEMMA 4
Il numero C di cicli presenti nel grafo è tale che: $ C \geq k-(n-1) $
Dimostrazione: per il lemma 2 il grafo G ha al suo interno uno spanning tree, che ha per definizione n-1 archi. Se parto dallo spanning tree di G e aggiungo archi fino ad ottenere proprio G, per ogni arco che aggiungo fino ad arrivare a k creo almeno un nuovo ciclo, dal momento che unisco due vertici già precedentemente connessi da un altro cammino. Quindi creo almeno k-(n-1) cicli se G ha k archi.

Ora, per i lemmi 3 e 4 ho $ k-n+1 \leq C \leq \frac{k}{3} $ da cui segue che $ k \leq \frac{3n-3}{2} $. Ma dato che ogni vertice ha grado almeno 3 si ha che $ k \geq \frac{3n}{2} $, che è assurdo.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: Problemino sui grafi

Messaggio da Gottinger95 »

@Karl Zsigmondy: la dimostrazione funziona. Bella, molto pulita!
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Rispondi