Matematica Discreta
Lezione del giorno 15 gennaio 2009
Fissato un intero m (detto modulo) abbiamo definito una relazione di equivalenza nell’insieme Z dei numeri interi relativi, detta congruenza aritmetica modulo m: in tale relazione un intero relativo a è associato ad un intero relativo b se m è divisore della differenza a-b (quindi se esiste un intero relativo k tale che a-b=mk) e in tale caso si dice che a è congruo b modulo m e si scrive a≡b (mod m)
In base ad alcune considerazioni già esposte, ci limitiamo a studiare i casi in cui il modulo m è >1.
Ci proponiamo ora di studiare le classi di equivalenza della congruenza modulo m, dette classi di congruenza modulo m. Se scegliamo ad arbitrio un rappresentante aZ, dalla teoria delle classi di equivalenza sappiamo che la classe di congruenza [a] rappresentata da a è definita come segue:
[a] = { xZ / x≡a (mod m) } = { xZ / m è divisore di x-a } = { xZ / x-a=mk con kZ }=
= { xZ / x=a+mk con kZ }.
Dunque gli elementi di [a] sono della forma x=a+mk con k che varia in Z: al variare del parametro k, si ottengono tutti gli elementi della classe [a] (che sono dunque infiniti numeri interi relativi).
Possiamo calcolare qualche elemento di [a] facendo assumere al coefficiente k alcuni particolari valori interi relativi (k=0,1,-1,2,-2,…..): [a] = {a , a+m , a-m , a+2m , a-2m ,….}
Esempio: nella congruenza modulo m=9, la classe [5] rappresentata da a=5 contiene i numeri della forma x=5+9k, con k che varia in Z: [5] = { 5, 14, -4, 23, -13, ….}.
Abbiamo visto che ogni classe di congruenza modulo m contiene infiniti numeri interi relativi, e conosciamo la struttura che hanno i numeri di ogni classe. Ma quante sono in tutto le distinte classi di congruenza modulo m ?
Esempio. Studiamo le classi di congruenza modulo m=3.
Costruiamo una di tali classi, fissando per esempio il rappresentante a=5:
[5] = { xZ / x≡5 (mod 3) } = { xZ / x=5+3k con kZ } = {5, 8, 2, 11, -1, …}
Se vogliamo costruire una classe di congruenza diversa da [5], dobbiamo scegliere un rappresentante che non sia congruo 5 modulo 3 (perché sappiamo da un Teorema precedente che se aRb allora [a]=[b]). Possiamo per esempio scegliere a=7 (la differenza 7-5=2 non è multiplo di m=3):
[7] = { xZ / x≡7 (mod 3) } = { xZ / x=7+3k con kZ } = {7, 10, 4, 13, 1, …}
Se vogliamo costruire una classe di equivalenza diversa dalle 2 classi già costruite, dobbiamo scegliere un rappresentante a che non sia congruo 5 modulo 3 e che non sia congruo 7 modulo 3.
Possiamo per esempio scegliere a=3 (le differenze 5-3=2, 7-3=4 non sono multipli di m=3):
[3] = { xZ / x≡3 (mod 3) } = { xZ / x=3+3k con kZ } = {3, 6, 0, 9, -3, …}
A questo punto non riusciamo a costruire una classe di equivalenza diversa dalle 3 già costruite, perché non riusciamo, per quanti tentativi facciamo, a trovare un rappresentante a che non sia congruo 5 modulo 3, che non sia congruo 7 modulo 3, e che non sia congruo 3 modulo 3.
Da questo ragionamento un po’ empirico, possiamo concludere che le classi di congruenza distinte modulo 3 sono:
[5], [7], [3]
ossia le classi sono in numero di 3, cioè in numero uguale al modulo.
Il prossimo teorema dimostrerà che ciò non è casuale:
Teorema. Fissato il modulo m>1, le seguenti classi di congruenza modulo m:
[0], [1], ………., [m-1] (*)
sono tutte distinte ed esauriscono tutte le classi di congruenza modulo m. In particolare vi sono esattamente m distinte classi di congruenza modulo m.
Dimostrazione:
La tesi richiede la dimostrazione di 2 affermazioni:
a) le classi (*) sono tutte le classi di congruenza modulo m.
b) le classi (*) sono distinte
Dimostriamo la a): comunque preso un rappresentante aZ la tesi è che [a] coincide con una delle classi (*). Se a è uno dei numeri 0,1,….,m-1, non c’è niente da dimostrare. Sia dunque a diverso da 0,1,….,m-1.
Distinguiamo 2 casi:
I° caso: a>0. In questo caso dividiamo a per m: esistono interi q,r≥0 tali che a=mq+r, con r<m. Si ha a-r=mq, quindi a≡r (mod m) e da ciò si ricava [a]=[r]. Ma i valori possibili del resto r sono i numeri 0,1,…,m-1, dunque [a] coincide con una delle classi (*).
II° caso: a<0. In questo caso –a>0 e dividiamo (-a) per m: esistono interi q,r≥0 tali che (-a)=mq+r, con r<m. Distinguiamo 2 sottocasi:
I° sottocaso: r=0. In questo sottocaso si ha (-a)=mq quindi a-0=a=m(-q) cioè a≡0 (mod m), da cui [a]=[0], e dunque [a] coincide con una delle classi (*).
II° sottocaso: r>0. In questo sottocaso a-(m-r)=a-m+r=a-m-a-mq=m(-1-q) quindi a≡(m-r) (mod m) e da ciò si ricava [a]=[m-r]. Ma i valori possibili di r sono i numeri 1,2,….,m-1 (perché r>0), dunque i valori possibili di m-r sono i numeri m-1,m-2,…..,1 e si conclude che [a] coincide con una delle classi (*).
Dimostriamo la b): la tesi è che le classi (*) sono distinte. Se per assurdo 2 di tali classi coincidessero, si avrebbe [x] = [y], con 0≤x,y≤m-1, e con xy (per esempio sia x>y: nel caso opposto x<y si ragiona in modo analogo). Da [x]=[y] seguirebbe x≡y(mod m), ossia x-y sarebbe un multiplo di m, cioè x-y=kt con k intero; ma x-y>0 (perché x>y) ed inoltre x-y<m (perché x<m) e ciò implicherebbe k>0 e k<1, contraddizione perché k è intero.
Esempio: consideriamo il modulo m=6. Per il Teorema precedente vi sono 6 distinte classi di congruenza modulo 6 ed esse sono [0], [1], [2], [3], [4], [5]. Se prendiamo una qualunque classe di congruenza modulo 5, essa coinciderà con una di queste 5 classi.
Per esempio:
[22]=[?] : siamo nel I° caso (a>0) quindi si divide 22 per 6 e si prende il resto r=4, ottenendo [22]=[4]
[-30]=[?] : siamo nel II° caso (a<0) quindi si divide 30 per 6 e poiché il resto è 0 siamo nel I°
sottocaso, ossia si ha [-30]=[0]
[-31]=[?] : siamo nel II° caso (a<0) quindi si divide 31 per 6 e poiché il resto è 1 siamo nel II°
sottocaso, ossia [-31]=[m-r]=[6-1]=[5].
Nell’esempio precedente in cui abbiamo studiato empiricamente le classi di congruenza modulo 3, trovando le 3 classi:
[5], [7], [3]
possiamo notare che [5]=[2], [7]=[1], [3]=[0]
dunque le 3 classi di congruenza distinte modulo 3 sono:
[0], [1], [2]
coerentemente con l’ultimo teorema dimostrato.
Teoria dei grafi
L’origine storica della teoria dei grafi si fa risalire al problema dei 7 ponti di Könisberg (Eulero, 1736). Il problema posto era relativo al fiume Pregel attraversato da 7 ponti che collegavano 4 zone di terra (2 sponde e 2 isole):
Sponda a
1 2 6
Fiume Isola 5 Pregel
3 4 7 Sponda c
Ponti: 1,2,3,4,5,6,7 Zone di terra: a,b,c,d
Gli abitanti della città di Könisberg si chiedevano se fosse possibile partire da una delle 4 zone di terra, percorrere tutti i 7 ponti una ed una sola volta e tornare al punto di partenza.
Schematizzando il problema, si possono rappresentare le zone di terra a,b,c,d come punti nel piano ed i ponti come “archi” di curva che li uniscono:
a 6 1 2
b
5 d
3 4
C 7
Questo è già un primo modello di quello che chiameremo grafo, ma tale rappresentazione visiva (con punti e archi che li uniscono) non è univoca, in quanto dipende dalla scelta delle posizioni dei punti e dal modo di tracciare gli archi di curva che li uniscono.
Una definizione più astratta di grafo, ma più precisa ed univoca, è la seguente:
Isola b
Isola d
un grafo è una struttura costituita da 2 insiemi A, V (l’insieme A è detto insieme degli archi o lati del grafo, l’insieme V è detto insieme dei vertici o nodi del grafo), e da una funzione f: A → V2
(dove V2 indica l’insieme di tutti i sottoinsiemi di V che hanno cardinalità 2) detta funzione di adiacenza. Dunque la funzione f associa ad ogni arco aA un insieme f(a)={v,w} di 2 vertici: in questo caso si dice che i vertici v,w sono gli estremi dell’arco a.
Da notare che, in questa definizione così astratta, si prescinde dalla reale natura dei “vertici” e degli
“archi” perché gli insiemi A, V sono insiemi assolutamente generici.
Una rappresentazione grafica di un grafo si ottiene appunto rappresentando ogni vertice con un punto del piano e ogni arco con un arco di curva che unisce i due vertici estremi dell’arco.
Nell’esempio del grafo dei ponti, l’insieme dei vertici è V={a,b,c,d}, l’insieme degli archi è A={1,2,3,4,5,6,7}, e la funzione di adiacenza f: A V2 è definita ponendo:
f(1)={a,b}, f(2)={a,b}, f(3)={b,c}, f(4)={b,c}, f(5)={b,d}, f(6)={a,d}, f(7)={c,d}.
