Pluridigrafo

Da Wikipedia, l'enciclopedia libera.

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 ad un unico insieme di vertici.

Indice

1 Definizioni
2 Osservazioni su termini e notazioni
3 Plurigrafi e monoidi
4 Voci correlate

[modifica] Definizioni

Formalmente definiamo pluridigrafo una struttura relazionale della forma

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

dove Q è un insieme finito chiamato insieme dei vertici 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 (con $\mathcal{B}(Q)$ abbiamo denotato il booleano di Q, l'insieme delle parti di Q, la collezione dei sottoinsiemi dei nodi).

Gli elementi di A in genere sono oggetti semplici e vengono chiamate lettere; per il loro numero scriviamo n := |A|. Per ciascuna a di tali lettere si individua la relazione entro Q costituita dalle coppie di vertici 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 vertici Q si associa un pluridigrafo.

[modifica] 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.

[modifica] 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 τ$ . Se si considera anche la relazione identità dell'insieme Q si ottiene un monoide, il monoide associato al pluridigrafo P che indichiamo Mnd(P); questo evidentemente è finito, in quando contenuto nel monoide delle relazioni dell'insieme Q che denotiamo MndRel(Q).

La applicazione che ad ogni stringa su A associa una relazione entro Q è un morfismo di A^*, il monoide libero su 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 una operazione binaria). Questa congruenza della specie di struttura dei monoidi si dice congruenza di Myhill del pluridigrafo P e la denotiamo 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 |)$ .