Dimostrazione grado grafo connesso
Ciao a tutti ragazzi...
ho un problema da risolvere:
Se mi faccio un disegno di un grafo connesso e non diretto, effettivamente quanto detto sopra è vero... ma non capisco minimamente come si possa dimostrare questa cosa...
Qualcuno ha almeno un input da darmi?
Grazie...
ho un problema da risolvere:
Dimostrare che in un grafo non diretto e connesso G ci sono sempre almeno due nodi che hanno lo stesso grado.
Se mi faccio un disegno di un grafo connesso e non diretto, effettivamente quanto detto sopra è vero... ma non capisco minimamente come si possa dimostrare questa cosa...
Qualcuno ha almeno un input da darmi?
Grazie...
Risposte
[xdom="Raptorista"]Sebbene possa sembrare una domanda da ricerca operativa, mi suggeriscono di spostarla in algebra, dove riceverà maggiore attenzione.[/xdom]
Rifletti su questo: quali/quanti valori può assumere il grado di un vertice?
Allora...
il grado di un vertice è uguale al numero di archi incidenti nel vertice stesso....
Per essere connesso, vuol dire che ci devono stare minimo n-1 archi, dove n è il numero dei vertici...
il grado di un vertice è uguale al numero di archi incidenti nel vertice stesso....
Per essere connesso, vuol dire che ci devono stare minimo n-1 archi, dove n è il numero dei vertici...
Sto provando a pensare....
Allora...
Se il grafo è aciclico, vuol dire che abbiamo un albero... In tal caso le possibilità sono due:
- Le foglie dell'albero hanno tutte lo stesso grado (1);
- Nel caso di una sola foglia, allora questa ha lo stesso grado della radice (1);
Nel caso di un grafo con cicli.... ci penso su un attimo ancora...
Allora...
Se il grafo è aciclico, vuol dire che abbiamo un albero... In tal caso le possibilità sono due:
- Le foglie dell'albero hanno tutte lo stesso grado (1);
- Nel caso di una sola foglia, allora questa ha lo stesso grado della radice (1);
Nel caso di un grafo con cicli.... ci penso su un attimo ancora...
Niente... non riesco ad andare oltre...
No stai andando fuori strada...
Non pensare al numero di archi complessivo, ma quanti archi possono incidere al minimo/massimo su un determinato vertice?
Quindi quanti sono i possibili valori del grado di un particolare vertice?
Quanti sono i vertici?
Una volta risposto alle domande precedenti: è possibile che ogni vertice abbia un grado diverso da tutti gli altri?
Non pensare al numero di archi complessivo, ma quanti archi possono incidere al minimo/massimo su un determinato vertice?
Quindi quanti sono i possibili valori del grado di un particolare vertice?
Quanti sono i vertici?
Una volta risposto alle domande precedenti: è possibile che ogni vertice abbia un grado diverso da tutti gli altri?
"milizia96":
No stai andando fuori strada...
Non pensare al numero di archi complessivo, ma quanti archi possono incidere al minimo/massimo su un determinato vertice?
Allora... essendo un grafo connesso al minimo su un determinato vertice ci può incidere 1 arco;
Al massimo... n - 1 archi....
"milizia96":
Quindi quanti sono i possibili valori del grado di un particolare vertice?
Quindi, i possibili valori del grado di un particolare vertice possono essere n-1
"milizia96":
Quanti sono i vertici?
I vertici sono n...
"milizia96":
Una volta risposto alle domande precedenti: è possibile che ogni vertice abbia un grado diverso da tutti gli altri?
Quindi.. se ho capito bene.... se al massimo ci possono essere n-1 archi vuol dire che esiste almeno un nodo che ha lo stesso grado di un altro nodo... corretto?
Sì!
Abbiamo $n$ nodi, e ogni nodo ha un grado che può assumere uno dei valori $1$, $2$, ... $n-1$
E' impossibile che ogni nodo abbia un grado diverso! Infatti abbiamo $n-1$ valori possibili per "accontentare" $n$ nodi... insomma, è una cosa abbastanza intuitiva!
(è il famoso Pigeonhole principle)
Se vuoi, dimostra che la stessa cosa vale anche se il grafo non è connesso.
(è un po' più difficile)
Abbiamo $n$ nodi, e ogni nodo ha un grado che può assumere uno dei valori $1$, $2$, ... $n-1$
E' impossibile che ogni nodo abbia un grado diverso! Infatti abbiamo $n-1$ valori possibili per "accontentare" $n$ nodi... insomma, è una cosa abbastanza intuitiva!
(è il famoso Pigeonhole principle)
Se vuoi, dimostra che la stessa cosa vale anche se il grafo non è connesso.
Dimostrare che in un grafo non diretto ci sono sempre almeno due nodi che hanno lo stesso grado.
(è un po' più difficile)
Nel caso di un grafo non connesso, limiterei il problema ad una sua componente connessa...
In effetti...
Ma attento: dovresti considerare a parte il caso particolare in cui ogni componente connessa contiene esattamente un vertice!
Ma attento: dovresti considerare a parte il caso particolare in cui ogni componente connessa contiene esattamente un vertice!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo