Principio della casella: una rete di computer è composta da sei computer ...

Question

Una rete di computer è composta da sei computer. Ogni computer è direttamente connesso a zero o più degli altri computer.

Mostra che ci sono almeno due computer nella rete che sono collegati direttamente allo stesso numero di altri computer.

Ho capito che due computer non possono avere 0 e 5 connessioni contemporaneamente ma non posso andare avanti da lì.

Answer 1

Possiamo ancora usare la contraddizione. Hai già scoperto che se c'è un computer che non è collegato a nessun altro, gli altri computer possono avere al massimo$4$collegamenti. Se un computer è connesso a$5$ computer quindi non ci sono computer con $0$ connessione.

Quindi hai un numero di connessioni dirette per ogni computer tra $0$ per $4$ o tra $1$ per $5$. Questi sono$5$ numeri ma hai $6$computer. Quindi almeno due di loro hanno lo stesso numero di connessioni dirette.

Answer 2

Non è necessario utilizzare il principio della casella qui. Supponiamo di poter fare in modo che ogni computer abbia un numero diverso di connessioni. Rappresentiamo ogni computer come un vertice del grafo e ogni connessione come un bordo, quindi la somma dei gradi dei vertici è$15$ (come deve essere la sequenza dei gradi $5,4,3,2,1,0$). Ma questo è impossibile poiché la somma dei gradi deve essere pari e l'affermazione è dimostrata.

Answer 3

Possiamo dividerlo in due casi:

Caso 1: è presente un computer con $0$collegamenti. In questo caso, il numero totale di connessioni per un computer è$0,1,2,3$ o $4$ (poiché non può essercene uno con $5$collegamenti.). Queste sono cinque opzioni per sei computer e quindi devono esserci due con lo stesso numero di connessioni.

Caso 2: è presente un computer con $5$collegamenti. In questo caso, il numero totale di connessioni per un computer è$1,2,3,4$ o $5$ (poiché non può essercene uno con $0$collegamenti). Queste sono cinque opzioni per sei computer e quindi devono esserci due con lo stesso numero di connessioni.