Matematica Discreta Lezione del giorno 14 dicembre 2009 Numero delle funzioni surgettive fra insiemi finiti

(1)

Matematica Discreta

Lezione del giorno 14 dicembre 2009

Numero delle funzioni surgettive fra insiemi finiti

Siano A,B insiemi finiti con A=n, B=m, e contiamo il numero delle possibili funzioni surgettive f : A  B.

Sappiamo che se n<m tale numero è 0. Supponiamo dunque nm .

Data una funzione surgettiva f : A  B, da essa si può ricavare una partizione di A in m sottoinsiemi, ponendo in ciascuno degli m sottoinsiemi quegli elementi di A che hanno lo stesso corrispondente in B.

Per esempio se n=6, m=3, A={1,2,3,4,5,6}, B={1,2,3} e se f : A  B è definita ponendo:

f(1)=1, f(2)=1, f(3)=2, f(4)=3, f(5)=3, f(6)=3

si ricava una partizione di A in 3 sottoinsiemi {{1,2}, {3}, {4,5,6,7}}; schematizzando:

{1,2}1, {3}2, {4,5,6}3.

Ma se fissiamo una partizione di A in m sottoinsiemi, e costruiamo la corrispondente funzione surgettiva f : A  B (associando agli elementi di uno stesso sottoinsieme di A lo stesso elemento di B) non otteniamo una sola possibile funzione surgettiva, ma diverse funzioni surgettive.

Per esempio, se A,B sono come sopra, la partizione precedente {{1,2}, {3}, {4,5,6}} non determina solo la funzione f definita nell’esempio, ma anche la funzione g: A  B definita ponendo:

g(1)=2, g(2)=2, g(3)=3, g(4)=1, g(5)=1, g(6)=1 con schema:

{1,2}2, {3}3, {4,5,6}1.

Oltre f,g è evidente che possiamo costruire altre funzioni surgettive, in cui si cambia “l’ordine” in cui sono disposti gli elementi di B per definire le immagini degli elementi di A.

In generale quindi, per ottenere una funzione surgettiva f : A  B si deve fissare una partizione di A in m sottoinsiemi (tale scelta si può effettuare in S(n,m) modi diversi) e, fissata tale partizione, scegliere una permutazione degli elementi di B per definire le immagini degli elementi di A (con la regola che elementi dello stesso sottoinsieme della partizione hanno la stessa immagine in B).

Poiché questa seconda scelta (fissata la prima scelta) si può effettuare in m! modi diversi, per il principio delle scelte multiple il numero delle funzioni surgettive da un insieme di cardinalità n in un insieme di cardinalità m (con nm) è il prodotto m!S(n,m).

Esempio: il numero delle funzioni surgettive da un insieme di cardinalità 4 in un insieme di cardinalità 3 è il prodotto 3!S(4,3)=66=36 (su un totale di 3

⁴

=81 funzioni da un insieme di cardinalità 4 in un insieme di cardinalità 3).

Teoria dei grafi

L’origine storica della teoria dei grafi si fa risalire al problema dei 7 ponti di Könisberg (Eulero,

1736). La città di Könisberg era attraversata dal fiume Pregel, nel quale vi erano 2 piccole isole; le 4

zone di terraferma (le 2 sponde del fiume e le 2 isole nel fiume) erano collegate da 7 ponti, secondo

il seguente schema:

(2)

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:

Problema: è possibile partire da una delle 4 zone di terra, percorrere tutti i 7 ponti ognuno una ed una sola volta e tornare al punto di partenza ?

Schematizzando la situazione, 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 uniscono coppie di punti) 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:

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 → V

2

(dove V

2

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 aA 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 astratti.

A priori in un grafo sia l’insieme V dei vertici che l’insieme A degli archi possono essere insiemi infiniti, ma da ora in poi tutti i grafi considerati avranno sempre un numero finito di archi e di vertici.

Isola b

Isola d

(3)

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  V

2

è 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}.

Se in un grafo l’arco a ha come estremi i vertici v,w, scriveremo anche a=

vw

