Esercitazioni di Matematica Discreta
1
Esercitazione del 26/02/2004
Definizione 1 ( Principio dei cassetti ) Se m oggetti sono distribuiti in n
cassetti e m > n allora almeno un cassetto riceve almeno 2 oggetti.
Definizione 2 ( Principio dei cassetti generalizzato ) Se m oggetti sono
distribuiti in n cassetti e m > rn allora almeno un cassetto riceve almeno r + 1
oggetti.
Esercizio 1 ( Il Principio dei cassetti e la teoria dei numeri )
Dimostrare che dati 3 numeri naturali qualsiasi, ce ne due la cui somma è pari.
Soluzione Scegliamo come oggetti i 3 numeri naturali e come cassetti le classi
di congruenza modulo 2, i.e. Z2 = {[0], [1]}. Per il principio dei cassetti almeno
uno dei cassetti contiene almeno 2 dei 3 numeri naturali, siano essi n1 , n2 .
Se n1 , n2 ∈ [0] −→ 2|n1 , 2|n2 quindi n1 , n2 sono entrambi pari e anche la
loro somma n1 + n2 risulta pari.
Se n1 , n2 ∈ [1] −→ 2|n1 − 1, 2|n2 − 1, quindi n1 , n2 sono entrambi dispari e
la loro somma n1 + n2 è pari.
Esercizio 2 ( Il Principio dei cassetti e la teoria dei grafi )
Un grafo G = (V, S) è individuato daun insieme V di vertici e da un insieme S
di spigoli. I vertici sono generalmente rappresentati come punti materiali e gli
spigoli con segmenti congiungenti due vertici. Il grado di un vertice è il numero
degli spigoli che partono (o che terminano) da quel vertice. Considerate un grafo
che ha 9 vertici e in cui ogni vertice ha grado 5 oppure 6. Dimostrate che almeno
5 vertici hanno grado 6 oppure 6 vertici hanno grado 5.
Soluzione Distribuiamo i 9 vertici in due cassetti A e B individuati rispettivamente dai vertici di grado 6 e dai vertici di grado 5. Poichè 9 > 8 = 4 × 2, per il
principio dei cassetti generalizzato almeno uno dei due cassetti contiene almeno
5 vertici. Si presenatno i seguenti casi:
I caso: |A| ≥ 5, ovvero ci sono nel grafo almeno 5 vertici di grado 6;
II caso: |B| ≥ 5, ovvero ci sono nel grafo almeno 5 vertici di grado 5.
Occorre provare che |B| > 5 e a tal fine procediamo per assurdo, supponiamo
che nel grafo ci siano esattamente 5 vertici
di grado 5 e i rimanenti 4 vertici
P
abbiano grado 6. Sappiamo che 2|S| = v∈V δ(v) = 5 × 5 + 6 × 4 = 49 e quindi
una contraddizione.
Esercizio 3 (Altre applicazioni del principio dei cassetti)
Ci sono 15 persone ad un festa e alcune di esse si scambiano un stretta di mano.
Dimostrare che almeno due persone hanno stretto lo stesso numero di mani.
Soluzione Si scelgono 14 cassetti tanti quanti il numero delle strette di mano
che si possono realizzare. Si noti che se c’è qualcuno che non ha stretto mani
allora non ci sarà qualcuno che ha stretto 14 mani. Si presentano le seguenti
situazioni. In un caso i cassetti saranno
BOX(1) = {persone che stringono 1 mano},
BOX(2) = {persone che stringono 2 mani},
..
..
.
.
BOX(14) = {persone che stringono 14 mani};
mentre nell’altro caso i cassetti saranno
BOX(0) = {persone che non stringono mani},
BOX(1) = {persone che stringono 1 mano},
..
..
.
.
BOX(13) = {persone che stringono 13 mani}.
In entrambi i casi il numero dei cassetti è 14 e poichè 15 > 14 segue che
almeno un cassetto contiene almeno due oggetti, ovvero ci sono almeno due
persone alla festa che hanno stretto lo stesso numero di mani.
Esercizio 4 In una foresta ci sono un milione di alberi. Ciascun albero ha non
più di 600.000 foglie. Si dimostri che in ogni istante ci sono due alberi nella
foresta che hanno lo stesso numero di foglie.
Soluzione Distribuiamo gli alberi della foresta in 600.001 cassetti costruiti come
segue: per 0 ≤ i ≤ 600.000, definiamo il cassetto i-esimo quello individuato dagli
alberi che contengono un numero i di foglie. Poichè 1.000.000 > 600.000, esiste
almeno un cassetto che contiene almeno due alberi e quindi ci sono almeno due
alberi che contengono lo stesso numero di foglie.
Esercizio 5 Scrivere la formula esplicita per un quando:
u0 = 0, u1 = 1
un+2 = un+1 − un
n≥0
Soluzione√L’equazione algebrica
associata è t2 − t + 1 = 0 le cui soluzioni sono
√
3
3
1
1
t = 2 ± i 2 . Poichè 2 + i 2 = cos π3 + i sin π3 , scriviamo
un
√
√
1
1
3 n
3 n
= A( + i
) + B( − i
) =
2
2
2
2
πn
πn
πn
πn
+ i sin
) + B(cos
− i sin
)=
= A(cos
3
3
3
3
πn
πn
+ i(A − B) sin
.
= (A + B) cos
3
3
Imponendo le condizioni iniziali otteniamo:
un =
πn
2√
.
3 sin
3
3
Esercizio 6 (Applicazione del principio di induzione)
Dimostrare che per ogni intero n > 0 il numero 7n3 − 7n + 42 è un multiplo di
21.
Esercizio 7 (Applicazione del principio di inclusione-esclusione)
Una azienda vende 12.700 sets di cui 8.000 T.V., 5.000 V.H.S. Di questi sets
sono stati venduti 3.200 T.V + Decoder, 3.500 T.V. + V.H.S.,700 V.H.S +
Decoder, 1.000 T.V.+ V.H.S.+ Decoder. Quanti decoder sono stati venduti?
Soluzione Indichiamo con A1 l’insieme delle T.V. vendute, A2 l’insieme dei
V.H.S., A3 l’insieme dei decoder e per il principio di inclusione-esclusione abbiamo
|A3 | = |A1 ∪A2 ∪A3 |−|A1 |−|A2 |+|A1 ∩A2 |+|A1 ∩A3 |+|A2 ∩A3 |−|A1 ∩A2 ∩A3 | =
= 12.700 − 8.000 − 5.000 + 3.500 + 3.200 + 700 − 1.000 = 6.100
Esercizio 8 (Applicazione del principio di contare per righe e per
colonne) In una classe ci sono 32 ragazzi e n ragazze. Ogni ragazzo conosce 5
ragazze della classe e ogni ragazza conosce 8 ragazzi della clase. Quante ragazze
ci sono nella classe?
Soluzione Realizziamo una matrice di ordine n × 32, disponendo le ragazze sulle
righe e i ragazzi sulle colonne. Mettiamo un Xnel posto (i, j) della matrice se la
ragazza i-esima e il ragazzo j-esimo si conoscono. Contando il numero di Xper
righe, esso risulta 8n; mentre contando per colonne il numero di Xrisulta 5 × 32.
Abbiamo 8n = 5 × 32 → n = 20 e quindi nella classe ci sono 20 ragazze.
Esercizio 9 (Applicazione del principio di contare per righe e per
colonne)Una azienda di 30 operai vuole partecipare ad un torneo di calcetto
( ogni squadra è composta da 5 giocatori) e tale torneo consiste di 28 incontri. Ogni giocatore deve giocare lo stesso numero di partite ed ovviamente deve
giocare almeno una partita. È possibile che l’azienda partecipi a tale torneo di
calcetto, ovvero il problema ammette soluzione? Se gli incontri sono 24, quante
partite deve giocare ogni giocatore?
2
Esercitazione del 10/03/2004
Definizione 3 (Funzione di Eulero) Per ogni intero n ≥ 1, indichiamo con
Φ(n) = il numero degli interi x tali 1 ≤ x ≤ n e tali che M.C.D.(x, n) = 1.
Esercizio 10 Quanti sono gli interi x multipli di 3 tali che 316 ≤ x ≤ 317 ?
Soluzione Φ(317 ) = numero degli interi x con 1 ≤ x ≤ 317 e coprimi con 317 ,
poichè 3 è l’unico divisore primo di 317 segue che Φ(317 ) = numero degli interi
x con 1 ≤ x ≤ 317 e coprimi con 3. Analogamente Φ(316 ) = numero degli interi
x con 1 ≤ x ≤ 316 e coprimi con 3. Pertanto il numero cercato è
317 − Φ(317 ) − (316 − Φ(316 )) = 317 − 317 (1 − 31 ) − 316 + 316 (1 − 31 ) = 2 · 315 .
Proposizione 4 Per ogni intero n ≥ 1, risulta
P
d|n
Φ(d) = n.
Esercizio 11 Riflessioni sul teorema cinese del resto
Ricordiamo l’enunciato del teorema cinese del resto. Il sistema di congruenze
½
x ≡ a(mod n)
,
x ≡ b(mod m)
con a, b interi qualsiasi, ammette soluzioni se e soltanto se M.C.D.(m, n) = 1.
Inoltre la soluzione generale si ottiene aggiungendo ad una soluzione particolare
un arbitrario multiplo di n · m. Tale risultato si generalizza ad un sistema con
un numero finito qualsiasi di congruenze. Le nostre riflessioni iniziano dalla
considerazione del seguente esempio
Esempio 5 Il seguente sistema
½
x
x
≡
≡
1 (mod 7)
2 (mod 7)
non ammette soluzioni e si noti che il gruppo Z7 ⊕Z7 non è ciclico. Una soluzione
della prima congruenza è del tipo x = 7t + 1, con t ∈ Z, sostituendola nella
seconda equazione otteniamo 7t + 1 ≡ 2(mod 7) → 7|7t + 1 − 2 = 7t − 1.
Otteniamo un risultato contraddittorio infatti se esistesse un intero k tale che
7t − 1 = 7k avremmo 7(t − k) = 1.
Ma la domanda che adesso dobbiamo porci è: esistono interi a, b tali che il
sistema
½
x ≡ 1 (mod 7)
x ≡ 2 (mod 7)
ammetta soluzioni? Si, basti per esempio pensare al sistema con a = b ( caso
banale). Presentiamo un caso non banale.
Esempio 6
½
x ≡
x ≡
0 (mod 6)
a (mod 15)
Osserviamo che M.C.D(6, 15) = 3 e che il sistema ammette soluzioni non appena
scegliamo a ∈ [6t] = {[0], [6], [12], [3], [9]} e si noti che |h6i| = 5.
L’affermazione del teorema cinese del resto risulta molto forte, infatti garantisce la risolubità del sistema di congruenze qualunque sia la scelta delle condizioni iniziali a, b. Mentre se M.C.D(n, m) 6= 1, la risolubità del sistema dipende
dalla scelta delle condizioni iniziali.
Esercizio 12 Un ristorante aperto tutti i giorni a partire da oggi propone ogni
5 giorni come primo piatto lasagne, a partire da domani proporrà ogni 6 giorni
come secondo piatto pollo con contorno di patate, a partire da dopodomani proporrà ogni 7 giorni come dolce il tiramisù. Possiamo stabile che nell’arco di un
anno il menù del giorno sarà: Lasagne, Pollo con contorno di patate e tiramisù.
Soluzione

 x ≡ 1 (mod 5)
x ≡ 2 (mod 6)

x ≡ 3 (mod 7)
essendo M.C.D.(5, 6, 7) il sistema sopra proposto ammette soluzioni per il
teorema cinese del resto e adesso occorre determinarne le soluzioni.
Calcoliamo l’ inverso di 6 · 7 modulo 5
42 · c1 ≡ 1(mod 5) → 5| → 42c1 − 1 → c1 = 3;
Calcoliamo l’ inverso di 5 · 7 modulo 6
35 · c2 ≡ 1(mod 6) → 6| → 35c2 − 1 → c2 = −1;
Calcoliamo l’ inverso di 6 · 5 modulo 7
30 · c3 ≡ 1(mod 7) → 7| → 30c3 − 1 → c3 = 4.
Una soluzione particolare è
c = 1 · c1 · 6 · 7 + 2ċ2 · 5 · 7 + 3 · c3 · 5 · 6 = 126 − 70 − 360 = 416.
Poichè 416 ≡ 206(mod 210), la soluzione generale è
x = 206 + 210k
k ∈ Z.
Altro metodo.
x ≡ 1(mod 5) → 5|x − 1 → x = 5t + 1,
la quale sostituita nella seconda equazione diventa
5t + 1 ≡ (mod 6) → 5t − 1 = 6k → t = −1.
Pertanto la soluzione del sistema
½
x ≡ 1 (mod 5)
x ≡ 2 (mod 6)
risulta x = −4 + 30n, con n intero qualsiasi. Quest’ultima sostituita nella terza
equazione del sistema di partenza dà luogo a
−4 + 30n ≡ 3(mod 7) → 7| − 4 + 30n − 3 = −7 + 30n → −7 + 30n = 7k → n = 7;
la soluzione generale del sistema risulta
x = −4 + 210 + 210m = 206 + 210m
∀ m ∈ Z.
Esercizio 13 Contare il numero delle parole sull’alfabeto {a, b, c, d} di lunghezza
compresa tra 1 e 5 ( inclusi) che non soddisfano alcuna delle seguenti condizioni:
1. hanno lunghezza 3;
2. non contengono la lettera a.
Soluzione Sia A = {parole sopra indicate} e si osservi che |A| = 4 + 42 +
43 + 44 + 45 . Le parole del tipo considerato altro non sono che applicazioni di
Nn −→ {a, b, c, d}, con n = 1, 2, 3, 4. Sia A1 il sottoinsieme di A individuato dalle
parole che soddisfano la condizione 1 e A2 quello individuato dalle parole che
soddisfano la condizione 2. Il numero cercato è
|A| − |A1 ∪ A2 | = |A| − |A1 | − |A2 | + |A1 ∩ A2 |.
Osservando che
|A1 | = 43
|A2 | = 3 + 32 + 33 + 34 + 35
|A1 ∩ A2 | = 33
otteniamo che |A| − |A1 ∪ A2 | = 964.
3
Esercitazione del 16/03/2004
Esercizio 14 Proprietà della funzione di Eulero
Sia n ≥ 2 intero la cui fattorizzione in primi distinti è n = pe11 pe22 . . . perr . Si
dimostra che
1
r
1
Φ(n) = n(1 − )(1 − ) . . . (1 − ).
p1
p2
pr
Esercizio 15 Una donna ha 11 amici.
1. In quanti modi può invitarne 5 a pranzo?
2. In quanti modi può invitarne 5 a pranzo se due amici sono sposati e non
partecipano separatamenre?
3. In quanti modi può invitarne 5 a pranzo se due non sono in buoni rapporti
e non partecipano insieme?
Soluzione 1. Si tratta di selezione senza ripetizione e senza ordine di 5 oggetti
distinguibili
da un insieme di 11 oggetti distinguibili e pertanto tale numero è
¶
µ
11
= 462 modi.
5
2. Indichiamo con A, B gli amici sposati e distinguiamo i seguenti casi:
µ ¶
9
= 126 modi;
• se A, B sono esclusi dall’invito allora avremo
5
¶
µ
9
= 84 modi;
• se A, B sono inclusi nell’invito allora avremo
3
in totale avremo 126 + 84 = 210 modi.
3. Se C, D non partecipano insieme.
µ Se¶C, D partecipano insieme al pranzo,
9
i rimanenti 3 amici vengono scelti in
= 84 modi e quindi avremo
3
µ
¶ µ ¶
11
9
−
= 462 − 84 = 378
5
3
Esercizio 16 Quante colonne del totocalcio si possono realizzare se vogliamo
che esse contengono 5 segni uguali a X?
Soluzione Le colonne del totocalcio non sono altro che parole di lunghezza 13
nell’alfabeto 1, 2,µX. Le¶colonne cercate contengono esattamente 5 simboli uguali
13
a X e pertanto
è il numero delle ”collocazioni ” del simbolo X in una
5
colonna. Una volta assegnato il simbolo x, dobbiamo sistemare i simboli 1, 2
nei rimanenti 8 posti, cioè dobbiamo considerare
µ
¶ tutte le parole di lunghezza 8
13
nell’alfabeto {1, 2}. Il numero cercato è
× 28 .
5
Esercizio 17 In quanti modi possiamo selezionare un ordine di battitura di 11
giocatori da una squadra di cricket (composta da 14 giocatori)?
Soluzione Si tratta di selezioni senza ripetizioni di 11 oggetti distinguibili da un
insieme di 14 e pertanto un ordine di battitura del tipo richiesto corrisponde ad
una applicazione iniettiva f : N11 → N14 . Il numero cercato è 14 · 13 · 12 . . . 5 · 4.
Esercizio 18 Quanti numeri telefonici di 5 cifre hanno almeno una cifra che
interviene più di una volta?
I numeri telefonici di 5 cifre non sono altro che applicazioni di N5 → N10 e
pertanto son 105 ; i numeri telefonici di 5 cifre senza ripetizione non sono altro
che le iniezioni N5 → N10 e sono 10 · 9 · 8 . . . 6 = 30.240. Il numero cercato è
105 − 30.240 = 69.760.
Esercizio 19 Quante sono le possibili cinquine al lotto?
Soluzione Si tratta di selezione senza ordine e senza ripetizione di 5µ oggetti
¶
90
.
distinguibili da un insieme di 90 oggetti e quindi il numero cercato come
5
Esercizio 20 Cinque ragazzi leggono un libro ciascuno. In quanti modi si possono scambiare tra loro i libri in modo che ognuno riceva un libro diverso da
quello letto?
Soluzione Applicazione del principio della segretaria distratta.
5!(1 − 1! +
1
1
1
1
− + − ) = 44
2! 3! 4! 5!
Esercizio 21 Si devono preparare delle vernici utilizzando 4 colori. Per ottenere una vernice si procede come segue: vi sono 6 misurini di eguale capacità
ed ognuno viene riempito con un dei colori, poi il contenuto viene mescolato per
ottenere una singola vernice. Quante vernici si possono ottenere?
Esercizio 22 Si deve dipingere una palizzata di 10 pali disposti ordinatamente
in fila, utilizzando alcuni colori fra 8 colori a disposizione ( fra cui c’è il rosso).
In quanti modi si può colorare la palizzata se si pretende che esattamente 3 pali
siano colorati in rosso?
Esercizio 23 Un lucchetto ha la serratura a combinazione di 3 cifre; quanti
tentativi deve essere disposto a fare un ladro per essere certo di aprire il lucchetto?
Soluzione Ogni combianzione del lucchetto corrisponde ad una applicazione di
N3 → N10 e pertanto il numero cercato è 103 = 1.000
Esercizio 24 In quanti modi un insegnante può scegliere uno o più studenti tra
6 studenti?
Soluzione Si tratta di selezione senza ordine e senza ripetizione di oggetti distinguibili da un insieme di 6 oggetti. Si osservi che 26 = 64 è il numero dei
sottoinsiemi dell’insieme formato da 6 studenti. L’insieme ∅ deve essere trascurato poichè esigiamo che vengano scelti uno o più studenti. Ci sono 26 − 1 = 63
modi di scegliere gli studenti.
Esercizio 25 Quanti sono i possibili anagrammi della parola AMARENA ?
Soluzione Gli anagrammi considerati sono parole di lunghezza 7 nell’alfabeto
{A, M, R, E, N } tali che la lettera A interviene esattamente 3 volte. Inµprimo
¶
7
luogo, occorre decidere dove sistemare la lettera A e per fare ciò ci sono
3
modi. Rimangono
µ 4¶posti dove sistemare le 4 lettere M, R, E, N. Il numero degli
7
anagrammi è
· 4!.
3
Esercizio 26 Dato l’insieme A = {a, b, c, d, e, f, g, h, i}. Calcolare il numero dei
sottoinsiemi non vuoti di A che soddisfano almeno una delle condizioni:
1. hanno ordine pari;
2. sono sottonsiemi di {b, d, e, f, i}.
Soluzione Il numero cercato è 887
4
Esercitazione del 24/04/2004
Esercizio 27 In quanti modi si può colorare una palizzata di 7 pali avendo a
disposizione 4 colori da utilizzare contemporaneamente ?
Esercizio 28 13 amici viaggiano con 3 auto a, b, c. Devono salire 6 persone
sull’auto a, 4 sull’auto b e 3 sull’auto c. In quanti modi possono suddividersi?
Esercizio 29 Quante sono le schedine del totocalcio in cui ci sono sei 1, quattro
2 e tre X?
Gli ultimi due esercizi chiedono di contare il numero delle applicazioni da un
n-insieme ad un k-insieme, le cui fibre hanno ciascuna una cardinalità prestabilita. Si osservi che supponiamo che gli elementi di tali insiemi siano oggetti
distinguibili tra loro.
Definizione 7 Sia g : X → B una applicazione. Denotiamo col simbolo g −1 =
{x ∈ X|g(x) = b} e chiameremo tale insieme fibra di g sull’elemento b di B o
controimmagine di b mediante g.
Siano
n, k, n1 ,¶
. . . , nk interi non negativi tali che n1 + n2 + . . . nk = n.
µ
n
= il numero delle applicazioni di X = {1, . . . , n} → A =
n1 , . . . , n k
{a1 , . . . , ak } per le quali la controimmagine di ai abbia ni elementi per ogni
i = 1, . . . , k.
Altra interpretazione.
µ
¶
n
Con il metodo del linguaggio, il numero multinomiale
conta le
n1 , . . . , n k
parole di lunghezza n nell’ alfabeto {a1 , . . . , ak } di k lettere, in modo tale che
la lettera a1 sia ripetuta n1 volte, la lettera a2 sia ripetuta n2 volte, . . . e ak sia
ripetuta nk volte.
Esercizio 30 Quante parole di 11 lettere si possono comporre con le lettere
della parola MISSISSIPPI?
Soluzione
µ
11
1, 4, 4, 2
¶
= 11 × 10 × 9 × 7 × 5.
Esercizio 31 Calcolare il numero delle applicazioni
f : A = {1, 2, 3, 4, 5, } → B = {a, b, c, d, e, f, g}
tali che immagini di A formino un insieme di ordine 3.
Soluzione
µ
7
3
¶
3!S(5, 3) = 210S(5, 3).
Definizione 8 Sia X un insieme non vuoto di cardinalità v. Diremo che un
insieme B di k-sottoinsieme di X è un 1-disegno con parametri (v, r, k) se
∀ x ∈ X appartiene esattamente a r dei k-sottoinsiemi di B; gli elementi di X si
dicono punti del disegno, mentre i k-sottoinsiemi si dicono blocchi del disegno.
Sappiamo che C.N.S. per l’esistenza di un 1-disegno di parametri (v, k, r)
• k|vr;
vr
≤
•
k
µ
v
k
¶
.
Esercizio 32 Sia B l’insieme dei blocchi di un disegno di parametri (v, k, r) e
sia B 0 l’insieme dei complemenatri B c dei blocchi B in B. Dimostrare che B 0 è
anche un disegno e individuarne i parametri.
Soluzione Siano (v 0 , k 0 , r0 ) i parametri del disegno cercato. L’insieme dei punti
è X e quindi v 0 = v.
B 0 = {B c |B ∈ B} pertanto i suoi elementi saranno (v − k)-sottoinsiemi di X
e quindi k 0 = v − k. Qualsiasi x ∈ X appartiene esattamente a r blocchi di B
e quindi non appartiene ai rimanenti vr
k − r blocchi di B. Abbiamo che ogni x
appartiene esattamente a vr
−
r
blocchi
di B 0 e quindi r 0 = vr
k
k − r. Concludiamo
0
che B sono i blocchi di un disegno di parametri (v, v − k, vr
k − r).
Esercizio 33 Qual è il valore di r del disegno i cui blocchi sono tutti i ksottoinsiemi di un v-insieme?
¶
µ
v
= numero dei blocchi. Qualsiasi x ∈ X appartiene esattamente
Soluzione
k
¶
µ
v−1
= numero dei blocchi che non
a r blocchi del disegno e si osservi che
k
contengono x. Il numero dei blocchi che contengono x risulta
µ
µ
¶ µ
¶
¶
v(v − 1)! (v − 1)!
v
v−1
v−1
−
= (v − 1)
−
.
=
k
k
k
k!
k!
µ
¶
v−1
Pertanto r = (v − 1)
.
k
Esercizio 34 Per quali valori (v, k, r) esiste un disegno con questi parametri?
1. (6, 3, 1);
2. (7, 3, 3);
3. (5, 2, 1);
4. (9, 6, 4).
5
Esercitazione del 27/04/2004
Definizione 9 Un grafo G = (V, S) consiste di un insieme V , i cui elementi
chiameremo punti o vertici, di un insieme S di 2-insiemi di V che chiameremo
spigoli e di una relazione di adiacenza R tra i vertici definita come segue:
∀ v1 , v2 ∈ V, v1 6= v2 v1 Rv2 ↔ {v1 , v2 } ∈ S.
La proprietà caratterizzante un grafo è la relazione di adiacenza che sussiste
tra i suoi vertici. Ciò motiva la seguente definizione.
Definizione 10 Due grafi G1 = (V1 , S1 ) e G2 = (V2 , S2 ) si dicono isomorfi se
esiste α : V1 −→ V2 applicazione biunivoca tale che ∀ x, y ∈ V1 , x 6= y
{α(x), α(y)} ∈ S2 ↔ {x, y} ∈ S1 .
L’applicazione biunivova α si dice isomorfismo di grafi. Quando due grafi
G1 e G2 sono isomorfi, essi possono essere presentati come lo ”stesso” grafo.
Pertanto due grafi non sono isomorfi se non esiste alcuna applicazione biunivoca
dall’insieme dei vertici di uno all’insieme dei vertici dell’altro che porta spigoli
in spigoli.
Osserviamo che
• Se due grafi sono isomorfi allora presentano lo stessso numero di vertici;
• Se due grafi sono isomorfi allora presentano lo stessso numero di spigoli.
Domanda: Se due grafi presentano lo stesso numero di vertci e di spigoli, essi
risultano isomorfi? In generale no.
Per rispondere a questa domanda, presentiamo alcune riflessioni. Si noti che
se α : G1 −→ G2 è un isomorfismo di grafi tali che α(v) = w. Ogni spigolo
contenente il vertice v viene trasformato mediante α in uno spigolo contenente
w e pertanto δ(v) = δ(w).
Conseguenza: se G1 è un grafo con un vertice x tale che δ(x) = n e G2 è un
grafo che non presenta vertici di grado n allora i due grafi non sono isomorfi.
Esempio 11 Sia G1 = (V1 , S1 ) con V1 = {1, 2, 3, . . . , 6} e
S1 = {{1, 4}, {3, 4}, {2, 4}, {2, 6}, {6, 5}, {5, 2}};
Sia G2 = (V2 , S2 ) con V2 = {a, b, . . . , f } e
S2 = {{a, b}, {b, c}, {c, d}, {d, e}, {e, f }, {g, h}}. I grafi G1 e G2 presentano 6
vertici e 6 spigoli ma non sono isomorfi; infatti δ(1) = 1 mentre G2 è un grafo
2-regolare.
Ricordiamo che
• Il numero delle componenti connesse di un grafo è un invariante sotto
l’azione degli isomorfismi;
• Il numero cromatico di un grafo è un invariante sotto l’azione degli isomorfismi.
Esercizio 35 Si consideri il grafo G i cui vertici sono i numeri interi 1, 2, . . . , 30
e in cui due vertici distinti x, y sono adiacenti se il prodotto xy è pari.
1) Il grafo proposto è connesso?
2) Esiste un cammino e un circuito euleriano?
3) Determinare il numero cromatico di G.
Esercizio 36 Sia G un grafo bipartito con un numero dispari di vertici. Dimostrare che G non possiede un circuito hamiltoniano
Esercizio 37 A partire da un insieme finito X di cardinalità n ≥ 5, si definisca
un grafo Gn = (V, S) nel modo seguente
V consiste di tutti i sottoinsiemi di X di cardinalità 2
S = {{v 0 , v 00 }, v 0 , v 00 ∈ V | v 0 ∩ v 00 = ∅}.
Segnare l’affermazione sbagliata.
a) Gn è connesso per ogni n ≤ 5;
b) ogni vertice di Gn ha grado
(n−2)(n−3)
;
2
c) esistono in Gn cammini euleriani per ogni n ≤ 5.
6
Esercitazione del 3/05/2004
Definizione 12 Sia G = (V, S) un grafo. Ghiameremo grafo complementare Ḡ
di G un grafo che consiste dell’insieme dei vertici di G e i cui spigoli congiungono
coppie di vertici non adiacenti in G
Pertanto G = (V, S̄) dove ∀ x, y ∈ V, x 6= y
{x, y} ∈ S̄ ←→ {x, y} ∈
/ S.
Se G ha n vertici v1 , v2 , . . . , vn e i loro gradi sono rispettivamente d1 , d2 , . . . , dn ;
quali sono i gradi dei vertici in Ḡ?
Il grafo Ḡ è il complementare di G nel grafo completo Kn . In Kn ogni vertice
ha grado n − 1 e pertanto δ(vi ) = n − 1 − di per i = 1, 2, . . . , n.
Esercizio 38 Si dimostra che due grafi G e H sono isomorfi se e soltanto se i
loro grafi complementari Ḡ e H̄ sono isomorfi.
Soluzione La dimostrazione segue immediatamente dalla definizione di isomorfismo α dei due grafi, infatti ∀ u, v ∈ VG
{u, v} ∈
/ SG ←→ {α(u), α(v)} ∈
/ SH .
Esercizio 39 I grafi G1 e G2 sotto proposti sono isomorfi?
Figure 1: Grafo1
Figure 2: Grafo2
Soluzione Si considerino i grafi complementari Ḡ1 e Ḡ2 , i quali sono chiaramenti
isomorfi come si evince dalla loro rappresentazione grafica:
Poichè Ḡ1 w Ḡ2 segue che G1 w G2 .
Esercizio 40 Trovare tutti gli automorfismi del grafo G1 dell’esercizio precedente.
Soluzione Gli isomorfismi conservano i gradi dei vertici, i.e. δG (u) = δH (α(u))
se α : G 7→ H è un isomorfismo. L’identità è sempre un automorfismo. Sia
α : G 7→ Gun automorfismo non identico del grafo G. Poichè v4 è il solo
vertice di grado 5, allora α(v4 ) = v4 . Inoltre v5 è il solo vertice adiacente sia
a v2 che a v3 tale che δG (v2 ) = 4 = δG (v3 ). Quindi abbiamo α(v5 ) = v5 . Se
α(v2 ) = v3 → α(v3 ) = v2 , α(v0 ) = v1 , α(v1 ) = v0 .
Esercizio 41 Determinare il numero cromatico di G1 .
Esercizio 42 Trovare grafi 4-regolari non isomorfi con 7 vertici.
Soluzione Due grafi sono isomorfi se e soltanto se lo sono i loro grafi complementari. Nel nostro caso, i grafi complentari hanno 7 vertici ciascuno di grado 2 ed
essi sono i seguenti:
Esercizio 43 Si consideri il grafo G = (V, S) costituito da 9 vertici v1 , v2 , . . . , v9
e i cui spigoli sono definiti come segue:
{vi , vj } ∈ S ←→ |i − j| ≥ 2
. Dire quale delle seguenti affermazioni è corretta:
(a) G è un grafo connesso regolare;
(b) χV (G) = 8;
(c) χV (G) < 8;
(d) non ci sono in G cammini euleriani.
7
Esercitazione dell’ 11/05/2004
Esercizio 44 Quale delle seguenti liste risultano quelle di possibili gradi di tutti
i vertici di un grafo? Nel caso affermativo, si fornisca una rappresentazione
grafica del grafo.
1)
2, 2, 2, 3;
2)
1, 2, 2, 3, 4;
3)
2, 2, 4, 4, 4;
4)
1, 2, 3, 4.
Soluzione La lista 1) non è quella
P dei gradi di un grafo, infatti otteniamo una
contraddizione essendo 2|S| = v∈V δ(v) = 2 + 2 + 2 + 3 = 9.
Nel caso 2) si osservi che |S| = 6 e pertanto l’eventuale grafo dovrebbe
presentare 5 vertici e 6 spigoli. La costruzione del grafo cercato G si ottiene
a partire dal grafo completo K5 come segue. In primo luogo osserviamo che
K5 presenta 10 spigoli di cui dobbiamo eliminarne opportunamente 4 ed inoltre
pensiamo K5 avente come circuito esterno il pentagono di vertici v1 , v2 , v3 , v4 , v5 .
Poichè nel grafo cercato G esiste un solo vertice di grado 1 (sia esso v1 ), togliamo
dal grafo K5 i seguenti 3 spigoli: {v1 , v2 }, {v1 , v3 }, {v1 , v4 }. In G c’è un solo
vertice di grado 4 e questo necessariamente deve essere v5 ; non possiamo togliere
nessuno degli spigoli uscenti dal vertice v5 ma possiamo togliere esattamente uno
dei seguenti spigoli: {v2 , v4 }, {v2 , v3 }, {v3 , v4 }. In questo modo otteniamo il grafo
cercato, infatti δ(v1 ) = 1, δ(v2 ) = 2, δ(v3 ) = 2, δ(v4 ) = 3, δ(v5 ) = 4.
Nel caso 3) il grafo cercato G = (V, S) presenta 8 spigoli. Dal grafo completo
K5 , costruito come visto prima, dobbiamo eliminare in modo opprtuno 2 spigoli.
In G ci sono tre vertici, siano essi v3 , v4 , v5 , di grado uguale a quattro. Pertanto
degli spigoli di K5 possiamo eliminare soltanto lo spigolo {v1 , v2 } ottenendo in
tal modo un grafo con 5 vertici ma 9 spigoli.
Nel caso 4) il grafo G presenta 4 vertici v1 , v2 , v3 , v4 di gradi rispettivamente
1, 2, 3, 4, presenta 5 spigoli. Impossibile esibire un grafo del tipo descritto.
Esercizio 45 Si considerino i seguenti quattro grafi Gi = (Vi , Si ) con i =
1, 2, 3, 4 dove
(a) V1 è l’insieme delle parole binarie di lunghezza 3, S1 è l’insieme dei 2-insiemi
di parole di V1 che differiscono esattamente in una posizione;
(b) V2 = X ∪ Y con X = {x1 , . . . , x4 }, Y = {y1 , . . . , y4 }; mentre l’insieme
S2 = {{xi , yj }, i, j = 1, . . . , 4, i 6= j}
(c) V3 ha elementi v1 , . . . , v8 .
S3 = {{vi , vj } : i − j invertibile inZ8 }.
(d) G è un grafo connesso bipartito con 8 vertici, regolare di grado 3.
Segnare quale dei suddetti grafi non è isomorfo al cubo ordinario.
Soluzione Sappiamo che, a meno di isomorfismi, esiste un solo grafo con le proprietà di G4 ( che poi sono quelle caratterizzanti il cubo ordinario); pertanto
occorre controllare se tali proprietà risultano soddisfatte o meno dai rimanenti
grafi G1 , G2 , G3 . Osserviamo che G1 = (V1 , S1 ) è un grafo con 8 vertici e connesso, i.e. due qualsiasi vertici u, v sono congiungibili mediante un cammino in
G1 . Partizioniamo l’insieme dei vertici V1 = A ∪ B nel modo seguente:
A = {u ∈ V1 |u contiene un numero pari di1},
B = {u ∈ V1 |u contiene un numero dispari di1}.
Costruiamo la seguente applicazioneα : V −→ N2 = {a, b} definita come segue
∀v∈V
½
a
v∈A
α(v) =
b
v∈B
Si noti che ∀ {u, v} ∈ S1 −→ α(u) 6= α(v), infatti le parole u, v differiscono in
una sola posizione e pertanto se per esempio u ∈ A segue che v ∈ B e viceversa.
Se n è il numero di 1 che contiene la parola u allora sarà n+1 oppure n il numero
di 1 della parola v. Segue che il grafo G1 è bipartito. Per ogni v ∈ V1 , v è una
parola binaria di lunghezza di 3 e poichè a partire da essa modificando i bits in
una sola posizione possiamo individuare 3 parole binarie di lunghezza 3 segue
che G1 è un grafo 3-regolare.
Analogamente si procede per provare che G2 = (V2 , S2 )4 è un grafo connesso
3-regolare con 8 vertici. Risulta particolarmente efficace la rappresentazione
grafica di G2 .
In Z8 gli elementi invertibili sono 4 e sono 1, 3, 5, 7; segue che in G3 ogni
vertice ha grado 4 e quindi G3 non è isomorfo al cubo ordinario.
Generalizzando quanto detto sopra, si dimostra che:
Esercizio 46 Il k-cubo Qk è il grafo i cui vertici sono le parole binarie di
lunghezza k e i cui spigoli sono i 2-insiemi di tali parole che differiscono esattamente in una posizione. Si verifichi che:
• Qk è un grafo k-regolare;
• Qk è un grafo bipartito.
Definizione 13 Sia G = (V, S) un grafo. ”Colorare gli spigoli” del grafo G
significa stabilire una applicazione β : S −→ Nn ( detto insieme dei colori) suriettiva tale che ∀ {a, x}, {a, y} ∈ S con x 6= y risulta β({a, x}) = β({a, y}); i.e.
due qualsiasi spigoli contenenti lo stesso vertice hanno colori diversi. Denoteremo col simbolo χS (G) il minimo numero di colori che occorre per colorare gli
spigoli di G e lo chiameremo numero cromatico degli spigoli di G.
Dalla definizione segue facilmente che se G1 w G2 allora χS (G1 ) = χS (G2 );
mentre il viceversa non è in generale valido. Poichè in un grafo bipartito G,
χS (G) = max dei gradi di G segue che χS (Q3 ) = 3. Sia G1 il grafo definito come
segue
I grafi G1 e Q3 non sono isomorfi pur presentando lo stesso numero cromatico
degli spigoli.
Esercizio 47 Sia G2 = (V2 , S2 ) il grafo precedentemente definito. Si considerino le seguenti applicazioni γi : S2 −→ Z4
(a) γ1 ({xi , yj } = i;
(b) γ2 ({xi , yj } = |i − j|;
(c) γ3 ({xi , yj } = 3i + j(mod 4);
(d) γ3 ({xi , yj } = 2i + j(mod 4);
indicare quale tra le γi risulta una colorazione degli spigoli di G2 .
Esercizio 48 Dimostrare che
χS (Kn ) =
½
n
n−1
n > 1 dispari
n pari
Soluzione Sia n > 1 un intero dispari qualsiasi e consideriamo il grafo completo
Kn costruito a partire da un poligono regolare con n lati. Ogni spigolo di Kn è
parallelo ad un unico lato di tale polignono che ovviamente fa parte del grafo.
Coloriamo i lati del poligono con i colori 1, 2, . . . , n e coloriamo con il colore i lo
spigolo di Kn ( che non fa parte del circuito esterno ) con il colore i se questo
è parallelo al lato di questo colore. Questa descritta è una colorazione degli
spigoli di Kn che utilizza n colori. Adesso proviamo che non può esistere una
colorazione degli spigoli di Kn che utilizzi n − 1 colori.
Fissato un colore A, al massimo possono esserci n−1
spigoli non confluenti
2
aventi tutti il colore A ( altrimenti ci sarebbero spigoli aventi un vertice in
comune colorati con il colore A ). Si consideri la seguente rappresentazione
grafica di K5
Per esempio se coloro con A lo spigolo {v1 , v2 } di K5 , degli spigoli uscenti dal
vertice v3 non confluenti in v1 , v2 possiamo scegliere lo spigolo {v3 , v5 } e nessun
altro.
In generale con n − 1 colori si possono colorare al massimo (n−1)(n−2)
spigoli.
2
Poichè in Kn ci sono esattamente n(n−1)
spigoli
segue
che
non
è
possibile
colorare
2
tutti gli spigoli di Kn con n − 1 colori.
Consideriamo il caso n pari e coloriamo gli spigoli di Kn−1 con n − 1 colori
come suggerito precedentemente, dove con Kn−1 intendiamo il sottografo di Kn
ottenuto da esso eliminando il vertice v e tutti gli spigoli uscenti da v. Denotiamo
con vi il vertice del sottografo Kn−1 da cui si dipartono tutti gli spigoli colorati
co 1, 2, . . . , n − 1 tranne il colore i. A questo punto coloriamo con i lo spigolo
{v, vi } del grafo Kn ed otteniamo la colorazione degli spigoli richiesta. Si osservi
che n − 1 è il minimo numero di colori necessario per colorare gli spigoli di Kn ,
essendo χS (Kn ) ≥ n − 1. Illustriamo quanto detto con un esempio.
Esercizio 49 Consideriamo il grafo G = (V, S) dove V = X ∪ Y con
X = {x1 , x2 , x3 } e Y = {y1 , y2 , y3 , y4 },
S = {{xi , yj } con i = 1, 2, 3, j = 1, 2, 3, 4}.
1) In G esistono cammini o circuiti euleriani?
2) In G esistono cammini o circuiti hamiltoniani?
3) Determinare χS (G).
8
Esercitazione del 18/05/2004
Esercizio 50 Costruzione del campo F9 con nove elementi.
Poichè il polinomio x2 + 2x + 2 risulta irriducibile nell’anello Z3 [x] ( basta
osservare che esso non presenta fattori lineari), possiamo pensare il campo F 9
come Z3 [x]\(x2 + 2x + 2) i cui elementi sono le classi ∼ di equivalenza definita
come segue:∀ a(x), b(x) ∈ Z3 [x]
a(x) ∼ b(x) ↔ x2 + 2x + 2 divide a(x) − b(x).
Convenendo di denotare col simbolo [a(x)] la classe di equivalenza individuata
dal polinomio a(x), definiamo l’addizione e la moltiplicazione in modo ovvio:
[a(x)] + [b(x)] = [a(x) + b(x)],
[a(x)][b(x)] = [a(x)b(x)];
si verifica che rispetto a tali operazioni l’insieme delle classi di equivalenza acquista struttura di campo, che denotiamo col simbolo F9 . Si osservi che i polinomi di grado 0, 1 con coefficienti in Z3 [x]
F9 = {0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2}
formano un insieme completo di rappresentanti per tali classi di equivalenza e
pertanto il campo F9 contiene 9 elementi. Sappiamo che il gruppo moltiplicativo
di F9 è il gruppo ciclico C8 e che presenta Φ(8) = 4 generatori.
Pensando F9 come Z3 [x]\(x2 + 2x + 2), vogliamo controllare se il polinomio
2
x + 2x + 2 risulta primitivo in Z3 [x], i.e. se il polinomio x risulta un generatore
del gruppo moltiplicativo di F9 . A tal fine occorre calcolare tutte le potenze di
x, abbiamo
x, x2 = −2x−2 = x+1, x3 = 2x+1, x4 = 2, x5 = 2x, x6 = 2x+2, x7 = x+2, x8 = 1.
Le potenze di x ci danno tutti gli elementi non zero di F9 e il periodo di x è
uguale a 8, scriviamo C8 = hxi. Invece controlliamo che il polinomio x + 1 non
è elemento primitivo di F9 , infatti abbiamo
x + 1, (x + 1)2 = 2, (x + 1)3 = 2x + 2, (x + 1)4 = 1.
Si verifica che anche x + 2 è un generatore del gruppo moltiplicativo di F9 e
d’altra parte si osserva che
x(x + 2) = x2 + 2x = −2 = 1,
i.e. l’inverso di x è il polinomio x+2. Essendo (x+1)(2x+2) = 2x2 +2x+2x+2 =
2(x + 1) + 4x + 2 = 6x + 4 = 1 segue che l’inverso di x + 1 è il polinomio 2x + 2 e
pertanto 2x + 2 non può essere un generatore per il gruppo moltiplicativo di F 9
e che 2x e 2x + 1 ( inversi l’uno dell’altro) risultano i candidati per i rimanenti
generatori del gruppo moltiplicativo di F9 . Si lascia allo studente la verifica di
quanto testè affermato.
Il fatto che il polinomio x2 + 2x + 2 sia un polinomio primitivo ha il vantaggio
di semplificare la nostra costruzione di F9 . Per esempio la tavola delle potenze
di x può semplificare la moltiplicazione di due elementi di F9 .
Domanda: Quali elementi di F9 = Z3 [x]\(x2 + 2x + 2) hanno radici quadrate
nel campo?
Poichè il polinomio x è un elemento primitivo di campo, gli elementi non
zero del campo si scrivono nella forma
x, x2 , . . . , x8 = 1.
Ovviamente le potenze pari di x hanno radici nel campo essendo x2m = (xm )2 ;
mentre per le potenze dispari di x abbiamo x2m+1 = β 2 = (xk )2 = x2k →
x2(m−k)+1 = 1; segue che l’intero dispari 2(m − k) + 1 deve essere un multiplo
di 8 e quindi troviamo un risultato contraddittorio. Concludiamo che i quadrati
non zero di F9 sono 2 = {x2 , x4 , x6 , x8 = 1} e sono in numero di quattro.
Esercizio 51 Risolvere in F9 = Z3 [x]\(x2 + 2x + 2) la seguente equazione
y 2 + 2y + 2 = 0
Soluzione Calcoliamo il discriminante ∆
4 = 1−2 = −1 e ricordiamo che, essendo
9 ≡ 1(mod 4), −1 ha radice in F9 . Se pensiamo F9 costruito come il campo
Z3 [x]\(x2 + 2x + 2), ci proponiamo di determinare le soluzioni dell’equazione
proposta. Dalla tavola delle potenze di x ricaviamo che x4 = 2 = −1 e quindi le
soluzioni sono −1 ± x2 , i.e. i polinomi x e 2x + 1.
Esercizio 52 In Z3 [x]\(x2 + 2), il polinomio x risulta invertibile?
Soluzione Prima di rispondere a questa domanda, osserviamo che l’anello descritto sopra non risulta un campo, infatti il polinomio x2 + 2 non è irriducibile
in Z3 [x]. Ciò significa che non tutti gli elementi non zero presentano inverso,
che non possiamo a priori stabilire se il polinomio x risulta o non invertibile ma
che occorre verificarlo. A tal fine osserviamo che x2 = −2 = 1 e pertanto il
polinomio x coincide col suo inverso.
Esercizio 53 Qual è il numero degli elementi primitivi nel campo F 32 ? Dedurre
dalla risposta che il polinomio x5 + x2 + 1 risulta primitivo irriducibile in Z2 [x].
Soluzione Il numero degli elementi primitivi di F32 è Φ(31) = 30 e quindi tutti,
tranne 0 e 1, sono generatori del gruppo moltiplicativo di F31 . Controlliamo che
il polinomio x5 + x2 + 1 risulta irriducibile in Z2 [x]. In primo luogo osserviamo
che non può presentare fattori lineari essendo
05 + 02 + 1 = 1,
15 + 12 + 1 = 1.
In secondo luogo, non presenta fattori quadratici poichè l’unico polinomio irriducile in Z2 [x] è x2 + x + 1 e x5 + x2 + 1 = (x2 + x + 1)(x3 + x2 ) + 1.
Possiamo concludere che il polinomio x5 + x2 + 1 risulta irridubile in Z2 [x] e
che F32 ' Z2 [x]\(x2 + x + 1). Il polinomio x, per quanto sopra detto, risulta
un generatore del gruppo moltiplicativo di F32 e quindi il polinomio x5 + x2 + 1
risulta primitivo irriducibile in Z2 [x].
9
Esercitazione del 25/05/2004
Esercizio 54 Siano dati i seguenti codici:
1. C1 = {0000, 1100, 1010, 1001, 0110, 0101, 0011, 1111} in V 4 ;
2. C2 = {10000, 01010, 00001} in V 5 .
Si chiede di:
(a) trovare la distanza minima δ per ciascuno dei suddetti codici;
(b) determinare di ciascun codice il numero di errori che può essere individuato
e corretto;
(c) quale dei dati codici può essere esteso con l’inclusione di una ulteriore parola
senza modificare δ.
Soluzione Ricordiamo che δ = min{∂(a, b)|a, b ∈ C, a 6= b}, dove la distanza
∂(a, b) conta il numero di bits in cui le parole a, b differiscono. Le parole di
C1 , tranne 0000, 1111, sono tutte quelle che contengono due bits uguali a 1 e
pertanto δ = 2. Ricordando che un codice con distanza minima δ individua al
più δ − 1 errori, segue che C1 individua al più un errore.
Dalla diseguaglianza 2 ≥ 2e + 1 segue che e ≤ 21 e quindi e = 0, i.e. il
codice C1 non corregge errori. Tale codice non può essere esteso aggiungendo ad
esso una ulteriore parola binaria senza modificare δ; infatti potremmo aggiungere
soltanto una parola binaria con 3 bits uguali a 1 e in tal caso la sua distanza dalla
parola 1111 risulterebbe uguale a 1, modificando δ = 1. Infine osserviamo che
quello presentato risulta un codice lineare essendo C1 un sottogruppo del gruppo
addittivo V 4 ; tenendo conto di tale osservazione avremmo potuto calcolare la
distanza minima δ come il minimo peso di C 4 , ovvero il minimo numero di bits
1 contenuto dalle parole del codice.
Calcoliamo le distanze
∂(10000, 01010) = 3, ∂(10000, 00001) = 2, ∂(01010, 00001) = 2.
le quali ci assicurano che δ = 2 e quindi il codice C2 individua al più un
errore e non corregge errori. Aggiungiamo a C2 la parola 10101 e calcoliamo le
distanze
∂(10000, 10101) = 2, ∂(01010, 10101) = 5, ∂(00001, 10101) = 2.
Questo codice (non lineare ) chiarisce il fatto che il peso minimo coincide con la
distanza minima se e soltanto se il codice è lineare, infatti il peso minimo di C 2
è uguale a 1 6= 2 = δ.
Definizione 14 Un codice C si dice ciclico se esso risulta lineare e se
a0 a1 a2 . . . an−1 ∈ C → an−1 a0 a1 . . . an−2 ∈ C.
Esercizio 55 Siano dati i seguenti codici
(i){000, 100, 010}, (ii){000, 100, 010, 001},
(iii){0000, 1100, 0110, 0011}, (iv){0000, 1010, 0101, 1111}.
Quali dei precedenti codici risulta ciclico?
Soluzione Il codice (i) non è ciclico perchè per esempio non contiene la parola
001. Il codice (ii) non è ciclico perchè non è lineare, infatti non contiene la parola
011 = 010 + 001.
Il codice (iii) non è ciclico perchè non lineare, infatti esso non contiene la
parola 1111 = 1100 + 0011.
Infine osserviamo che il codice (iv) è ciclico infatti abbiamo
1010 → 0101 → 1010.
Infine occorre controllare che esso risulta anche lineare:
1010 + 0101 = 1111
1010 + 1111 = 0101
0101 + 1111 = 1010
Esercizio 56 Scrivere tutte le parole codice
ciato alla seguente matrice di controllo

1 1 0 1 0
 0 0 0 1 1

 1 0 1 1 0
0 0 0 0 0
Individuare i parametri n, k, δ di tale codice.
appartenenti al codice lineare asso
0 1
0 1 
.
0 1 
1 1
Soluzione n = 7, ovvero il numero delle colonne della matrice di controllo. Il
codice contiene tutte e sole le parole binarie x1 x2 x3 x4 x5 x6 x7 soddisfacenti il
sistema di equazioni:


x1

  x2 


1 1 0 1 0 0 1


 0 0 0 1 1 0 1   x3 

  x4  = 04×1 .

 1 0 1 1 0 0 1 
 x5 


0 0 0 0 0 1 1
 x6 
x7
Esplicitiamo le equazioni del suddetto sistema

x1 + x 2 + x 4 + x 7 = 0



x4 + x 5 + x 7 = 0
x
+ x3 + x4 + x7 = 0

1


x6 + x 7 = 0
Le soluzioni sono le parole del tipo (x3 + x5 , x3 , x3 , x5 + x7 , x5 , x7 , x7 ) al variare
di x3 , x5 , x7 ∈ {0, 1} e pertanto il codice presenta dimensione k = 3. Nel codice
ci sono 2k = 23 = 8 parole binarie. Tenendo conto della struttura della generica
parola-codice segue facilmente che il peso minimo del codice è uguale a 2 e che
pertanto δ = 2. Dalla diseguaglianza δ ≥ 2e + 1 segue che e = 0 e quindi il codice
non corregge errori.
Esercizio 57 Sia C il codice lineare definito dalla seguente matrice di controllo


1 1 0 1 0 1
 1 1 1 0 1 0 .
1 0 1 1 0 0
Se la parola ricevuta è 110110 e un solo errore è stato commesso nella trasmissione dei dati, qual è la parola codice inviata?
Soluzione Calcoliamo

1
 1
1
1
1
0
0
1
1
1
0
1
0
1
0



1



0


0

1
1
0
1
1
0

 
  

1+1+1
1

 =  1 + 1 + 1  =  1 .


1+1
0

Otteniamo la seconda colonna della matrice di controllo, pertanto è stato
commesso un errore nella trasmissione della parola, in realtà la parola inviata è
100110.
Esercizio 58 Sia C un codice lineare con distanza minima δ, sappiamo che
esso individua al più δ − 1 errori ma che può correggere e errori con δ ≥ 2e + 1.
Cerchiamo di chiarire le espressioni C corregge al più e errori e individua al
più δ − 1 con il seguente esempio. Si consideri il codice lineare descritto dalla
seguente matrice di controllo


1 1 0 1 0 1
 1 1 1 0 1 0 
1 0 1 1 0 1
e supponiamo che la parola arrivata dopo la trasmissione dei dati sia 011000.
Osserviamo che
 
0

 1   
 
1 1 0 1 0 1
1
 
 1 1 1 0 1 0  1  =  0 .
 0 
 
1 0 1 1 0 1
1
 0 
0
Se supponiamo che nella trasmissione dei dati sia stato commesso un solo errore,
non siamo in grado di stabilire se tale errore è stato commesso nel quarto bit
oppure nel sesto bit della parola arrivata. Il codice non è in grado di correggere l’errore. Calcoliamo le parole del codice risolvendo il seguente sistema di
equazioni:


x1
  x2 



1 1 0 1 0 1


 1 1 1 0 1 0   x3  = 03×1 ,
 x4 


1 0 1 1 0 1
 x5 
x6
esplicitiamo le equazioni del sistema

 x1 + x 2 + x 4 + x 6 = 0
x1 + x 2 + x 3 + x 5 = 0

x1 + x 3 + x 4 + x 6 = 0
Le soluzioni sono le parole binarie del tipo (x5 , x3 , x3 , x4 , x5 , x5 + x3 + x4 ), con
x3 , x4 , x5 ∈ {0, 1}, e pertanto il codice ha dimensione k = 3. Si osservi che la
distanza minima δ = 2 infatti il peso minimo delle parole del codice è 2, come
si evince dalla loro ”struttura”. Questo significa che il codice individua al più
un errore ma non risulta sempre in grado di corregerlo, sarà in grado di farlo se
l’errore è stato commesso nel primo, nel secondo, nel terzo o nel quinto bit della
parola inviata.