Problemi irrisolti 24. Grafo di 9 vertici

Forum dedicato ai quesiti irrisolti presenti nella collezione di Base5, nel vecchio forum ed in quello attuale.

Moderatori: Gianfranco, Bruno

Rispondi
giobimbo
Livello 5
Livello 5
Messaggi: 257
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Problemi irrisolti 24. Grafo di 9 vertici

Messaggio da giobimbo »

Alla pagina 2 dei problemi irrisolti troviamo:
24. Grafo di 9 vertici
Un grafo è costituito da vertici e lati. I vertici sono generalmente rappresentati con piccoli cerchi e i lati con linee che congiungono due vertici.
Il grado di un vertice è il numero di lati che partono (o terminano) da quel vertice.
Considerate un grafo che ha 9 vertici e in cui ogni vertice ha grado 5 oppure 6.
Dimostrate che almeno 5 vertici hanno grado 6 oppure almeno 6 vertici hanno grado 5.

..Penso che il problema sia mal formulato.
Dalla frase
ogni vertice ha grado 5 oppure 6
intesa in senso inclusivo ricaviamo 6 possibili tipi di grafo, uno con 9 vertici di grado 6, un altro con 7 vertici di grado 6 e 2 di grado 5, un altro… Ovvero, in modo sintetico e più leggibile:

9x6....(7x6 e 2x5)....(5x6 e 4x5)....(3x6 e 6x5)....(1x6 e 8x5)....9x5

di cui un esempio con (1x6 e 8x5) è nella figura sotto.
Anche prendendo la frase “ogni vertice ha grado 5 oppure 6” in senso esclusivo, cioè togliendo il primo e l’ultimo caso in cui tutti i vertici hanno lo stesso grado, rimangono 4 tipi di grafo, mentre dal testo sembrerebbe che solo il terzo e quarto tipo siano possibili.
153 bsse5 grafo.png
153 bsse5 grafo.png (66.25 KiB) Visto 1223 volte

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 857
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Re: Problemi irrisolti 24. Grafo di 9 vertici

Messaggio da Admin »

Ciao giobimbo,
non ho ben capito il tuo ragionamento.

Io direi:

Piccioni = i $9$ vertici
Cassetti = le differenti tipologie di vertici (cassetto$1$ = vertici di grado $6$, cassetto$2$ = vertici di grado $5$).
Essendo $9$ i vertici, ed avendo $2$ cassetti, è chiaro che uno dei due cassetti conterrà sempre $5$ o più elementi.
Ossia vi saranno sempre almeno $5$ vertici di grado $6$, oppure almeno $5$ vertici di grado $5$.
CI siamo quasi.
CI basta dimostrare che il caso di $5$ vertici di grado $5$ non è possibile.
Vediamo.
Se avessimo $5$ vertici di grado $5$, avremmo i restanti $4$ di grado $6$.
Quindi avremmo come somma totale dei gradi dei vertici $5\cdot 5 + 4\cdot 6 = 49$
Il che non è possibile perchè sappiamo che tale somma deve essere pari.

Quindi scartando questo caso non possibile,
vi saranno sempre almeno $5$ vertici di grado $6$, oppure almeno $6$ vertici di grado $5$.

Saluti
Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

giobimbo
Livello 5
Livello 5
Messaggi: 257
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Problemi irrisolti 24. Grafo di 9 vertici

Messaggio da giobimbo »

Ragionamento perfetto, ma anch’io avevo detto più o meno questo (senza dimostrarlo), se guardi i due casi che adesso scrivo in rosso nel mio elenco dei grafi possibili:
9x6 (7x6 e 2x5) (5x6 e 4x5) (3x6 e 6x5) (1x6 e 8x5) 9x5

Quello che volevo dire è che il testo del problema non è preciso, visto che nel disegno dell’esempio da me fatto
ogni vertice ha grado 5 oppure 6
ma solo uno ha grado 6 e otto hanno grado 5.

