Dimostrare che un grafo semplice planare con $ n $ vertici ha al piu' $ 3n-6 $ archi e che se non si permettono triangoli, allora ha al piu' $ 2n-4 $ archi.
Bonus: dire inoltre se e quando e' possibile l'uguaglianza.
Numero di archi nei grafi planari
Poniamo che x=S/F dove S e la somma dei livelli di tutti i nodi e F è il numero delle facce.
Abbiamo banalmente che 2A=S (A=numero di archi) e che x è la media deli nodi comunicanti con ciascuna faccia (ovvero se ogni faccia è racchiusa da 3 nodi abbiamoi che x=3): questo si dimostra vedendo che separando tutte le facce, ogni nodo lo prendi tante volte quanto è il suo livello.
Quindi partendo da A+2=N+F dove N=n è il numero di nodi e A il numero di archi, possiamo arrivare a A+2=n+2A/x che a sua volta diventa A=(n-2)x/(x-2) che si massimizza riducendo x. Il minimo con più di una faccia (con meno di 2 facce questo ragionamento non vale, credo che avresti dovuto specificare n>2) è ovviamente x=3, quindi il massimo numero di archi è 3(n-2). Escludendo i triangoli abbiamo che il minimo di x è x=4 quindi il massimo numero di archi è 2(n-2). Si può ottenere con un bipartito completo (2,n-2), mentre l'altro caso (quello con i triangoli concessi) si ottiene facendo lo stesso bipartito disponendo gli n-2 punti su una retta, gli altri 2 una sopra la retta, uno sotto, e poi collegando il primo degli n-2 punti col secondo, il secondo col terzo, e così via e poi il primo con l'ultimo.
Ciao
Abbiamo banalmente che 2A=S (A=numero di archi) e che x è la media deli nodi comunicanti con ciascuna faccia (ovvero se ogni faccia è racchiusa da 3 nodi abbiamoi che x=3): questo si dimostra vedendo che separando tutte le facce, ogni nodo lo prendi tante volte quanto è il suo livello.
Quindi partendo da A+2=N+F dove N=n è il numero di nodi e A il numero di archi, possiamo arrivare a A+2=n+2A/x che a sua volta diventa A=(n-2)x/(x-2) che si massimizza riducendo x. Il minimo con più di una faccia (con meno di 2 facce questo ragionamento non vale, credo che avresti dovuto specificare n>2) è ovviamente x=3, quindi il massimo numero di archi è 3(n-2). Escludendo i triangoli abbiamo che il minimo di x è x=4 quindi il massimo numero di archi è 2(n-2). Si può ottenere con un bipartito completo (2,n-2), mentre l'altro caso (quello con i triangoli concessi) si ottiene facendo lo stesso bipartito disponendo gli n-2 punti su una retta, gli altri 2 una sopra la retta, uno sotto, e poi collegando il primo degli n-2 punti col secondo, il secondo col terzo, e così via e poi il primo con l'ultimo.
Ciao
"Sei la Barbara della situazione!" (Tap)