[Grafi] Non diretto e connesso ha sempre almeno due nodi con lo stesso grado
Dimostrare che in un grafo non diretto e connesso G ci sono sempre almeno due nodi che hanno lo stesso grado.
Un modo sarebbe quello di inizializzare un array contenente il grado di un nodo.
Poi effettuo una DFS ed ogni volta che da un nodo scandisco i suoi adiacenti, inremento di 1 il grado del nodo adiacente nell'array dei gradi. La complessità sarebbe equivalente a quello di una DFS, ovvero O(n+m).
E' una soluzione valida? E' possibile formalizzarla diversamente? Esiste qualche altra dimostrazione?
Io purtroppo con le dimostrazioni non sono mai stato molto in gamba.
Grazie e buona serata
Un modo sarebbe quello di inizializzare un array contenente il grado di un nodo.
Poi effettuo una DFS ed ogni volta che da un nodo scandisco i suoi adiacenti, inremento di 1 il grado del nodo adiacente nell'array dei gradi. La complessità sarebbe equivalente a quello di una DFS, ovvero O(n+m).
E' una soluzione valida? E' possibile formalizzarla diversamente? Esiste qualche altra dimostrazione?
Io purtroppo con le dimostrazioni non sono mai stato molto in gamba.
Grazie e buona serata
Risposte
Non capisco il legame tra la richiesta di trovare una dimostrazione alla tesi con la creazione di un algoritmo per trovare se un grafo ha la proprietà richiesta. La soluzione non è certamente valida.
Trovare una dimostrazione non è diverso da trovare la soluzione ad un qualsiasi altro problema. Richiede un po' di esperienza, ma soprattutto impegno e pazienza. Esistono dei metodi euristici per aiutarci a trovare la soluzione, ma alla fine è solo questione di continuare a provare fino a quando non si trova la strategia giusta.
In questo caso si parte normalmente dalla tesi e si cerca di capire cosa possiamo dedurne. Cosa sai dei grafi non diretti e connessi? Sai dire qualcosa sul numero di nodi e archi? Sai dire qualcosa sul grado? Alcuni fatti che mi vengono per esempio in mente che potrebbero o meno portare ad una dimostrazione sono:
* Il numero di archi è compreso tra il numero di nodi N e il numero N*(N-1)/2.
* Il grado di un nodo è compreso tra 1 (il grafo è connesso per cui ogni nodo ha almeno un arco ad esso connesso) ed N-1 (ogni nodo è connesso a tutti gli altri - escludo la possibilità di archi da un nodo a se stesso).
A questo punto puoi iniziare a guardare alla tesi vera e propria. Devi dimostrare che ci sono almeno due nodi con lo stesso grado. Una prima strategia potrebbe per esempio essere quella di ragionare per assurdo. Inizi a supporre che tutti i nodi abbiamo un grado diverso e vedi se arrivi ad un assurdo. Ma un assurdo lo vediamo immediatamente dalla seconda osservazione nel punto 1. Ci sono N nodi, ma solo N-1 gradi possibili! Suppongo che altre dimostrazione avrebbero potuto essere trovate.
Trovare una dimostrazione non è diverso da trovare la soluzione ad un qualsiasi altro problema. Richiede un po' di esperienza, ma soprattutto impegno e pazienza. Esistono dei metodi euristici per aiutarci a trovare la soluzione, ma alla fine è solo questione di continuare a provare fino a quando non si trova la strategia giusta.
In questo caso si parte normalmente dalla tesi e si cerca di capire cosa possiamo dedurne. Cosa sai dei grafi non diretti e connessi? Sai dire qualcosa sul numero di nodi e archi? Sai dire qualcosa sul grado? Alcuni fatti che mi vengono per esempio in mente che potrebbero o meno portare ad una dimostrazione sono:
* Il numero di archi è compreso tra il numero di nodi N e il numero N*(N-1)/2.
* Il grado di un nodo è compreso tra 1 (il grafo è connesso per cui ogni nodo ha almeno un arco ad esso connesso) ed N-1 (ogni nodo è connesso a tutti gli altri - escludo la possibilità di archi da un nodo a se stesso).
A questo punto puoi iniziare a guardare alla tesi vera e propria. Devi dimostrare che ci sono almeno due nodi con lo stesso grado. Una prima strategia potrebbe per esempio essere quella di ragionare per assurdo. Inizi a supporre che tutti i nodi abbiamo un grado diverso e vedi se arrivi ad un assurdo. Ma un assurdo lo vediamo immediatamente dalla seconda osservazione nel punto 1. Ci sono N nodi, ma solo N-1 gradi possibili! Suppongo che altre dimostrazione avrebbero potuto essere trovate.
Ci sono riuscito grazie al principio della piccionaia.
Il grado di un qualsiasi nodo è compreso tra $1<=d(v)<=n-1$ dove n è il numero di nodi.
Quindi avendo n-1 valori possibili da assegnare ad ogni nodo, ed essendo i nodi n, allora inevitabilmente almeno due nodi avranno lo stesso grado.
Non so come formalizzarlo in linguaggio matematico. Fila il ragionamento?
Grazie mille per avermi indirizzato è molto intuitivo.
Il grado di un qualsiasi nodo è compreso tra $1<=d(v)<=n-1$ dove n è il numero di nodi.
Quindi avendo n-1 valori possibili da assegnare ad ogni nodo, ed essendo i nodi n, allora inevitabilmente almeno due nodi avranno lo stesso grado.
Non so come formalizzarlo in linguaggio matematico. Fila il ragionamento?
Grazie mille per avermi indirizzato è molto intuitivo.
Direi che l'hai già espresso in modo abbastanza formale. L'unica cosa che potresti aggiungere è qualche parola in più su quale sia la ragione per cui il grado è compreso tra quei valori.
Il grado di un nodo in un grafo connesso e non diretto sarà sempre compreso nell'intervallo [1,n-1], escludendo nodi isolati ed archi di tipo cappio, ovvero che hanno i due estremi coincidenti, dato che per rendere il grafo connesso da ogni nodo deve partire almeno un arco per un altro nodo, e al massimo un nodo può essere collegato a tutti gli altri.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo