Matematica Discreta - Algebra

R

[a] = { x appartnente X | (a,x) appartenente a R} = R(a)

R

Osservazioni:

Se R è una relazione di equivalenza su X ogni elemento di x appartenente a X è in relazione

– R con qualche elemento, almeno con se stesso, e quindi appartiene ad almeno una classe di

equivalenza

Ogni elemento può appartenere ad una sola classe di equivalenza .

– Le classi di equivalenza realizzano una partizione di X

–

Partizione: Sia X un insieme e sia Ai una famiglia di sottoinsiemi , anche non finita, di X.

Dico che Ai è una partizione di X se:

Ai diverso da vuoto, per ogni i appartenent a I (sottoinsieme)

– Ai interesezione con Aj = insieme vuoto se i diverso da j

– Unione di tutte Ai = X

–

Sia {Ai} una partizione di X. La relazione R su X definita da

(x,y) appartenente a R <=> esiste Ai che contiene x e y

e' una relazione di equivalenza su X, le cui classi di equivalenza sono proprio gli Ai.

Partizioni e relazioni di equivalenza "stessa cosa":

Ogni relazione di equivalenza su X determina una partizione di X

– Ogni partizione di X determina una relazione di equivalenza su X

–

Insieme quoziente di X rispetto a R: E' l'insieme che ha come classi di equivalenza di X rispetto a R

e indicato con X / R. (R una relazione di equivalenza su X)

Lezione 11: Congruenze in Z

Def: Siano a, b appartenenti a Z e n appartenente a Z , con n > 1. Si dice che a è congruo a b

modulo n a ≡ b (mod n)

se a-b è divisibile per n, cioè esiste una k appartenente in Z tale che

a-b = kn

La congruenza è una relazione di equivalenza in Z

Nota => operazione di congruenza è verificata controllanto se a e b hanno lo stesso resto utilizzando

come divisore n

Esempio: 38 ≡14 (mod 12) => 38 / 12 r =2 14 / 12 r=2 OK

Relazioni di congruenza compatibili con operazioni somma e prodotto.

Lezione 12: Congruenze lineari

Def: Siano a, b appartenenti a Z, e n appartenente N con n > 1. L'equazione in x del tipo

ax ≡ b (mod n)

è detta congruenza lineare, e ogni intero x0 tale che

ax0 ≡ b (mod n)

è detta soluzione della congruenza lineare

Problemi da risolvere:

Risolubilità congruenze lineari =>Entrambe risolubili grazie alle equazioni diofantee

– Determinare le soluzioni possibili

–

ax ≡ b (mod n) <=> ax = b + hn , ovvero ax – nh = b con h appartenente a Z

Esempio:

9x ≡ 6 (mod 12) ha soluzioni in quanto => MCD (9,12) = 3 che divide 6

(n = 12 , n' = 12/3 = 4)

Dobbiamo risolvere:

9x – 12h = 6 ossia 3x – 4h = 2

soluzioni ( x0, h0 ) = 2,1

Tutte altre soluzioni del tipo: xk = 2 + 4k

Osservazioni:

Se MCD (a.n) = 1 ha soluzione congruenza lineare ax ≡ 1 (mod n) e c'è solo una soluzione

– x0 con 0 < x0 < n

Se MCD (a.n) = 1 ha soluzione congruenza lineare ab ≡ ac (mod n) <=> b ≡ c (mod n)

–

Il teorema cinese dei resti:

Dovremo capire se ha o meno soluzioni, quante sono e come sono fatte.

Tutti gli n ( n1, n2, ... nj) sono coprimi tra loro, cioè:

MCD (ni, nj) = 1 con i diverso da j

Condizione sufficiente, se è verificata, allora:

Il sistema ammette soluzioni

– Se c è una soluzione ogni altra soluzion c' è definita con c' ≡ c mod( n1 n2 ... nj)

–

Risoluzione procedura:

Utilizziamo un esempio

Dobbiamo calcolare la soluzione del seguente sistema

1) Controlliamo gli MCD dei moduli => (5,4) , (5,7) , (4,7) = 1 OK, esistono soluzioni

