COMBINATORIA

Claudia Malvenuto Scheda di esercizi n. 2

1. Come sono fatti i grafi in cui ogni vertice ha grado 2?

2. Dare una caratterizzazione (condizione necessaria e sufficiente) affinché un grafo sia un ciclo.

3. Un grafo si dice autocomplementare se è isomorfo al suo complementare.

Dimostrare che se G è un grafo regolare autocomplementare, allora |V (G)| ≡ 1 (mod 4).

4. Siano F e G due grafi connessi. Dimostrare che il grafo F ∪G è connesso se e solo se V (F) ∩ V (G) ≠ ∅. (Si ricorda che il grafo unione F ∪ G è definito da V (F ∪ G) := V (F) ∪ V (G) e E(V ∪ G) := E(F) ∪ E(G).)

5. (a) Elencare tutti gli alberi di copertura del grafo completo su n vertici, per n = 1, 2, 3, 4 (alberi etichettati). Facoltativo: continuare con n = 5.

(b) Se con lt_{i} indichiamo il numero di alberi etichettati con i elementi (lt per labelled trees), scrivere i primi quattro (o cinque!) termini della successione lt_{1}, lt_{2}, lt_{3}, lt_{4}, …, quindi interrogare il sito

www.research.att.com/~njas/sequences (“On–line Encyclope-

dia of Integer Sequences”) per confrontare il risultato.

(c) Elencare tutti gli alberi non isomorfi su n vertici, per n = 1, 2, 3, 4, 5. Anche in questo caso interrogare la “On–line Encyclopedia of Integer Sequences” per gli alberi non isomorfi.

6. (Unicità dei cammini in un albero) Dimostrare che in una foresta esiste al più un cammino tra due vertici (quindi in un albero dati due vertici esiste esattamente un cammino tra di essi).

7. Dimostrare che in un albero su almeno 2 vertici esiste almeno una foglia (dove in un albero chiamiamo foglia ogni vertice di grado 1).

8. Dimostrare che in un albero su almeno 2 vertici esistono almeno due foglie.

9. Dimostrare che in un albero il numero di foglie (vertici di grado 1) è maggiore o uguale al grado dell’albero.

10. Sia fissato un cammino in un grafo connesso. Provare che esiste un albero di copertura del grafo che lo contiene (più generalmente: dato un albero che sia un sottografo del grafo di partenza, provare che esiste un albero di copertura che lo contiene).

11. Dimostrare che se H è un sottografo ricoprente di un grafo G allora per ogni x, y ∈ V (G) si ha

d_{H}(x, y) ≥ d_{G}(x, y).

12. Sia G un grafo. Fissato un suo albero di copertura T ⊆ G, si definisca l’applicazione d_{T} : V (G) × V (G) → R^{+} come d_{T} (x, y) = lunghezza del cammino di T (unico!) tra x e y (distanza tra due punti relativa all’albero T). Verificare che l’applicazione d_{T} : V (G) × V (G) → R^{+} è una distanza e che si ha:

d_{G}(x, y) = min_{T ⊆G} d_{T} (x, y).

13. Sia X un insieme su cui sia definita una famiglia di distanze

d_{h} : X × X → R^{+}, h ∈ I.

Fornire un esempio del fatto che l’applicazione d(x, y) = min_{h∈I} d_{h}(x, y) non è necessariamente una distanza.

14. Dimostrare che un grafo è una foresta se e solo se vale la seguente

relazione:

|V (G)| = |E(G)| + λ(G),

dove λ(G) denota il numero di componenti connesse del grafo G.