Matematica Discreta Lezione del giorno 21 gennaio 2011
Testo completo
Documenti correlati
Si basa sul seguente risultato di insiemistica: se A,B sono insiemi finiti, con A=n, B=m, e se n>m , comunque data una funzione f: A → B, esistono sempre almeno 2
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
Se A,B sono insiemi infiniti, diremo che A è equipotente a B (o anche che A,B hanno la stessa cardinalità) se esiste una funzione biunivoca f: A B (scriveremo in tal caso AB).
Costruiamo un nuovo grafo ottenuto dal precedente aggiungendo un arco che colleghi i vertici v,w: otteniamo un grafo in cui esiste un cammino ciclico Euleriano, e possiamo applicare
Dalla teoria delle componenti connesse di un grafo, segue che, per calcolare il numero cromatico di un grafo, possiamo operare nel modo seguente: nella colorazione dei vertici
- sappiamo che k é il numero dei vertici, e la somma degli elementi numerici di ogni riga è il grado del vertice corrispondente; inoltre il numero r degli archi potrà essere
N indicherà l’insieme dei numeri interi positivi (detti anche numeri naturali), Z indicherà l’insieme dei numeri interi relativi (ossia dei numeri interi
dove i puntini contengono una formula algebrica nella variabile x, intendendo con ciò che, dato un elemento aA, il corrispondente b=f(a)B si ottiene sostituendo nella formula