Esercizi svolti di informatica n.2

Sia G un grafo con n nodi ed m archi. Dire se le seguenti affermazioni sono vere o false e giustificare la propria risposta:

1. tutte le foreste generate da differenti visite in profondità hanno lo stesso numero di alberi;
2. tutte le foreste generate da differenti visite in profondità hanno lo stesso numero di spigoli dell’albero e lo stesso numero di spigoli all’indietro.

SOLUZIONE.

Si ricordi che, dato un grafo G con k componenti connesse, qualsiasi foresta ricoprente (che sia generata da una visita in profondità o no) è formata esattamente da k alberi, uno per ciascuna componente connessa. Da questa semplice osservazione si deduce che la risposta al primo quesito è affermativa.

Anche la risposta al secondo quesito è affermativa; infatti ogni albero con a nodi ha a-1 spigoli, ed ogni foresta di k alberi con nnodi ha n-k spigoli. Pertanto il numero di spigoli dell’albero è uguale per tutte le foreste (sia quelle generate da visita in profondità che le altre). Per quanto riguarda gli spigoli all’indietro, si ricordi che una visita in profondità non produce spigoli di attraversamento, e quindi tutti gli spigoli non dell’albero sono all’indietro; ne consegue che tutte le foreste generate da differenti visite in profondità hanno m-(n-1)spigoli all’indietro.

Concludendo, mentre le proprietà descritte dalla prima affermazione e dalla parte della seconda affermazione riguardante gli spigoli dell’albero sono proprietà valide per tutti gli alberi ricoprenti, indipendentemente dal fatto che essi scaturiscano da una visita in profondità o no, la proprietà sugli archi all’indietro relativa alla seconda affermazione si basa pesantemente sulle proprietà degli alberi generati da visita in profondità.