Matematica
Discreta
6
Dicembre
2011

La
correzione
del
compito
sara’
effettuata
il
giorno
14
Dicembre
ore
14.30
in
aula
da
destinarsi

Risultati
Compitino
BBBBB

1.

Si consideri il grafo semplice non orientato, in cui i vertici sono tutti i numeri naturali con un numero di cifre (in base 10) compreso fra 3 e 9 (inclusi) e in cui le cifre

Ricordiamo che nel corso della dimostrazione del Teorema di esistenza del mcd(a,b) si è anche dimostrato che il mcd(a,b) è combinazione lineare dei numeri a,b con coefficienti

Un grafo orientato è detto connesso se, comunque dati 2 vertici distinti v,w, esiste sempre almeno un cammino fra i due vertici (cioè un cammino che ha v come vertice di partenza,

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

Il prossimo risultato dimostra che, nel caso di dominio e codominio finiti e con la stessa cardinalità, i concetti di funzione iniettiva e surgettiva in pratica

dove i puntini contengono una formula algebrica nella variabile x, intendendo con ciò che, dato un elemento aA, il corrispondente b=f(a)B si ottiene sostituendo nella formula

Dati i naturali a,b definiamo combinazione lineare di a,b a coefficienti interi relativi un qualunque numero intero relativo della forma ax+by dove i numeri

Interpretando nella teoria dei grafi tale problema si arriva alla seguente definizione: dato un qualunque grafo (orientato o no) un cammino Hamiltoniano è