Ciao. Sul "bella" non mi pronuncio. Nel week-end ho buttato giù questa. Spero non contenga troppe inesattezze...enomis_costa88 ha scritto:dov'è che posso trovare una bella dispensa sui grafi??
Definizioni:
Di un grafo possiamo dare due definizioni: una più intuitiva e grafica, l'altra più precisa e insiemistica.
Un grafo è un insieme di punti (detti vertici oppure nodi) e di archi (oppure spigoli o anche lati) che hanno gli estremi nei vertici.
Ci sono alcune regolette che questi archi devono soddisfare:
- gli estremi di un arco sono su vertici distinti (salvo che non sia esplicitamente consentito il contrario)
- se un arco congiunge X con Y, nessun altro arco congiunge X con Y (altrimenti si parla di multigrafo
In un grafo non conta la topografia, ma la combinatoria, quindi non è importante sapere se le righe degli archi sono dritte o storte, si intersecano o no. E' invece importante sapere chi è collegato con chi.
Questo suggerisce la definizione insiemistica:
Un grafo è un insieme V di vertici e un insieme A, con la proprietà che gli elementi di A sono sottoinsiemi di due elementi di V (=coppie non ordinate di V).
A è l'insieme degli archi: un arco (grafico) è tracciato tra i vertici X e Y sse la corrispondente coppia {X,Y} (arco insiemistico) appartiene ad A.
Notate che in questo modo garantite automaticamente le due regolette degli archi. Nel seguito non sarà importante quale delle due rappresentazioni (grafica o insiemistica) scegliete. Normalmente alcuni concetti sono più intuitivi se vi fate un disegno.
-----------------------------------
Terminologia:
Un grafo è finito se ha un numero finito di vertici. Nel seguito supporrò sempre i grafi finiti.
Dato un grafo un suo sottografo è ottenuto cancellando alcuni (eventualmente nessuno) archi e alcuni (ev. nessuno) vertici, in modo che l'oggetto ottenuto sia ancora un grafo (e quindi, ad esempio, non si cancelli un nodo se ci sono degli archi che vi giungono).
Se in un grafo è possibile, camminando lungo gli archi, andare da X a Y, comunque si scelgano X e Y tra i nodi del grafo, si dice che il grafo è connesso.
Dato un vertice, l'insieme dei nodi raggiungibili dal vertice dato seguendo gli archi è detto componente connessa.
Il numero di archi che si dipartono da un nodo è detto grado del vertice. Un vertice di grado 0 è detto punto (nodo, vertice) isolato ed è sempre anche una componente connessa.
Un grafo è detto completo se contiene il massimo numero possibile di spigoli. Cioè, se per ogni coppia di vertici c'è un arco che li congiunge.
Un grafo è detto bipartito se è possibile colorare in rosso e blu i suoi vertici in modo tale che ogni arco abbia gli estremi di colori diversi. Un grafo è bipartito completo se contiene un arco per ogni coppia di vertici con colori diversi. Attenzione che la terminologia è ambigua e dicendo "bipartito" il più delle volte si sottintende "bipartito completo"!
Analogamente un grafo tripartito, quadripartito, ecc..., anche se si incontrano decisamente molto più di rado.
Dati due vertici nella stessa componente connessa, è possibile definire la distanza tra loro come il minimo numero di archi che occorre percorrere per andare da uno all'altro. La massima distanza possibile è detta diametro.
Un percorso lungo gli archi che consenta senza ripercorrere uno stesso spigolo più di una volta di tornare al punto di partenza è detto ciclo. Un grafo senza cicli è detto aciclico e, se è anche connesso, è detto albero
Se in un albero fissiamo un vertice particolare (che chiameremo radice). La distanza dalla radice è detto livello. Il livello massimo dei suoi nodi è detto altezza.
I vertici di grado 1 diversi dalla radice sono detti foglie. I vertici che non sono né radice, né foglie sono detti nodi intermedi (attenzione: spesso si sottintende "intermedio", con la possibilità di confondersi con l'altro significato di nodo come vertice generico; normalmente il contesto chiarisce).
Se tutti i nodi hanno grado 3 l'albero è detto binario. Se tutti i nodi hanno grado quattro è detto ternario, ecc...
Se è possibile disporre vertici e archi su un piano in modo tale che gli archi non si intersechino, il grafo è detto planare. [Nota di folklore: c'è un teorema non banale che dice che i vertici di un grafo planare possono essere disposti sul piano in modo che gli archi siano segmenti non intersecantisi.]
Se abbiamo un grafo planare, ognuna delle regioni in cui il piano è diviso è detta faccia. Notare bene: anche la regione illimitata è una faccia.
-----------------------------------
Esercizi
Dimostrare che ogni grafo ha un numero pari di vertici di grado dispari.
Dimostrare che: le componenti connesse sono sottografi connessi che costituiscono una partizione del grafo; essere nella stessa componente connessa è una relazione di equivalenza.
Quanti archi ha il grafo completo con n vertici? Quanto vale il grado di ogni suo vertice? Quanto vale il suo diametro?
Quanti archi ha un grafo bipartito [completo] con m vertici blu e n vertici rossi? Quanto vale il grado di ogni suo vertice? Quanto vale il suo diametro?
Supponiamo che un grafo abbia v vertici, tutti con lo stesso grado d e s spigoli. Trovare una formula che leghi d, v e s.
Dimostrare che la distanza è proprio una distanza, ossia che d(X,X) = 0, d(X,Y)=d(Y,X) e che vale la diseguaglianza triangolare d(X,Y) + d(Y,Z) >= d(X,Z).
Calcolare il numero di archi di un grafo aciclico, in funzione dei vertici e delle cp.ti cn.se.
Dimostrare che in un albero i nodi di livello massimo sono foglie. E' vero il viceversa?
Dimostrare che ogni nodo ha un unico arco che lo congiunge ad un nodo di livello inferiore. Usare questo fatto per dimostrare che il percorso che congiunge ogni vertice alla radice è unico; che dati due qualunque vertici, il percorso che li congiunge è unico.
In un albero si sa che la radice ha grado r, le foglie sono tutte al livello h e i nodi intermedi hanno tutti grado d. Calcolare il numero di foglie e il numero totale di vertici.
[Formula di Eulero] Se un grafo planare connesso ha F facce, V vertici e S spigoli, allora
F + V = S + 2
["Fatti Vedere Sabato alle Due": Facce + Vertici = Spigoli + 2]
Dimostrare che il grafo completo con 5 vertici e il grafo bipartito (3,3) non sono planari. Dimostrare che un qualunque grafo bipartito (n,2) è planare.
Dimostrare che un albero è un grafo planare.
[Numeri di Ramsey] Se coloriamo gli archi di un grafo completo con 6 vertici in rosso o blu, allora esiste un triangolo monocromatico. Dimostrare che 6 è il minimo possibile. Dimostrare che se coloriamo gli archi di un grafo completo con 17 vertici in rosso, blu o verde, allora esiste un triangolo monocromatico. Dimostrare che 17 è il minimo possibile.
[Ponti di Koenigsberg; Criterio di Eulero] E' possibile disegnare un grafo senza mai staccare la matita dal foglio se e solo se
- è connesso
- possiede al massimo 2 vertici di grado dispari.
Nel caso che abbia esattamente due vertici di grado dispari, dove si trovano gli estremi del percorso?