. Ovviamente, essendo l’arco a associato all’insieme {v,w} dei suoi estremi, l’ordine in cui sono elencati gli stessi estremi non ha alcuna importanza, quindi a=

^vw

ma anche a=

^wv

.

Osservazione: nella nostra definizione di grafo, un arco ha sempre due vertici estremi distinti, quindi non sono ammessi i cappi, cioè non sono ammessi archi che uniscono un vertice con sé stesso.

Dati due vertici distinti v,w in un grafo, diremo che v,w sono adiacenti se esiste almeno un arco che ha v,w come estremi.

Nell’esempio del grafo dei ponti, i vertici a,b sono adiacenti, ma i vertici a,c non sono adiacenti.

Poiché nel problema dei ponti si parlava di percorrere i ponti, tale concetto si formalizza nella definizione di cammino.

Un cammino in un grafo è una successione finita di archi del grafo della forma:

a

1

= v

₁

v

₂

, a

2

= v

2

v

3

,….. a

n

= v

_n

v

_n_₁

(notare che il secondo estremo di ogni arco coincide con il primo estremo dell’arco seguente, in modo che gli archi siano percorsi di seguito, senza “salti”). Si dice anche che il cammino unisce il vertice v

1

(primo vertice del primo arco) con il vertice v

n+1

(secondo vertice dell’ultimo arco).

Il numero n è detto lunghezza del cammino. Notiamo che nella definizione di cammino, è consentito che un arco sia percorso più volte, quindi il numero n può essere maggiore del numero di archi distinti percorsi nel cammino.

Nel grafo dei ponti, un esempio di cammino di lunghezza n=6 può essere il seguente:

1=

ab

, 2=

ba

, 1=

ab

, 5=

bd

, 5=

db

, 4=

bc

(la lunghezza è n=6, ma sono in tutto 4 gli archi distinti, perché 2 archi sono percorsi ognuno 2 volte)

Dato un cammino in un grafo:

a

1

= v

₁

v

₂

, a

2

= v

2

v

3

,….. a

n

= v

_n

v

_n_₁

tale cammino è detto ciclico se il primo vertice v

1

del primo arco coincide con il secondo vertice v

n+1

dell’ultimo arco (ciò corrisponde praticamente a percorrere un cammino tornando al vertice da cui si è partiti).

Nel grafo dei ponti, un esempio di cammino ciclico può essere il seguente:

1=

ab

, 2=

ba

, 6=

ad

, 5=

db

, 2=

ba

(si parte dal vertice a e si ritorna alla fine del cammino sullo stesso vertice).

Un cammino in un grafo è detto Euleriano se percorre tutti gli archi del grafo ognuno 1 sola volta.

Il problema dei ponti di Könisberg si traduce, nel linguaggio dei grafi, nel seguente quesito: esiste nel grafo dei ponti un cammino Euleriano ciclico ?

Più in generale: sotto quali condizioni esiste in un grafo un cammino ciclico Euleriano ?

(4)

Per rispondere a tali domande, introduciamo il concetto di grado di un vertice e di grafo connesso.

Dato un grafo, il grado di un vertice w è il numero di archi che hanno w come estremo. Se il grado di w è 0 (cioè se nessun arco ha w come estremo) si dice che w è un vertice isolato.

Esempio: nel grafo dei ponti i vertici a, d, c hanno grado 3, il vertice b ha grado 5 e nessun vertice è isolato.

Un grafo è detto connesso, se, comunque dati 2 vertici distinti v, w, esiste sempre almeno un cammino che unisce v e w.

Esempio: il grafo dei ponti è connesso (infatti dati comunque 2 vertici distinti esiste sempre un cammino che li unisce: in particolare i vertici a, c sono uniti da un cammino di lunghezza 2, mentre per ogni altra coppia di vertici, esiste un cammino di lunghezza 1, cioè un singolo arco, che li unisce).

Il seguente grafo con 6 vertici e 5 archi non é connesso:

a b c d x z

perché, per esempio, non esiste nessun cammino che unisce il vertice a con il vertice c.

Il prossimo Teorema (che dimostreremo in seguito) fornisce una condizione necessaria e sufficiente per l’esistenza in un grafo di un cammino ciclico Euleriano.