Matematica discreta - Esercizi

18/1/2011

COGNOME E NOME..............................MATRICOLA........................................

Relazione nell’insieme S

Nell’insieme S = {2,4,5,6,10,12} si consideri la relazione e così definita h ^α o h = h_o (h,n) = p (numero primo >1)

1. Studiare ai rispetto alle proprietà di riflessività, simmetria, antisimmetria e transitività.
2. Determinare la rappresentazione grafica e matriciale.
3. Detto G_α, il grafo semplice associato, determinare se esistono un cammino euleriano, un cammino hamiltoniano, punti di taglio.

Operazioni nell’insieme Z₂₄

Dire quali delle seguenti operazione nell’insieme Z₂₄ inducono una struttura di gruppo.

1. (4)[(3*x)] = [3*x][8][x][*v] = [8*x+3][(6)[*v] = [5*x+4]

Nei casi affermativi, studiare il gruppo determinando i sottogruppi e, se esiste, un isomorfismo con il gruppo (Z₂₀, +)).

Dimostrazioni

Provare che il ricoprimento completo associato ad una relazione di equivalenza è una partizione.

1. (Teorema di Bezout) Siano a,b, interi non entrambi nulli e sia d = (a,b). Allora esistono h,k ∈ Z tali che d = h*a + k*b.
2. Un grafo è bipartito se e solo se non contiene cicli di lunghezza dispari.
3. L’insieme dei laterali formano una partizione del gruppo G.