Grafi immersi in un libro, colorati, pesati e altro
(la numerazione dei §§, abbastanza arbitraria, ha il solo scopo di permettere qualche riferimento)
1.2. Che cosa intendiamo per grafi immersi in un libro?
[→ book embedding in Wiki o linear embedding in Math]
Per “immergerli”, dobbiamo idealmente disporre i nodi lungo il dorso o la costola del libro, e
rappresentare i lati mediante linee curve sulle pagine. Tra l’altro, avendo a disposizione abbastanza
pagine (almeno tante quanto lo spessore del grafo: si parla infatti di spessore o numero di pagine
per indicare il numero minimo necessario), anche un grafo non planare potrebbe essere facilmente
“disegnato” sulle pagine senza che le linee dei lati si intersecassero, se non nei nodi.
Ma il punto essenziale è che i nodi allineati lungo il dorso si succedono in un ordine ben preciso, e
questo ci permette di definire più semplicemente i collegamenti, ossia i lati, come vedremo tra un
attimo. Supporremo sempre che i nodi siano allineati orizzontalmente e ordinati da sinistra verso
destra, riservandoci però anche, eventualmente, di etichettare i nodi in modo non conforme
all’ordinamento.
Per esempio, avendo lati 12, 13, 14 e 34, almeno
una versione di Mathematica produce il grafo a
fianco, e non è affatto immediato ottenere la
rappresentazione conforme all’etichettatura
“naturale” 1234 invece di 3412.
Notiamo almeno tre cose. Come abbiamo già detto, i lati non devono necessariamente essere
rappresentati come segmenti rettilinei: curve qualsiasi o archi di cerchio o addirittura linee a zig-zag
vanno bene (purché non creino ambiguità) – e sono essenziali se i nodi sono allineati (come
abbiamo visto nell’esempio in cui lati lineari erano sovrapposti e quindi indistinguibili). Inoltre, e
più importante, potremmo rappresentare astrattamente i collegamenti mediante, per esempio, la
successione di interi 211 (che scriviamo al solito di seguito, sfruttando il fatto che gli interi sono
minori di dieci). Che significa 211? Significa che il primo nodo (quello più a sinistra) è collegato ai
2 successivi; il secondo e il terzo al (rispettivo) successivo. Infine, perché ci sono solo tre interi per
quattro vertici? Perché l’ultimo vertice non ha un successore, e quindi è inutile elencarne gli
(inesistenti) collegamenti successivi!
Osserviamo anche che, se “leggessimo” il grafo da destra a sinistra, la successione sarebbe 121, ma
è ovvio (vero?) che il grafo resta il medesimo, e potremmo anche rietichettare i nodi in modo da
avere etichette crescenti andando da destra a sinistra o viceversa, e quindi i lati sarebbero
rietichettati di conseguenza (ma anche la sequenza dei numeri di collegamenti cambierebbe: se
Mathematica non avesse cambiato l’ordine ovvero le etichette, la sequenza sarebbe stata 301 –
controllate). Un dato grafo, dunque, inteso come “struttura di collegamenti”, ammette
rappresentazioni diverse, non solo perché può essere “disegnato” in modi anche molto differenti,
ma soprattutto perché i nodi possono essere etichettati in modi diversi, e può non essere affatto
1 23 4
facile stabilire se due etichettature differenti corrispondano allo “stesso” grafo oppure no. Questo è
il problema dell’isomorfismo dei grafi, su cui torneremo in seguito.
Atteniamoci, come detto, alla successione dei vertici da sinistra a destra, per pura convenzione.
Qual è il caso più semplice dei collegamenti possibili? Quello in cui non ci sono collegamenti (il
grafo è detto vuoto) e quello in cui ci sono tutti i collegamenti possibili (il grafo è allora detto
completo). Ma a parte questi due casi estremi, il caso più semplice è quello in cui un nodo o è
collegato a tutti i suoi successori, oppure non è collegato a nessuno di essi. E qual è il modo più
semplice di rappresentare questa situazione? Invece di dire quanti sono i nodi collegati, basta
scrivere 1 se sono collegati tutti, e 0 altrimenti: un vettore (lista o parola, se preferite) binario di
n – 1 bit è sufficiente! Noi chiameremo codice del grafo il vettore binario che lo rappresenta. Il
grafo visto sopra può allora essere rappresentato dal codice 101: il nodo 1 è collegato a tutti gli altri,
il nodo 2 a nessuno dei successivi (ma è collegato al primo), il nodo 3 è collegato al 4. Se
assegniamo etichette crescenti da sinistra a destra ai nodi, otterremo esattamente i lati 12, 13, 14 e
34 come sopra, ma il grafo verrebbe rappresentato come qui sotto a sinistra.
Una rappresentazione compatta e conveniente! Per esempio, il grafo cui è associato il codice di 11
bit 10100011010 è rappresentato (con i nodi etichettati nell’ordine… stabilito da Math!) qui sopra a
destra ed ha 12 vertici e 11 + 9 + 5 + 4 + 2 = 31 lati, che sarebbe lungo elencare.
La rappresentazione binaria ci porta anche, in modo naturale, a considerare un concetto semplice
ma abbastanza importante: quello di grafo complemento. Se consideriamo il complemento a 1 del
codice, ossia, per esempio, se passiamo da 101 a 010, qual è la relazione tra i rispettivi grafi? Nel
grafo 010 il nodo 1 è isolato mentre il 2 è collegato a 3 e 4, ossia il grafo ha esattamente i lati che
mancano al grafo 101, e nessuno di quelli presenti in 101. In altre parole, il grafo 010 è il
complemento del grafo 101: i nodi sono gli stessi e se mettiamo assieme tutti i lati dei due grafi,
nessuno è doppio e nessuno manca.
1.3 Grafi rappresentabili a buon mercato
Quali grafi possiamo rappresentare in binario? Quali con liste di interi? Quali altre rappresentazioni
compatte possiamo escogitare? Ecco alcune delle domande cui risponderemo. I grafi che possiamo
rappresentare in binario sono i cosiddetti grafi a soglia, e ne riparleremo a breve (intanto potete
cercare di motivare la denominazione).
3 421 12 3 45 67 8 91011 12
Per generalizzare la scelta di collegare un vertice a tutti i suoi successori o a nessuno, possiamo
supporre di stabilire per ogni vertice a quanti successori è collegato, come abbiamo in pratica già
fatto nel paragrafo precedente. Per esempio, la lista di interi 3011 potrebbe abbinarsi a un grafo in
cui il nodo 1 è collegato a 3 successori, il nodo 2 a nessun successore, i nodi 3 e 4 sono collegati
ciascuno a un successore. Dunque l’elenco dei lati sarebbe 12, 13, 14, 34, 45 e il potrebbe essere
quello qui sotto.
Notiamo che questo grafo non è un grafo a
soglia, perché il primo nodo dovrebbe essere
collegato ai successivi 4 nodi oppure a nessuno,
ma non a 3. Qual è il vincolo sulle liste di interi
accettabili per rappresentare i collegamenti di
un grafo con n vertici? La lista dovrà avere lunghezza n – 1 e l’i-esimo intero non dovrà superare
n – i. Per 5 nodi, per esempio, la lista massima è 4321 (corrispondente al grafo a soglia 1111 ovvero
al grafo completo con 5 nodi, di solito indicato con la sigla K5 → pag. 130 del libro). Di fatto
potremmo ammettere liste di interi non negativi qualsiasi, pur di non vincolare il numero di nodi
alla lunghezza della lista: la lista 4331 corrisponderebbe a un grafo con 6 nodi, essendo il nodo 3
collegato appunto a 4, 5 e 6.
A un primo esame non si trovano in letteratura riferimenti a questo tipo di grafi. Li chiameremo
talvolta grafi a lista, ma sono di fatto ben noti come grafi di intervalli: infatti è possibile allineare
segmenti (o, appunto, intervalli) lungo una retta, e considerare le loro sovrapposizioni. I nodi del
grafo corrispondono agli intervalli e due nodi sono collegati se e soltanto se i due intervalli
corrispondenti sono sovrapposti. Elencando gli intervalli in ordine crescente di inizio, il grafo a lista
ci dice quanti intervalli successivi si sovrappongono a quello considerato.
L’approccio a lista ha il vantaggio che la lista massima ci indica immediatamente quante sono le
liste accettabili per un n-grafo, ossia un grafo con n nodi: sono n!. Abbiamo infatti n scelte per il
primo vertice: i valori da 0 a n – 1, poi n – 1 scelte per il secondo vertice e così via fino alle due
scelte, 0 o 1, per il penultimo vertice, e una sola per l’ultimo, che possiamo omettere.
L’approccio con gli intervalli si presta invece a rappresentare situazioni concrete, del tipo “quante
aule occorrono per poter tenere tutte le lezioni negli intervalli di tempo considerati?”, come già
avevamo visto.
Le nostre liste rappresentano anche una partizione del numero dei lati. Per esempio, la lista 3011
costituisce una partizione di 5 = 3 + 0 + 1 + 1, e 5 è il numero dei lati del corrispondente grafo a
lista. Ma esistono anche vari modi di associare partizioni alle permutazioni, ed esistono… i grafi di
permutazione, anch’essi (abbastanza) ben noti.
Prendiamo per esempio la permutazione 41352: il valore 4 precede i 3 elementi più piccoli, essendo
il primo; il successivo valore 1, essendo il minimo, non precede alcun elemento minore, mentre il 3
e il 5 precedono entrambi soltanto il 2. Se elenchiamo il numero di elementi minori successivi a
ciascun elemento, ossia le cosiddette inversioni della permutazione (rispetto alla permutazione
ordinata 12345), otteniamo 3011. E se passiamo ai grafi riotteniamo il nostro grafo con lista 3011,
oppure, rietichettando opportunamente i vertici, il grafo di permutazione avente per lati proprio le
inversioni, ossia 41, 43, 42, 32, 52. Ovvero i grattacieli che sarebbero nascosti dall’i-esimo
12 3 4 5
grattacielo (da sinistra) se non ci fossero in mezzo grattacieli più alti). O semplicemente le coppie
maggiore-minore.
È sempre così? Il grafo di permutazione è sempre isomorfo al grafo avente come lista quella del
numero di inversioni? Certo che no! Consideriamo per esempio la perm 436152 e la corrispondente
lista delle inversioni 32301 e generiamo i grafi relativi, rappresentati qui sotto.
È evidente che i due grafi non sono isomorfi: infatti quello generato da 32301 (a destra) ha come
sottografo il grafo completo K4 (quello coi vertici 1234), mentre il grafo di perm a sinistra non
contiene un K4; oppure si può notare che nessun vertice del grafo di perm ha grado 5, mentre il
nodo 3 del grafo a destra ha grado 5. Il grado di un nodo è il numero di lati incidenti, ossia il
numero di nodi a cui è collegato.
Ma esiste un grafo di perm isomorfo al grafo di destra? Certamente: la perm è per esempio 326541,
oppure 432651, oppure…. Si disegnino per esercizio questi grafi e se ne controlli l’isomorfismo!
Abbiamo così visto tre classi di grafi di ordine n rappresentabili in maniera molto economica: con
n-1 bit, i grafi a soglia, con n-1 (o meno) interi non negativi, i grafi di intervalli, con una
n-permutazione i grafi di permutazione. Una quarta la vediamo tra poco.
1.4 Esercizi e… problemi di ricerca!
Perché abbiamo scritto che i grafi di permutazione sono “abbastanza” ben noti? Innanzi tutto perché
purtroppo esistono definizioni diverse su che cosa debba intendersi per “grafo di permutazione”.
Noi ci atteniamo alla definizione “storica” (che è anche quella della Wikipedia e di
http://www.graphclasses.org/). Ma anche limitandoci ai “nostri” grafi di permutazione, un problema
è che nessuno sa quanti siano! Gli unici valori noti sul numero di grafi di permutazione non
isomorfi tra loro arrivano al caso di 10 vertici (A123448)! È chiaro che non tutti i grafi sono di
permutazione, ma tutti i grafi con 4 vertici o meno lo sono (ma quelli con 4 vertici, compresi quelli
sconnessi, sono soltanto 11). I grafi con 5 vertici sono 34 e quelli di permutazione 33: manca infatti
il ciclo con 5 vertici. Potete provare per esercizio a rappresentare C4, il ciclo con 4 vertici, come
grafo di permutazione o di lista, e cimentarvi nel compito impossibile di farlo per C5.
Attenzione: spoiler! La permutazione per C4 è 3412, e la lista per il grafo a lista… non c’è! Ma
come?! Abbiamo 220 per la lista delle inversioni: ma questa dà i lati 12, 13, 23, 24 e il grafo è il
“triangolo con la coda”, non il ciclo C4! Non c’è verso di ottenere C4 come grafo a lista. Anzi, ogni
4
3
1
2
6
5
1
23
4
5
6
grafo che contenga come sottografo indotto un ciclo di più di 3 nodi non è a lista: è facile
dimostrarlo, pensando agli intervalli!
Di fatto, i grafi di intervalli sono molti meno dei grafi di permutazione! Con 10 nodi abbiamo
67.659 grafi di intervalli e 524.572 grafi di permutazione. Quindi ovviamente i primi sono contenuti
nei secondi. O no?
Come possiamo (sperare di) scoprire un grafo a lista non perm?
Abbiamo accennato in precedenza al grado che
possiamo attribuire a ciascun nodo: il numero di
nodi collegati ad esso. Se elenchiamo in ordine,
per esempio crescente, i gradi di ciascun nodo,
otteniamo quella che si chiama la sequenza dei
gradi. È facile, data una perm o un lista, ricavare
la sequenza corrispondente: le sequenze distinte
sono molte meno delle perm! Sorprendentemente
si scopre, eseguendo un programma abbastanza
semplice, che la sequenza dei gradi 12235555 non
è tra quelle generate dalle 8! = 40.320 perm di 8
elementi, mentre è generata da ben 10 liste, per
esempio dalla 1413320, che fornisce il grafo qui a
fianco, com’è facile controllare per esercizio.
In realtà questo grafo non è il controesempio più piccolo all’ipotesi che i grafi di intervalli siano
contenuti in quelli di permutazione: c’è un grafo con 7 soli vertici che potete trovare
nell’illuminante e dettagliatissimo articolo di Stefan Hougardy, Classes of perfect graphs, Discrete
Mathematics 306 (2006) 2529 – 2571.
1.5. Grafi di diversità: la diversità rende perfetti!
Per finire… in Bell-ezza, vediamo come associare grafi a (una sottoclasse delle) sequenze CR.
Sfrutto un mio vecchio scritto (di quando formalizzavo) che non menzionava le CR, ma le
riconoscerete certamente, anche se partono da 0 invece che da 1.
Dato un insieme finito V di vertici, stabiliamo per ogni vertice un peso p (che sia, per esempio,
un numero naturale, p:V ℕ) e consideriamo adiacenti due vertici che abbiano pesi diversi:
considereremo a adiacente a b sse p(a) p(b). Un grafo i cui lati rappresentano questa relazione di
diversità sarà detto grafo di diversità.
1
2
3
4
5
6
7
8
Per esempio, dato V = {a, b, c, d, e} e p(a) = p(b) = 0, p(c) = p(d) = 1, p(e) = 2, il grafo di
diversità è il quadrato di vertici a, b, c, d e centro e: .
Come risulta chiaro anche dall’esempio, per specificare un grafo di diversità non è necessario
distinguere i vertici: è sufficiente specificare i loro pesi, più precisamente specificare quanti vertici
hanno peso 0, quanti hanno peso 1 e così via, convenendo per esempio di ordinare gli insiemi di
vertici con lo stesso peso in ordine di cardinalità decrescente e di assegnare i pesi in ordine
crescente a partire da 0 (o da 1, se si preferisce).
E’ subito evidente che i grafi di diversità con n vertici sono tanti quante le partizioni di n.
Infatti a ciascun grafo corrisponde esattamente una partizione degli n vertici in blocchi costituiti da
vertici con lo stesso peso.
E’ anche evidente che i pesi possono essere pensati come colori, dato che il grafo rispetta il
consueto vincolo della “buona” colorazione: vertici adiacenti debbano avere colori diversi; nei grafi
di diversità vi è tuttavia il vincolo aggiuntivo che, se due vertici hanno colori diversi, allora vi è
necessariamente un lato che li congiunge. Questo vincolo ulteriore fa anche sì che il numero di
colori non possa essere ridotto e pertanto il numero di pesi (o colori) usati risulta minimo, ossia è il
numero cromatico del grafo.
Se si rispetta la convenzione di assegnare peso 0 al maggior numero possibile di vertici, il
numero di zeri rappresenta anche il numero d’indipendenza del grafo, ossia la cardinalità di un
insieme indipendente massimo. I diversi blocchi di vertici di dato peso costituiscono gli insiemi
indipendenti massimali.
Se si considerano invece insiemi di vertici con pesi tutti diversi, si ottengono sottografi completi
o cricche, e il numero di cricca, la dimensione di una cricca massima, coincide evidentemente col
numero cromatico (mentre in generale è soltanto minore o uguale), e questo vale sia per l’intero
grafo sia per tutti i grafi indotti, ossia i grafi di diversità sono perfetti. Si veda
https://it.wikipedia.org/wiki/Grafo_perfetto oppure, per esempio, le Note di Vadim Lozin
https://homepages.warwick.ac.uk/~masgax/Graph-Theory-notes.pdf. Se si vogliono gli imperfetti,
come il ciclo C5 (numero di cricca = 2, numero cromatico = 3), si veda per esempio
http://mathworld.wolfram.com/ImperfectGraph.html.
I grafi di diversità costituiscono dunque un sottinsieme molto particolare di grafi, e anche molto
ristretto (ci sono, per esempio, 34 grafi non isomorfi con 5 vertici, ma solo 7 partizioni di 5, e
quindi 7 grafi di diversità). E’ facile contarli, facile dimostrare che sono perfetti, facile stabilire se
un grafo è di diversità oppure no (basta pensarci un attimo...). Possono andar bene come esempio
didattico, ma sono una classe tutto sommato banale di grafi, o hanno qualche rilevanza?
Perché non sembrano esserci riferimenti in letteratura? Probabilmente perché sono banalmente
grafi k-partiti (o multipartiti) completi: i nodi di un colore non sono collegati tra loro e sono invece
collegati a tutti gli altri. Di seguito cerchiamo di trovare alcuni motivi di interesse.
Un grafo di diversità può essere vuoto, ossia non avere alcun lato, e questo accade se e solo se
abbiamo un unico colore per tutti i vertici, che restano perciò isolati. Altrimenti, se vi sono almeno
2 colori, non solo non vi sono vertici isolati, ma il grafo è addirittura connesso, vero?
Consideriamo il cammino con 4 vertici P4: è un grafo di diversità? E il triangolo caudato o
zampa o imbuto K1,3 + x (notazione di Harary: la stella a 3 punte più un lato)? Basta provare a
colorarli per escluderli. I grafi multipartiti completi escludono sia P4 sia la zampa come sottografi
indotti. I grafi che escludono P4 come sottografo indotto costituiscono la classe ampiamente studiata
dei cografi, che è un sottinsieme dei grafi di permutazione. I nostri grafi sono quindi casi (molto)
particolari di cografi. Si veda in OEIS la sequenza A000084 per i cografi.
Tra i grafi multipartiti completi spiccano poi i grafi di Turán, in cui i colori sono ripartiti il più
equamente possibile (per esempio 3,3,4, se abbiamo 10 vertici).
C’è però un altro modo di interpretare la colorazione: collegare solo nodi con lo stesso colore,
al contrario di quanto fatto finora. Otterremo unioni disgiunte di grafi completi (o grafi a grappoli –
cluster), grafi che sono i complementi dei multipartiti completi, evidentemente in corrispondenza
biunivoca tra loro. Per questi grafi la caratterizzazione è più semplice: non dev’esserci P3 come
sottografo indotto! Infatti così li caratterizza e conta la sequenza A000041. Ma allora possiamo
caratterizzare anche i nostri grafi multipartiti come i grafi che escludono semplicemente il
complemento di P3, ossia K1 + K2 (cfr. fig. 3.20 del libro).
Ancora, i grafi di diversità sono i grafi di quelle permutazioni che corrispondono a partizioni
(di insiemi ora!) in cui ciascun blocco è ordinato: per esempio, per n = 5, abbiamo che la partizione
05 corrisponde alla permutazione ordinata 12345, la partizione 1 0
4 corrisponde alla permutazione 5
1234, la 12
03 a 45 123, la 2 1 0
3 a 5 4 123, la 2 1
2 0
2 a 5 34 12, la 3 2 1 0
2 a 5 4 3 12 e infine la
4 3 2 1 0 a 5 4 3 2 1.
3.1 Soglie o binari?
Finora non abbiamo dato la minima giustificazione per il nome attribuito ai grafi “a soglia”:
avremmo potuto ugualmente bene chiamarli grafi “a sogliola”… schiacciati come sono tra le pagine
! Ebbene, entrino i grafi a soglia!
Supponiamo di attribuire a ciascun nodo di un grafo, ancora da specificare per quanto riguarda i lati,
un peso: un valore numerico intero o anche reale. Stabiliamo poi un valore di soglia: due nodi
saranno collegati da un lato se e soltanto se la somma dei loro pesi supera la soglia. I grafi che si
possono costruire in questo modo sono i grafi a soglia!
Altolà: i grafi a soglia non erano stati definiti nel § 1.3 come quelli rappresentabili in binario, ossia
i grafi in cui un nodo o è collegato a tutti i successivi oppure a nessuno? Stiamo parlando degli
stessi grafi o no? Non è mica evidente!
Prendiamo un grafo rappresentabile in binario e vediamo se riusciamo a stabilire una soglia… e poi
magari facciamo il contrario, dato che non vogliamo solo stabilire binario → soglia, ma anche il
viceversa. Dunque, sia 010011 la rappresentazione del nostro grafo, e per non farci mancare nulla
abbiamo anche il nodo 1 isolato, ossia non collegato ad altri nodi. Costruiamoci una tabella, per
chiarezza: riuscite a riempire l’ultima riga nel modo più semplice, con interi non negativi?
Nodi 1 2 3 4 5 6 7
Rappresentazione binaria 0 1 0 0 1 1
Peso
Non dovrebbe essere difficile. Intuizione: diamo pesi crescenti ai nodi via via più collegati. Quindi
diamo peso 0 al nodo 1 isolato, poi peso 1 ai nodi 3 e 4 che non sono collegati ai successivi. Adesso
procediamo da destra a sinistra: ai nodi 5 e 6 spetta peso 2, e al nodo 2 il peso 3. Ci siamo
dimenticati del nodo 7? È come 5 e 6, quindi peso 2. Ecco la tabella completata:
Nodi 1 2 3 4 5 6 7
Rappresentazione binaria 0 1 0 0 1 1
Peso 0 3 1 1 2 2 2
Ma qual è la soglia? È il peso massimo, ossia 3. Verifica. C’è il lato 12? No: la somma dei pesi deve
superare la soglia 3, laddove 0 + 3 = 3. Il nodo 2 risulta invece correttamente collegato a tutti gli
altri. I nodi 3 e 4 non riescono a superare la soglia coi successivi, mentre 5 e 6 sì.
Dovrebbe essere evidente che si può procedere anche al contrario. Fatelo per esercizio usando
questa tabella:
Peso 8 1 7 2 2 2 6 6 3 5 4 4
Rappresentazione binaria
Qual è la soglia? Funziona? Il grafo risultante dovrebbe essere una vecchia conoscenza: si veda
verso la fine del § 1.2.
Un altro passo. I pesi (e la soglia) stabiliscono le connessioni tra i nodi. È possibile stabilire pesi e
soglie anche per gli insiemi stabili, in modo che se la somma dei pesi dei nodi non supera la soglia,
allora l’insieme di quei nodi è stabile. In che modo?
I nodi isolati non sono un problema, possiamo attribuire loro peso 0. Poi c’è un nodo collegato a
tutti quelli non isolati (il primo di tipo 1), cui potremmo attribuire, come peso, proprio il valore di
soglia, in modo da sistemare tutti i lati che lo coinvolgono, purché si diano pesi positivi ai nodi non
isolati. Ma gli altri nodi di tipo 1, se presenti, possono comparire in insiemi stabili che non
contengano i loro vicini: se dessimo uno stesso peso ai nodi di tipo 0 non isolati e il valore di soglia
a tutti i nodi di tipo 1 non potremmo configurare questi casi. Dobbiamo dare un peso ai nodi di tipo
0 che ci consenta di sapere a quali nodi sono collegati! Per fare questo basta però semplicemente
che il peso di ciascun nodo collegato a un nuovo nodo di tipo 1 sia superiore alla somma dei pesi
dei nodi collegati soltanto ai nodi precedenti.
Vediamo l’esempio più complesso del grafo con 12 nodi, che mostra vari casi.
Peso per i lati 8 1 7 2 2 2 6 6 3 5 4 4
Rappresentazione binaria 1 0 1 0 0 0 1 1 0 1 0 (0)
Etichetta nodo 1 2 3 4 5 6 7 8 9 10 11 12
Peso per gli insiemi 47 1 46 2 2 2 40 40 8 32 16 16
Non ci sono nodi isolati (zeri iniziali), a cui attribuiremmo peso 0. Diamo peso 1 al nodo 2, il primo
0, e poi peso 2 ai nodi (di tipo 0) 4, 5 e 6, che sono così distinti dal nodo 2. Come distinguere il
nodo 9 dai precedenti nodi di tipo 0? Attribuendogli la somma dei pesi + 1, ossia 8. Analogamente,
il nodo 11 avrà peso 8 + 7 + 1 = 16, come il nodo 12 (che quindi converrebbe considerare di tipo 0).
I due nodi 11 e 12 possono essere sostituiti, in un insieme stabile, dal nodo 10 ad essi collegato, e
quindi è giusto attribuirgli lo stesso peso complessivo, 32. Analogamente, i nodi 9, 11 e 12 (oppure
9 e 10) possono stare insieme, oppure essere sostituiti da 7 o 8, che quindi avranno peso 8 + 32 =
40. Dovrebbe essere chiaro perché attribuire peso 46 al nodo 3 e finalmente 47 al nodo 1, e 47 è
anche il valore della soglia, la somma dei pesi dei nodi di tipo 0, che possono stare tutti nell’insieme
indipendente massimo.
Vediamo un’ultima proprietà abbastanza stupefacente dei grafi a soglia. Se vedo il codice 010011,
posso calcolare a vista il numero di sottoinsiemi indipendenti del grafo a soglia corrispondente!
34 = ((2 + 1 + 1) 2 2) + 1) 2. Qual è il trucco? Parto da destra, dal nodo 7: lui da solo mi dà 2
indipendenti: lui stesso e il vuoto. Poi il nodo 6 è collegato a tutti i successivi, dunque aggiunge
solo se stesso, così come il 5. Ma il nodo 4 è invece scollegato, e raddoppia il numero degli
indipendenti, dato che possiamo aggregarlo oppure no. Idem per il 3. Il 2 aggiunge 1 e il nodo 1
raddoppia. La tabella può aiutare:
Nodi 1 2 3 4 5 6 7
Rappresentazione binaria 0 1 0 0 1 1
Insiemi indipendenti 34 17 16 8 4 3 2
3.2 Sequenze dei gradi, partizioni grafiche, tabelle di Young e grafi canonici
Possiamo rappresentare la sequenza dei gradi di ciascun nodo, ordinata in qualche modo canonico
(per esempio in ordine non crescente). Prima di ordinare dobbiamo stabilire i gradi. Possiamo, per
esempio, ricuperare la tabella del grafo a soglia visto nel paragrafo precedente e iscriverci i gradi.
Nodi 1 2 3 4 5 6 7
Rappresentazione binaria 0 1 0 0 1 1
Grado
La sequenza ordinata sarebbe quindi 5333110. Nello storico Atlante dei grafi di Read & Wilson
questa sequenza sarebbe invece riportata come 0.12.3
3.5: l’ordinamento preferito è quello crescente
e le molteplicità sono indicate con un esponente.
In alternativa, possiamo considerare di pensare i gradi come le parti della partizione di un intero: la
scomposizione dell’intero in addendi che sommati danno l’intero. Quale intero? Evidentemente, il
doppio del numero di lati, dato che ogni lato contribuisce al grado dei suoi due vertici. Abbiamo
così scoperto che la somma dei gradi dev’essere sempre un intero pari. Nell’esempio abbiamo
5+3+3+3+1+1+0 = 16, e la partizione si suole scrivere come (5,3,3,3,1,1,0) 16.
Quante sono le partizioni di 16? Infinite, dato che possiamo aggiungere un numero arbitrario di
parti nulle. Si conviene quindi che le parti non siano nulle, il che per noi significa che… è meglio
considerare soltanto grafi privi di nodi isolati: questi nodi li possiamo sempre elencare a parte, se
davvero ci interessano.
Specificata una partizione, esiste sempre un grafo (semplice) che la realizzi come sequenza dei
gradi? Invece di enunciare un teorema, cerchiamo di scoprirlo passo passo! A questo scopo,
parliamo prima di un altro modo di rappresentare partizioni/sequenze: le tabelle di Young,
introdotte dal matematico Alfred Young nel 1900 per descrivere le rappresentazioni dei gruppi
simmetrici.
Una tabella ha tante righe quante sono le parti (positive) e ogni riga ha un numero di caselle pari al
valore della parte (anche qui, 0 caselle… non si vedrebbero). La novità è che nelle caselle si
possono iscrivere dei valori: per esempio, le etichette dei nodi collegati al nodo considerato, che
può avere etichetta diversa dal numero di riga, dato che abbiamo collocato le righe in ordine
decrescente di lunghezza! Qui le etichette creano forse confusione.
Vediamo la tabella relativa al nostro grafo senza il nodo isolato, di codice 10011. Possiamo
costruirla facilmente senza bisogno di vedere disegnato il grafo (però i nodi 4, 5 e
6 sono rappresentati nelle righe 2, 3 e 4 rispettivamente, mentre 2 e 3 sono in
fondo)! Per qualche ragione abbiamo scurito le caselle in diagonale e quelle
soprastanti.
La parte della tabella con le caselle scurite è costituita da (5,2,1) caselle e la parte
che sta sotto, con le caselle bianche, è costituita, per colonne, da (5,2,1) caselle.
Toh, proprio la stessa lista! Sarà un caso….
2 3 4 5 6
1 5 6
1 4 6
1 4 5
1
1
Prima di indagare su questo strano caso, diamo la semplice regola per trovare la sequenza dei gradi
partendo dal codice binario. Se ci sono zeri iniziali, li possiamo togliere: i nodi corrispondenti sono
isolati, hanno grado 0. Consideriamo allora il codice, senza gli zeri iniziali. Il primo nodo è dunque
collegato a tutti i successivi: il suo grado è pari alla lunghezza del codice. Il grado di un nodo
rappresentato da uno 0 è pari al numero degli 1 che lo precedono. Il grado di un nodo rappresentato
da un 1 è pari al numero degli 1 che lo precedono più il numero di bit che lo seguono. Per esempio,
dato il codice 0010100011010, il grado del nodo corrispondente all’ultimo 0 è 5, mentre il grado del
nodo corrispondente all’ultimo 1 è… di nuovo 5.
Vediamo un altro esempio, in cui facciamo a meno delle etichette, e prima un esercizio.
Esercizio. Costruire la sequenza dei gradi per il grafo a soglia con 12 nodi i cui pesi sono riportati
nella tabella alla fine del § 3.1, o il cui codice risulta 10100011010 (fine § 1.2), e verificare che la
sequenza (ordinata) risulta (11,10,7,7,6,5,5,4,2,2,2,1).
A fianco abbiamo riportato una rappresentazione diversa della
sequenza (11,10,7,7,6,5,5,4,2,2,2,1), ossia il cosiddetto
diagramma di Ferrers, (da Norman Macleod Ferrers,
matematico inglese dell’800; curioso che proprio l’Enciclopedia
Britannica – oltre al nostro libro EMC – scriva invece “Ferrer
diagram”) in cui le caselle sono sostituite da punti o altri
simboli. Il vantaggio delle tabelle di Young è che,
all’occorrenza, si possono inserire dei valori numerici nelle
caselle, arricchendo il significato della tabella stessa. Anche qui,
abbiamo evidenziato in rosso i punti in diagonale, e la parte di
diagramma comprendente la diagonale e i punti soprastanti
corrisponde alla partizione (11,9,5,4,2), mentre le colonne sottostanti hanno (11,9,5,4,2) punti.
Qualche reminiscenza? Alla fine del § 1.2 avevamo scritto che il grafo aveva 11 + 9 + 5 + 4 + 2 =
31 lati: infatti il nodo 1 era collegato a tutti i restanti 11 nodi, il nodo 3 ai seguenti 9, eccetera. In
altri termini, numerando i bit del codice 10100011010 da destra a sinistra, da 1 fino a 11, gli 1 si
trovano esattamente nelle posizioni (11,9,5,4,2).
Se le posizioni degli 1 determinano il grafo a soglia connesso, anche il diagramma dev’essere
determinato dalla sola porzione superiore, ed è facile vedere che la porzione inferiore dev’essere
simmetrica! Infatti, nel diagramma, il puntino nella colonna k della riga j, quando k j (la parte
superiore), ci dice che il nodo j ha bit 1 ed è collegato al (k+1)-esimo nodo. Analogamente, il
puntino nella riga k+1 e colonna j (cioè nella parte inferiore) ci rimanda al medesimo lato.
Se preferite una dimostrazione formale, un po’ complicata, potete vedere per esempio [Merris,
Combinatorics § 5.7]). La conclusione comunque è che i grafi a soglia connessi hanno sempre
sequenze dei gradi che corrispondono a diagrammi simmetrici, nel senso precisato sopra. E vale
anche il viceversa: se il diagramma è simmetrico, allora il grafo che realizza la corrispondente
sequenza dei gradi è un grafo a soglia, connesso. In ogni caso, a una partizione del numero di lati in
parti differenti corrisponde sempre uno e un solo grafo a soglia connesso, determinato dal
corrispondente codice! Non ci sono problemi di isomorfismo: ce n’è uno solo.
Quante sono le partizioni di un intero m in parti distinte? Possiamo ricorrere a manipolazioni
simboliche, perché la semplicissima espressione 1 + xk può ben rappresentare la scelta del valore k
per la k-esima parte, se scegliamo xk, oppure la sua assenza, se scegliamo 1. Quindi il numero di
partizioni di m in parti distinte è dato dal coefficiente di xm
nell’espansione del prodotto
(1 + x) (1 + x2)… (1 + x
m) = , dove
abbiamo supposto m = 8 e ottenuto i coefficienti anche per tutti i valori inferiori ad 8. A000009.
Il risultato ottenuto ci dice per esempio che ci sono 6 grafi a soglia connessi, aventi esattamente 8
lati… ma non ci dice quanti nodi hanno. È facilissimo invece contare i grafi a soglia connessi con n
nodi: il codice deve cominciare con 1 ed essere lungo n – 1, e ce ne sono quindi 2n-2
. Se contassimo
anche quelli non connessi potremmo avere degli zeri iniziali, e quindi tutti i 2n-1
vettori: metà sono
connessi e metà sconnessi.
Passando bruscamente ai grafi qualsiasi, come si fa a stabilire se una sequenza o partizione non
crescente è grafica, ossia è la sequenza dei gradi di un grafo, oppure no? È facilissimo, se… si
conosce il trucco.
E il trucco è… sbucciare la sequenza! Ovvero, se il primo elemento della sequenza vale x, lo
togliamo e diminuiamo di 1 gli x elementi successivi della sequenza, poi eventualmente la
riordiniamo: la sequenza originaria è grafica se e solo se lo è anche quella sbucciata e riordinata.
Cenno di dimostrazione (del teorema di Havel [1955], articolo in lingua ceca (→ Borůvka che
scrisse in moravo: https://it.wikipedia.org/wiki/Algoritmo_di_Bor%C5%AFvka) e Hakimi [1962]).
Se la sequenza sbucciata è grafica, si può costruire un grafo che la realizza. Se ora aggiungiamo un
nodo opportunamente collegato a x nodi del grafo, ecco che abbiamo un grafo per la sequenza
originale. Mentre, se abbiamo il grafo originale, possiamo scollegare un nodo di grado x e ottenere
un grafo per la sequenza sbucciata.
Che cosa vuol dire “opportunamente collegato”? Lo spieghiamo negli esempi qui sotto.
Esempi. Prendiamo la partizione 443322 (è più comodo senza parentesi e virgole, nevvero?) e
sbucciamola togliendo il primo nodo, di grado 4: cosa resta? La sequenza disordinata 32212.
Riordiniamola: 32221. Per la dimostrazione precedente, come facciamo a riottenere la partizione
originale? Non possiamo aumentare di 1 le prime quattro parti ordinate, se no otterremmo 443331,
dobbiamo incrementare la partizione disordinata; ma è sempre possibile incrementare le parti
“giuste”. Se ora procediamo con la sbucciatura abbiamo 1111. Possiamo arrestarci: abbiamo due
lati sconnessi, che sono pur sempre un grafo! Se invece partiamo da 544221 abbiamo 33110 e poi
200: un solo nodo di grado 2?! Certamente non è un grafo semplice, e la partizione non è grafica.
Attenzione a non confondere la sequenza dei gradi con la lista dei nodi successivi collegati, per i
grafi di intervalli!
Piccolo corollario: se (e solo se) non è mai necessario riordinare le sequenze sbucciate, perché sono
già in ordine non crescente, allora il grafo di partenza è a soglia. È una conseguenza della simmetria
del diagramma: la sbucciatura fa scomparire una riga e una colonna, e il diagramma resta della
forma corretta.
Divertiamoci un attimo. Costruiamo i grafi corrispondenti alla partizione 443322
dell’esempio. Per procedere, partiamo dalla partizione vista sopra, 1111, realizzata
evidentemente solo da una coppia di lati disgiunti. Per passare alla 32221 dobbiamo
aggiungere un nodo e collegarlo a 3 dei 4 preesistenti: lo possiamo fare in un solo
modo (prescindendo dalle diverse etichettature), quello riportato a fianco, in cui il
nodo 5 è quello aggiunto. Per passare a 443322 dobbiamo collegare il sesto nodo al nodo di grado 3
(etichetta 5), a quello di grado 1 (etichetta 4), e a due dei tre nodi di grado 2, e abbiamo quindi due
scelte non equivalenti: lati 61 e 62, oppure 61 e 63. La scelta 62 e 63 è “equivalente”, ovvero
produce un grafo isomorfo a quello di lati 61 e 63.
I due grafi costruiti sopra sono gli unici non isomorfi che realizzano 443322? Purtroppo (o per
fortuna) no: se partiamo da un lato più due nodi isolati, e colleghiamo altri due nodi non collegati
tra loro ma li colleghiamo entrambi a questi 4 nodi iniziali, abbiamo un grafo in cui i nodi di grado
4 non sono collegati tra loro, e quindi evidentemente non isomorfo a quelli in cui viceversa sono
collegati. Ci sono poi altri due grafi non isomorfi a questi, che il lettore può divertirsi a cercare,
oppure può accontentarsi di… apprezzare la complessità del problema dell’isomorfismo.
Problema (aperto?). Caratterizzare i grafi determinati univocamente (a meno di isomorfismo) dalla
sequenza dei gradi.
3.3 Spogliarelli e logge segrete
Come si può stabilire se un grafo è a soglia? Nulla di più facile, potreste pensarci da soli. Pensate a
spogliare (o sbucciare) il grafo…. Se siete moralisti o pigri, ecco l’algoritmo.
1) Se ci sono nodi isolati, si eliminano. Se ci sono altri nodi si prosegue, altrimenti il grafo è a
soglia.
2) Se c’è un nodo collegato a tutti gli altri, lo si elimina e si torna al passo 1), altrimenti il grafo non
è a soglia.
L’algoritmo considera la struttura “in grande” del grafo e la “spoglia” passo passo fino a
conclusione. Un altro modo di procedere, molto più interessante, è invece quello di considerare la
struttura del grafo “in piccolo”: quali sottografi non devono esserci in un grafo a soglia? Abbiamo
già visto la nozione di sottografo: un sottoinsieme dei nodi e dei lati che li collegano nel grafo
originario. Ma qui vogliamo un sottografo indotto: scegliamo certi nodi e li colleghiamo con tutti i
lati che li collegavano tra loro nel grafo originario, senza ometterne (né aggiungerne, ovviamente)
nessuno.
Consideriamo un grafo a soglia e il suo codice. Com’è fatto e qual è il codice di un sottografo
indotto? Prendiamo certi nodi e i bit corrispondenti nel codice. Un bit 1 indica che il nodo è
collegato ai successivi, un bit 0 è collegato solo agli 1 precedenti, esattamente come nel grafo
originario. Dunque un sottografo indotto di un grafo a soglia è sempre un grafo a soglia!
Vediamo quali sono i grafi a soglia “piccoli” e quali grafi piccoli non sono a soglia. I grafi non
isomorfi con 3 nodi (anche isolati) sono 4 (disegnarli per esercizio) e sappiamo che anche i grafi a
soglia con 3 nodi e dunque codice di lunghezza 2 sono 4. I grafi con 4 nodi, invece, sono 11, ma ci
5
1
2
3
4
sono solo 8 grafi a soglia: quali sono i 3 mancanti? È un semplice esercizio scoprire che i 3 grafi
non a soglia sono 2P2, P4 e C4: 2 lati separati (descritti comunemente come 2K2), il cammino con
4 vertici, e il 4-ciclo. L’algoritmo ovviamente conferma: non ci sono nodi isolati né nodi connessi a
tutti gli altri. Quei sottografi indotti sono proibiti nei grafi a soglia! Ogni riferimento a logge segrete
e simili è puramente casuale.
Il bello è che vale anche il viceversa: se un grafo non ammette nessuno dei 3 proibiti come
sottografi indotti, allora è a soglia. O anche: se un grafo non è a soglia, posso trovare 4 nodi che
formano un sottografo indotto proibito. Infatti, applichiamo il nostro algoritmo: poiché il grafo non
è a soglia, al passo 2 abbiamo ancora almeno 4 nodi, ma non troviamo un nodo collegato a tutti gli
altri, ma neppure più nodi isolati. Allora scegliamo un nodo x di grado massimo, d(x), e un nodo y
non collegato ad x. Il nodo y non può essere isolato, quindi possiamo scegliere un nodo z a cui è
collegato. Ma anche x non può essere isolato: scegliamo w che sia collegato a x ma non a z. Esiste
un nodo w con questi collegamenti? Deve esistere, perché il grado di x è massimo: se ogni nodo
collegato a x fosse collegato anche a z avremmo d(z) > d(x) perché z è collegato anche a y mentre x
non lo è. Ed ecco formato il sottografo proibito: se non ci sono altri lati tra i nodi x, y, z e w,
abbiamo 2K2 con xw e yz; se c’è anche xz oppure yw abbiamo P4, mentre se ci sono entrambi
questi lati abbiamo C4.
Per completare il quadro, abbiamo già visto che i grafi liberi da P4 (soltanto) formano la classe dei
cografi (§1.5), mentre i grafi liberi da P4 e da C4 sono i grafi detti quasi a soglia o banalmente
(trivially) perfetti. Le classi caratterizzate da sottografi indotti proibiti sono chiamate anche classi
ereditarie, perché le proprietà vengono ereditate dai sottografi indotti.
4. I grafi possono evolvere?
Avevamo affermato che i grafi col massimo numero di sottoinsiemi indipendenti, fissato il numero
n dei nodi e il numero k dei lati, sono i grafi a soglia aventi codice massimo tra quelli con le
caratteristiche volute. Non l’avevamo enunciato proprio in questo modo, ma ormai dovrebbe essere
chiaro che possiamo dirlo così.
Vogliamo ora dimostrare questa affermazione, mediante il seguente schema. Partiamo da un grafo
qualsiasi con n nodi e k lati. Modifichiamo il grafo mantenendo immutato il numero di nodi e lati,
secondo un percorso irreversibile che non fa mai diminuire il numero di sottoinsiemi indipendenti e
termina nel grafo a soglia di codice massimo.
Sia G un grafo semplice e consideriamo due nodi x e y qualsiasi: possono essere collegati oppure
no. Diciamo A l’insieme dei nodi collegati a x che non sono collegati a y, B l’insieme dei nodi
collegati sia a x sia a y, e infine C l’insieme dei nodi collegati soltanto a y. Supponiamo che né A né
C siano vuoti.
Che cosa succede se non riusciamo a trovare due nodi che abbiano A e C non vuoti? Vedi oltre.
Che cosa succede se trasformiamo il grafo G nel grafo Gxy prendendo i nodi di A, che erano
collegati solo a x, scollegandoli tutti da x e collegandoli invece tutti a y? Nel grafo Gxy l’insieme di
nodi “comuni” B è rimasto immutato, ma il grado del nodo y è cresciuto esattamente di quanto è
diminuito il grado di x (e almeno di 1, dato che l’insieme A non era vuoto). Il numero dei lati
rimane invariato, come quello dei nodi. Chiamiamo compressione di x in y questa operazione
(seguendo più o meno l’articolo sul Journal of Graph Theory Volume 67 issue 4, 2011, di Cutler
Radcliffe -- Extremal graphs for homomorphisms).
E che cosa succede se “comprimiamo” ripetutamente il nostro grafo G, facendolo per così dire
“evolvere” fin quando raggiungerà un grafo H “incomprimibile”? Dobbiamo innanzi tutto mostrare
che il processo di compressione termina: altrimenti il grafo potrebbe comprimersi e poi…
espandersi di nuovo, in un ciclo infinito!
Ispirandoci alla fisica, consideriamo dunque l’entropia e(G) di un grafo G (solitamente però
chiamata varianza dei gradi): la somma dei quadrati dei gradi dei nodi. Indichiamo ora con a il
numero di nodi nell’insieme A, con b il numero in B, e con c il numero di nodi in C. Come varia
l’entropia dopo una compressione di x in y? Prima della compressione, nel grafo G, x aveva grado
a + b + d, e y grado b + c + d, dove d vale 0 se x e y sono scollegati, 1 altrimenti. Dopo la
compressione, ossia nel grafo Gxy, il nodo x perde a nodi collegati, mentre il nodo y li guadagna:
quindi x avrà grado b + d mentre y avrà grado a + b + c + d. Tutti i gradi degli altri nodi restano
immutati. Come varia dunque l’entropia?
e(Gxy) – e(G) = (b + d)2 + (a + b + c + d)
2 – (a + b + d)
2 – (b + c + d)
2.
Poiché i termini quadratici sono gli stessi sommati e sottratti, essi si elidono, e resta soltanto
2 a b + 2 a c + 2 b c + 2 a d + 4 b d + 2 c d – (2 a b + 2 b c + 2 a d + 4 b d + 2 c d) = 2 a c,
che per ipotesi (quella che né A né C siano vuoti) è positivo! Dunque a ogni compressione
l’entropia del grafo ottenuto cresce, e anche se ripetessimo successivamente (quando ridiventasse
possibile) la compressione tra i due stessi nodi y e x in senso inverso, non riotterremmo lo stesso
grafo, ma uno con entropia maggiore!
Consideriamo ora un insieme indipendente I del grafo G. Se I non contiene il nodo y, allora è
indipendente anche in Gxy, perché solo al nodo y sono stati aggiunti lati nella compressione.
Se viceversa I contiene y, allora I non è indipendente in Gxy se (e solo se) esiste in I un nodo z
appartenente all’insieme A definito sopra, che è stato collegato a y nella compressione. L’insieme I
non può contenere nodi di B, perché questi sono tutti collegati con y, ma y ora deve stare in I. Se
prendiamo l’insieme Ixy in cui y viene sostituito da x mentre tutti gli altri nodi sono quelli
dell’insieme I, abbiamo viceversa un insieme che è indipendente in Gxy mentre è dipendente in G:
infatti xz è un lato in G, dato che z apparteneva ad A, mentre in Gxy x ha soltanto collegamenti con
nodi in B, che quindi non sono in Ixy.
Quanto detto sopra significa che per ogni insieme indipendente I di G ne possiamo trovare uno, Ixy,
indipendente in Gxy. Ciò non esclude che Gxy possa avere anche altri insiemi indipendenti: ma
allora gli indipendenti di Gxy sono almeno tanti quanti quelli di G. Ogni compressione può far
aumentare il numero di insiemi indipendenti, o mantenerne invariato il numero, ma certamente non
li fa diminuire.
Consideriamo ora tre casi particolari e significativi, che fungeranno anche da esempi.
1) G = 2K2. Il grafo G è costituito da due lati disgiunti, xz e yw. L’insieme A dei nodi collegati a x
è costituito solo da z, B è vuoto, C comprende solo w. Il grafo compresso Gxy ha lati yz e yw,
mentre il nodo x è isolato. Gli insiemi indipendenti di G, oltre al vuoto e ai singoletti, che daremo
sempre per scontati, sono xy, xw, yz e wz; quelli di Gxy sono xy, xz, xw, wz e xwz, uno in più.
Nel grafo G ogni nodo ha grado 1, quindi l’entropia è 4; nel grafo compresso Gxy il nodo y ha grado
2 e x ha grado 0, dunque l’entropia vale 0 + 4 + 1 + 1 = 6.
2) G = P4. Il grafo G è il cammino con 4 nodi zxyw. Gli insiemi A, B e C sono gli stessi di prima.
Gli indipendenti di G sono xw, wz e yz. Staccando z da x e attaccandolo a y otteniamo il grafo
compresso Gxy: la stella con centro y e punte w, x e z. Gli indipendenti di cardinalità maggiore di 1
sono xw, xz, wz e wxz, uno in più di prima. Notiamo che le compressioni di z in w o viceversa,
pure possibili, non aumenterebbero invece il numero di indipendenti.
Nel grafo G l’entropia vale 1 + 1 + 4 + 4 = 10; nel grafo compresso Gxy l’entropia vale
1 + 1 + 1 + 9 = 12.
3) G = C4. Il grafo G è il 4-ciclo ottenuto chiudendo P4 col lato wz. Gli indipendenti di G sono
dunque soltanto xw e yz. Staccando z da x e attaccandolo a y otteniamo il grafo compresso Gxy che
ha come indipendenti xw e xz, senza incremento. Nel grafo G ogni nodo ha grado 2, quindi
l’entropia è 4 4 = 16; nel grafo compresso Gxy il nodo y ha grado 3 e x ha grado 1, dunque
l’entropia vale 1 + 9 + 4 + 4 = 18.
Se G è un grafo qualsiasi avente come sottografi indotti 2K2, P4 o C4, successive compressioni li
elimineranno, arrivando infine a un grafo libero da questi sottografi indotti. Come abbiam visto, un
grafo cosiffatto è un grafo a soglia. Se nel grafo di partenza G non è possibile trovare due nodi che
abbiano A e C non vuoti, questo significa che è già un grafo a soglia!
Il meccanismo della compressione fornisce un curioso abbinamento tra grafi con un dato numero di
nodi. Dato infatti un grafo G, l’insieme delle coppie di nodi che possono dar luogo alla
compressione di G (quelli per cui i due insiemi A e C non sono vuoti) può essere interpretato come
l’insieme dei lati di un grafo Gc che potremmo chiamare grafo di compressione (non ci risulta sia
mai stato definito prima). Determinare il grafo di compressione Gc a partire dal grafo G è facile: xy
è un lato di Gc se e soltanto se in G esistono due lati, xz e yw, e i nodi z e w sono distinti.
Il grafo Gc fornisce informazioni sul grafo G: in particolare, se Gc non ha lati, allora G è un grafo a
soglia (non può essere compresso), mentre se è vuota l’intersezione tra i lati di G e quelli di Gc,
allora la compressione può essere fatta solo su certe coppie di nodi di G non collegate. Se l’insieme
B è inoltre sempre vuoto, allora il grafo G è detto quasi a soglia o banalmente perfetto (un’altra
classe di grafi nota, sottoclasse di quella dei grafi perfetti). Nei grafi quasi a soglia, dunque,
esistono sottografi indotti costituiti da 4 nodi che formano il grafo 2K2, ossia due lati sconnessi xz e
yw, mentre non ci sono P4 né C4.
Possiamo concludere che il grafo a soglia ottenuto al termine dell’“evoluzione” del grafo iniziale G
avrà non solo entropia maggiore (se è stata fatta almeno una compressione, ovvero il grafo non era
già a soglia) ma anche un numero di insiemi indipendenti almeno pari a quelli di G.
Tuttavia, l’evoluzione non finisce qui! Anche i grafi a soglia possono evolvere, sia pure in modo
diverso, e per fortuna più semplice. Possiamo sfruttare la rappresentazione del grafo a soglia tramite
il suo codice, ossia la parola binaria che indica se un nodo è collegato a tutti i successivi (bit 1)
oppure a nessuno (bit 0). Per far evolvere il grafo a soglia mantenendo costante il numero dei lati
possiamo effettuare la trasformazione di una parola binaria P01Q10R nella parola P10Q01R, dove
P, Q ed R indicano parole binarie eventualmente vuote. Questa trasformazione incrementa il valore
numerico del codice, ma incrementa anche il numero di insiemi indipendenti, come possiamo subito
dimostrare ricordando come si calcolava il numero di indipendenti nel grafo a soglia di dato codice.
Se infatti r è il numero di indipendenti associati al grafo avente per codice il suffisso R (ricordiamo
che r vale 2 anche nel caso che R sia la parola vuota!), il grafo 10R ha 2r + 1 indipendenti, mentre
01R ne ha 2(r+1) = 2r + 2: un nodo non collegato (bit 0) raddoppia gli indipendenti (quelli esistenti
più quelli a cui si aggiunge il nuovo nodo), mentre un nodo collegato a tutti i successivi (bit 1)
fornisce un solo indipendente in più, il nodo stesso. Analogamente, se il grafo di codice Q ha q
indipendenti, allora 01Q avrà 2(q + 1) = 2q + 2 indipendenti, mentre 10Q ne avrà 2q + 1. È una
diminuzione, ma è indispensabile per mantenere costante il numero dei lati. L’incremento dovuto
alla trasformazione 10R → 01R compensa la diminuzione: anche nel caso peggiore in cui Q fosse
vuoto, il grafo 1001R avrebbe 1 + 4(r + 1) = 4r + 5 indipendenti, mentre quello originario 0110R
ne avrebbe 2(2r + 2) = 4r + 4, uno in meno.
In conclusione, come volevamo dimostrare, i grafi con dato numero di nodi e lati, aventi il massimo
numero di insiemi indipendenti, sono i grafi a soglia aventi codice numericamente massimo.
Questo schema di evoluzione, o altri simili, possono essere utili in altri contesti?
Quali grafi hanno il massimo numero di partizioni indipendenti o stabili (cfr. libro pag. 165)?
Anche queste si determinano facilmente nei grafi a soglia?
Top Related