2) Troviamo parti utilizi alla soluzione:

b1 = 2 , b2 = 0 , b3= 4

n1= 5 , n2 = 4 , n3 = 7

N totale = n1 * n2 * n3 = 140

N1 = n2 * n3 = 28 N2 = n1 * n3 = 35 N3 = n1 * n2 = 20

3) Determiniamo le soluzioni particolari

N1y ≡ 1 (mod n1) ossia 28y ≡ ( mod 5 ) => y1 = 2

N2y ≡ 1 (mod n2) ossia 35y ≡ ( mod 4 ) => y2 = 3

N3y ≡ 1 ( mod n3) ossia 20y = ( mod 7 ) => y3 = 6

4) La soluzione particolare del sistema x0 è data da

x0 = b1N1y1 + b2N2y2 + b3N3y3 = 112 + 480 = 512

512 mod ( N totale ) => 512 (mod 140) = 32

5) Soluzione risultante data da:

x = 32 + 140k

Lezione 13: Grafi

Siano: V: Un insieme di elementi chiamati Vertici o Nodi

– E: Una collezione di sottoinsiemi di V di ordine 2 o 1 che chiameremo Lati o Spigoli

–

La coppia ordinata (V,E) = G è detta Grafo.

Un lato di ordine 1 sarà detto loop o cappio e si rappresenta => {v1} oppure {v1, v1}

E' lecito avere lati ripeturi chiamati multipli o paralleli.

Rappresentazione Grafica:

Terminologia:

|V| => Ordine del grafo

– |E| => Grandezza del grafo: può essere 0 se non ci sono lati

– Se {vi, vj} appartengono a E => I due vertici sono adiacenti

– Se due lati {vi, vj} , { vj, vk} appartengono a E => Sono incidenti in vj

– Grado (o valenza) d(v) => Numero di lati incidenti di v

– Vertice di grado 0 => Isolato

– Vertice di grado 1 => Terminale

– Se d(v) => E' pari si dice che è un vertice pari

– Se d(v) => E' dispari si diche che è un vertice dispari

– Grafo regolare di grado r => Se ogni suo vertice ha grado r

– Grafo nullo su n vertici => E' un grafo con E = 0 e |V| = n, ossia non ha lati

– Grafo semplice => Grafo senza loop e lati multipli

– Grafo completo di ordine n => Grafo semplice che ha ogni coppia di vertice di V adiacente

– Ogni grafo regolare di grado r e ordine n ha => 1/2 r*n lati

– Un grafo orientato => E' una coppia ordinata (V,E) ove V è un insieme (non vuoto) di vertici

– ed E è una collezione di coppie ordinate di elementi di V, dette archi

Terorema:

Sia (V,E) un grafo e sia d(v) il grado del vertice v appartenente a V. Si ha:

| E | = 1/2 ∑ d(v)

Colorrario => Ogni grafo ha un numero pari di vertici dispari

Il grafo (V,E) puo essere rappresentato tramite matrici di adiacenza , cioè una matrice A quadrata di

ordine n tale che

aij è il numero (intero >= 0) dei lati ce congiungono vi e vj

Osservazioni:

La matrice A cambia se l'ordine dei vertici viene permutato

– La matrice A di adiacenza di un grafo è simmetrica

–

La matrice di adiacenza di un grafo evidenza:

1) Numero di vertici => Ordine della matrice

2) Vertici isolati => Producono una riga e colonna di zeri

3) Cappi => Presenza di numeri diversi da zero sulla diagonale

4) Il grado di ogni vertice vi => Somma degli elementi della riga ( o colonna) i, contanto due

volte aii

5) Regolarità del grafo => Le somme de punto 4 sono tutte uguai al variare di i

6) Numero di lati => 1/2 della somma al variare di i delle somme del punto 4

7) Semplicità del grafo => Per ogni i , aij e i diverso da j : aij uguale a 0 o 1

Lezione 14: Cammini sui Grafi

Analizziamo u e v come vertici di un grafo (V,E)

Definizioni:

