Pluridigrafo

In matematica e in particolare in teoria dei grafi, per pluridigrafo si intende una struttura che può considerarsi costituita da una famiglia di digrafi costruiti sopra un unico insieme di nodi.

Definizioni

Formalmente definiamo pluridigrafo una struttura relazionale della forma

$P=\langle Q,A,\tau \rangle$

dove Q è un insieme finito chiamato insieme dei nodi di P, A è un insieme finito chiamato alfabeto di P e $\tau :Q\times A\mapsto {\mathcal {B}}(Q)$ viene chiamata relazione di transizione di P; qui con ${\mathcal {B}}(Q)$ abbiamo denotato il booleano di Q, cioè l'insieme delle parti di Q, ovvero la collezione dei sottoinsiemi di Q.

Gli elementi di A in genere sono oggetti semplici e vengono chiamate lettere; per il loro numero scriviamo n := |A|. A ciascuna a di tali lettere è associata la relazione entro Q costituita dalle coppie di nodi per la quale scriviamo, utilizzando la notazione costruttiva delle relazioni

$a^{\tau }:=(|q\in Q\mapsto \tau (a,q)|)$.

Si osserva che ogni coppia $\,\langle Q,a^{\tau }\rangle$ individua un digrafo: quindi ad ogni pluridigrafo è associata una famiglia di digrafi. Questa associazione è una corrispondenza biunivoca e ad ogni famiglia di digrafi sopra un dato insieme di nodi Q si associa un pluridigrafo.

Osservazioni su termini e notazioni

Si deve osservare che il termine pluridigrafo non è utilizzato molto comunemente ed ha varie alternative: sembra però opportuno per ragioni di chiarezza complessiva fare preciso riferimento a questo termine e ad altri presenti tra le Voci correlate; per le stesse ragioni risulta vantaggioso servirsi di notazioni come quelle introdotte nel paragrafo che segue.

Come sinonimo di pluridigrafo si usa anche il termine di semiautoma nondeterministico (a stati finiti). Nel caso particolare nel quale tutte le relazioni associate agli elementi dell'alfabeto sono funzioni si parla di semiautoma deterministico. Questa specie di struttura relazionale è basilare per le trattazioni formali degli automi.

Plurigrafi e monoidi

Considerando le n:=|A| relazioni entro Q derivate dal pluridigrafo P e le loro composizioni si individua un semigruppo di relazioni; più precisamente diciamo semigruppo associato al pluridigrafo P il sottogruppo generato dalle relazioni $a^{\tau }$. Se si considera anche la relazione d'identità dell'insieme Q si ottiene un monoide, il monoide associato al pluridigrafo P che denotiamo con Mnd(P); questo evidentemente è finito, in quanto è contenuto nel monoide delle relazioni dell'insieme Q che denotiamo MndRel(Q), struttura che, posto $m\,:=\,|Q|$, ha cardinalità $\,2^{m\times m}$.

La applicazione che ad ogni stringa su A associa una relazione entro Q è un morfismo di A^*, il monoide libero sull'alfabeto A, nel monoide delle relazioni entro Q. Indichiamo questa applicazione Mrph(P). Le classi di equivalenza dell'insieme delle stringhe A^* corrispondenti alla funzione Mrph(P) (v. equivalenza associata a una funzione) sono classi di congruenza per la operazione binaria di giustapposizione di stringhe (v. congruenza associata a un'operazione binaria). Questa congruenza della specie di struttura dei monoidi si dice congruenza di Myhill del pluridigrafo P e la denotiamo con Cngr(P).

Le entità denotate Mnd(P), Mrph(P) e Cngr(P) consentono di avviare lo studio algebrico dei multidigrafi che è alla base dello studio algebrico degli automi a stati finiti (v. Teoria di Krohn-Rhodes).

Il collegamento fra multidigrafi e semigruppi si chiarisce ulteriormente osservando che ad un monoide finito (M,·) si può associare il pluridigrafo (M,M,τ) nel quale la relazione di transizione si riduce alla semplice funzione definita mediante il prodotto del monoide:

$p^{\tau }:=(|q\in M\mapsto q\cdot p|)$ .

Voci correlate

• Digrafo
• Grafo arricchito
  • Multidigrafo
  • Plurigrafo
  • Multigrafo
• Semigruppo