Grafi ad albero esercizio
Salve a tutti, potreste spiegarmi come si risolvono questi esercizi: "Stabilire se esiste un albero con 21 vertici di cui 1 di grado 5, 2 di grado 4, 3 vertici di grado 3, 3 di grado 2 e i restanti di ordine 1, e in caso affermativo disegnarlo.", e soprattutto come si determina se esiste un albero con tali caratteristiche?? Vi ringrazio
il 29 Dicembre 2015, da Andrea Manisi
Ciao Andrea. Un teorema della teoria dei grafi afferma che un qualsiasi albero i cui $n$ vertici abbiano gradi $d_1, d_2, \ldots, d_n$ soddisfa la seguente relazione: $$\sum_{i=1}^n d_i = 2n - 2$$Di conseguenza, se i dati forniti non rispettano questa uguaglianza allora siamo autorizzati ad affermare che un albero del tipo richiesto non esiste; se invece l'uguaglianza vale allora siamo tranquilli. Nel nostro caso $n=21$ e inoltre $d_1=5$, $d_2=d_3=4$, $d_4=d_5=d_6=3$, $d_7=d_8=d_9=2$; tutti gli altri $12$ vertici avranno grado $1$. Allora $$\sum_{i=1}^n d_i = 5 + 2\cdot 4 + 3 \cdot 3 + 3 \cdot 2 + 12 \cdot 1 = 40$$Questo numero è proprio uguale a $2n-2$, dato che $2 \cdot 21 - 2 = 42-2=40$: quindi l'albero che vogliamo esiste! Se vuoi disegnare un albero fatto così, invece, ti consiglio di provare da solo, anche perché di alberi che rispettano queste condizioni in realtà ce ne sono tantissimi: vai per tentativi e stai attento a rispettare la definizione di albero e di grado di un vertice. Buona serata :)