Mi dici da dove viene questo problema?

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 857
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Re: Problemi irrisolti 24. Grafo di 9 vertici

Messaggio da Admin »

giobimbo ha scritto:
dom mag 17, 2020 11:27 am
Mi dici da dove viene questo problema?
il problema è presente nella collezione di Base5, QUI.
Non saprei pero' quale sia la fonte originaria.
Forse GIanfranco può aiutarci.

Saluti
Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

giobimbo
Livello 5
Livello 5
Messaggi: 257
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Problemi irrisolti 24. Grafo di 9 vertici

Messaggio da giobimbo »

Sì, tramite ricerca l'avevo trovato anch'io, ma non è molto illuminante; spero che Gianfranco legga questo intervento e sappia chiarire la questione.

Comunque sia è stato un piacere studiare la cosa, ho imparato delle cose nuove e interessanti.
:)

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1152
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Problemi irrisolti 24. Grafo di 9 vertici

Messaggio da Gianfranco »

giobimbo ha scritto:
lun mag 18, 2020 5:05 pm
Spero che Gianfranco legga questo intervento e sappia chiarire la questione.
Cari amici, non avevo scritto la fonte di questo problema perchè mi sembrava un esercizio di "normale amministrazione" senza un particolare valore storico.
Comunque, l'ho preso dal libro Introductory Graph Theory di Gary Chartrand, 1984 (corretto, 1985).
Si trova nel capitolo 2 e l'esercizio che lo precede chiede di dimostrare il Pigeonhole principle.
Ecco la citazione esatta:
grafo9_1.png
grafo9_1.png (24.53 KiB) Visto 1153 volte
Nelle ultime pagine del libro ci sono le soluzioni di molti esercizi, ma non di questo.
Chartrand_Intro_Graph.jpg
Chartrand_Intro_Graph.jpg (52.22 KiB) Visto 1153 volte
Pace e bene a tutti.
Gianfranco

giobimbo
Livello 5
Livello 5
Messaggi: 257
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Problemi irrisolti 24. Grafo di 9 vertici

Messaggio da giobimbo »

A questo punto direi di togliere questo problema dai casi irrisolti, la dimostrazione di Admin è più che chiara, è cristallina.
Io aggiungo solo che, provando a fare il disegno di tutti i casi possibili, ho scoperto di aver fatto un errore nei conteggi: il caso 9x5 non esiste. Col senno di poi ho anche capito il perché.
La matrice di adiacenza di un grafo è simmetrica, divisibile in due parti, quindi gli elementi diversi da zero sono in numero pari, allora i casi possibili sono solo quelli la cui somma dei gradi è un numero pari, cioè tutti meno 9x5=45 dispari.

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 857
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Re: Problemi irrisolti 24. Grafo di 9 vertici

Messaggio da Admin »

Gianfranco ha scritto:
lun mag 18, 2020 9:39 pm
Cari amici, non avevo scritto la fonte di questo problema perchè mi sembrava un esercizio di "normale amministrazione" senza un particolare valore storico.
Comunque, l'ho preso dal libro Introductory Graph Theory di Gary Chartrand, 1984.
Grazie Gianfranco per le info.
L'autore è di rilievo, e con la caratteristica di avere numero di Erdos 1.

Ok. Sposto nella sezione irrisolti ed aggiorno la pagina principale della sezione.

Saluti
Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1152
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Problemi irrisolti 24. Grafo di 9 vertici

Messaggio da Gianfranco »

Admin ha scritto:
mer mag 20, 2020 2:24 pm
L'autore è di rilievo, e con la caratteristica di avere numero di Erdos 1.
Ma guarda... non lo sapevo. Grazie a te Pietro per averci dato questa notizia.
Ho corretto la data di edizione del libro citato, che è il 1985.
Pace e bene a tutti.
Gianfranco

Rispondi