COMBINATORIA

Claudia Malvenuto – Daniele A. Gewurz Scheda di esercizi n. 7

1. Dimostrare che il numero cromatico di qualsiasi albero con almeno due vertici è 2.

2. Sia K(n, r) il grafo (detto grafo di Kneser) che ha come vertici tutti i sottoinsiemi di cardinalità r di [n] e come archi le coppie di insiemi la cui intersezione è vuota.

(a) Si mostri che, per ogni n, K(n, 1) è isomorfo a K_{n}. Come è fatto K(n, n − 1)?

(b) Si trovi il numero cromatico di K(5, 2). (È isomorfo a un grafo visto in un precedente esercizio. Quale?)

3. Si consideri una carta geografica in cui il bordo complessivo delle regioni sia un circuito euleriano (equivalentemente: si tracci una curva chiusa, che può intersecare se stessa in vari punti, e si considerino le regioni del piano così identificate). Dimostrare che questa carta si può colorare con due colori.

4. Sia H_{n} il grafo che ha come vertici tutte le stringhe binarie di lunghezza n, e in cui due vertici sono adiacenti se differiscono in una sola posizione (tale grafo viene chiamato ipercubo di dimensione n). Dimostrare che H_{n} è un grafo bipartito.

5. Un ciclo di de Bruijn per le stringhe binarie di lunghezza n è una collana con perle 0 o 1 le cui sottostringhe lunghe n sono tutte le stringhe binarie di lunghezza n e di più dove ciascuna appare una sola volta.

Dimostrare che per ogni n esiste un ciclo di de Bruijn per le stringhe binarie di lunghezza n. (Suggerimento: considerare il grafo che ha come vertici le stringhe di lunghezza n−1, in cui due stringhe sono adiacenti se il suffisso di lunghezza n − 2 di una è uguale al prefisso di lunghezza n − 2 dell’altra.)

Descrivere esplicitamente un ciclo di de Bruijn per n = 3 e n = 4.

6. Se G è un grafo sconnesso, è ancora vero che G è bipartito se e solo se G non ha cicli dispari?

7. Dimostrare che il numero cromatico di G è il minimo numero di stabili che ricoprono G.

8. Siano dati un grafo G e una partizione P dei vertici di G in classi C_{i}, i = 1, …, r (cioè V (G) = ⋃_{i} C_{i} e gli insiemi C_{i} sono a due a due disgiunti). Consideriamo i grafi G[C_{i}] indotti dagli insiemi dei vertici delle parti C_{i} e definiamo un funzionale ψ che dipende dalla partizione P :

ψ(P) := ∑_{i=1}^{r}(1 + d(G[C_{i}])),

dove d(G[C_{i}]) è il grado del grafo G[C_{i}].

Dimostrare che

χ(G) = min{ψ(P) : P partizione dei vertici}.