Digrafo aciclico connesso
In teoria dei grafi per digrafo aciclico connesso si intende un digrafo (grafo orientato) privo di cicli (circuiti) e tale che il grafo ottenuto trascurando la orientazione degli archi sia fortemente connesso. Un tale digrafo quindi non presenta cappi e, dati due suoi nodi, risulta possibile passare dall'uno all'altro muovendosi sui suoi archi nel loro senso o nel senso opposto.
Proprietà[modifica | modifica wikitesto]
Denotiamo con DAC l'insieme dei digrafi aciclici connessi e prendiamo in considerazione i seguenti suoi sottoinsiemi
- AE insieme delle arborescenze elementari;
- DB insieme dei digrafi bipartiti;
- A insieme delle arborescenze (o alberi muniti di radice);
- DGC insieme dei digrafi graduati connessi resi intransitivi e antiriflessivi.
Valgono le seguenti relazioni insiemistiche
Abbreviamo poi il termine "digrafo aciclico connesso" e il suo plurale con dac, in modo che si possa scrivere DAC = {dac}; similmente conveniamo che DGC = {dgc} ecc.
Se p, q e r denotano nodi di un digrafo D in DAC e se in tale D si trova l'arco (p,q) diciamo che q dipende direttamente da p; se si trova in D un cammino da p a r diciamo che r dipende da p (senza precisare se dipende direttamente o indirettamente).
In DAC - DGC si trovano digrafi con terne di nodi distinti (p,q,r) tali che sia q che r dipendono direttamente da p, mentre r dipende (direttamente o indirettamente) da q.
Come per i digrafi graduati conviene raffigurare i digrafi aciclici connessi in modo che un nodo si trovi più in basso dei nodi dai quali dipende.
Applicazioni[modifica | modifica wikitesto]
I digrafi aciclici connessi innanzi tutto, di rappresentare sistemi di distribuzione di merci con i nodi in alto che riforniscono i nodi loro dipendenti. Quasi equivalentemente: consentono di rappresentare sistemi di decisione con i nodi in alto che impartiscono ordini ai nodi loro dipendenti.[Cosa si intende?]
I digrafi aciclici connessi consentono poi di schematizzare collezioni di insiemi tra i quali esistono relazioni di inclusione compatibili con le relazioni di dipendenza, nel senso che se l'insieme Q dipende dall'insieme P deve essere un sottoinsieme di P; tra i sottoinsiemi di P solo una parte è rappresentata da nodi del digrafo, tutti questi sono dipendenti di P, ma in genere solo una parte di essi dipende direttamente da P. Gli insiemi che corrispondono a nodi del digrafo sono da pensare privilegiati in quanto solo su di essi si possono compiere determinate operazioni che possono configurarsi come operazioni di accesso; una relazione di dipendenza corrispondente alla presenza di un arco (p,q) nel digrafo dice che si ha la possibilità di collegare l'operazione di accesso a q all'operazione di accesso a p. Questi digrafi dunque riguardano non solo i sottinsiemi di un dato ambiente (per questo si dispone di un reticolo booleano, che sostanzialmente è un digrafo graduato), ma anche certe operazioni "di accesso" che si possono effettuare su di essi combinandole opportunamente.
Una applicazione più ricca della precedente riguarda la schematizzazione di categorie di contenitori di informazioni (insiemi di stringhe) o di contenitori di conoscenze (insiemi di documenti). In questo caso gli insiemi che corrispondono ai nodi di un digrafo aciclico connesso non sono considerati solo come collezioni di elementi, ma contenitori per i quali può risultare problematica la assegnazione delle stringhe o dei documenti (le entità dalle quali si deve partire per costruire il digrafo). Digrafi di questo genere si possono chiamare digrafi di categorizzazione.
In un digrafo aciclico connesso si possono individuare sottodigrafi di tipi particolari: AE, DB, A, DGC, ecc. In un digrafo di categorizzazione questi sottosistemi di categorie possono riguardare importanti operazioni di organizzazione dei documenti (in una biblioteca) e di organizzazione delle conoscenze (in una enciclopedia). Il grafico di una arborescenza elementare può aiutare a capire la ripartizione di un elenco di nuotatori in sottoelenchi di nuotatori africani, americani, asiatici, europei e oceanici. Se poi si vuole distinguere fra liberisti, dorsisti, delfinisti, farfallisti, mististi ecc. si ottiene una arborescenza a due livelli. Situazioni di ripartizione delle informazioni o delle conoscenze secondo più punti di vista (ad es. punti di vista di diverse discipline) portano a digrafi che non possono ridursi ad arborescenze (la categoria dei Termodinamici può dipendere dalla categoria Fisici e dalla categoria Chimici, ...).