1) percorso => Si dice percorso da u a v una sequenza di lati l1, l2 ... lh (non necessariamente

distinti) ognuno adiacente al successivo.

Il numero di lati che compongono il percorso è detta lunghezza del percorso

2) cammino => E' un percorso da u a v privo di lati ripetuti ( i vertici possono comparire piu di

una volta). Un cammino in cui anche i vertici non sono ripetuti (escluso iniziale e finale) è

detto cammino semplice (o catena). Un cammino senza lati da v a v è detto cammino nullo.

Un cammino chiuso contenente almeno un lato è detto circuito o ciclo.

Teorema: h

Sia A la matrice di adiacenza di un grafo. L'elemento di posto (i,j) di A dà il numero di percorsi da

vi a vj di lunghezza h.

Grafi Connessi:

Un grafo (V,E) è detto connesso se per ogni u, v appartenenti a V esiste un cammino che parta da u

e arriva a v.

Teorema:

Sia (V,E) un grafo. La relazione R su V definita da

(u,v) appartenente a R <=> Esiste un cammino sul grafo che parte da u e arriva a v

è una relazione di equivalenza

La relazione R determina una partizione dei vertici del grafo.

Gli elementi dell insieme quoziente V/R sono dette componenti connesse di V.

I vertici che stanno nella stessa classe di equivalenza costituiscono un grafo connesso.

Come sapere se un grafo connesso conoscendo la matrice di adiacenza?

Sia A la matrice di adiacenza di un grafo (V,E) con |V| = n. 2 n-1

Allora (V,E) è connesso <=> ogni elemento della matrice c = I+A+A + ... + A è diverso da zero.

Grafo Euleriano => Un grafo (V,E) è detto euleriano se esiste un circuito che contiene ogni lato del

grafo.

Teoreama di Eulero => Un grafo privo di vertici isolati è euleriano se e solo se è connesso e ogni

suo vertice ha grado pari.

Il grafo completo kn è euleriano se e solo se n è dispari.

Lezione 15: Alberi

Albero => Si definisce albero un grafo connesso privo di circuiti.

Foresta => Unione disgiunta di alberi

Lemma: Un albero con almeno due vertici ha almeno un vertice di grado 1.

Albero con radice :

Dato un alberto (V,E) si puo scegliere un suo vertie come radice e quindi assegnare un verso a ogni

lato, a partire dalla radice.

Un vertice dotato di almeno un figlio è detto => Vertice interno

Un vertice privo di figli è detto => Foglia

Albero n-ario => Un albero con radice in cui ogni vertice ha al piu n figli

Albero pienamente n-ario => Albero con ogni vertice interno con esattamente lo stesso numero di

figli. Se n = 2 => Albero binario

Se scegliamo un vertice v come radice si può definire il livello del vertice u come lunghezza del

cammino da v a u.

Alberi Sintattici:

Con un abero ordinat si possono rappresentare ad esempio le espressioni algebriche tenendo

presente che :

1) Gli operatori unari (potenza, radici)sono nodi con 1 figlio a sinistra e nessuno a destra

2) operatori binari (+, *...) hanno figlio a sinistra e destra

3) lettere e numeri su cui si operano sono foglie

4) leggendo il grafo si deve ritrovare la formula

RIASSUNTO GRAFI

Lezione 16: Strutture algebriche

Introduciamo concetto di:

Operazione Binaria tra due insiemi X e Y a valori in un insieme Z

Indico qualunque applicazione del tipo g : X x Y => Z

e per ogni coppia ordinata (x,y) appartenente a X x Y l'elemento z = g (x,y) è detto risultato

dell'operazione sulla coppia x,y.

Poiche g è un applicazione il risultato esiste ed è unico per ogni coppia di ordinate (x,y)

Per comodità si usa denotare l'operazione con un simbolo => * g(x,y) = x * y

Se i 3 insiemi coincidono X = Y = Z si parla di operazione binaria interna (o legge di composizione)

e si dice che x è chiuso rispetto all'operazione * => Altrimenti si parla di operazione binaria aper