Pluridigraf

În matematică și în special în teoria graficelor , prin pluridigraf înțelegem o structură care poate fi considerată constituită dintr-o familie de digrame construite pe un singur set de noduri .

Definiții

În mod formal, definim un pluridigraf ca o structură relațională de formă

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

{\ displaystyle P = \ langle Q, A, \ tau \ rangle}

{\ displaystyle P = \ langle Q, A, \ tau \ rangle}

unde Q este o mulțime finită numită mulțimea nodului lui P , A este o mulțime finită numită alfabetul lui P și $\tau :Q\times A\mapsto {\mathcal {B}}(Q)$ ${\ displaystyle \ tau: Q \ times A \ mapsto {\ mathcal {B}} (Q)}$ ${\ displaystyle \ tau: Q \ times A \ mapsto {\ mathcal {B}} (Q)}$ se numește relația de tranziție a lui P ; aici cu ${\mathcal {B}}(Q)$ ${\ displaystyle {\ mathcal {B}} (Q)}$ ${\ displaystyle {\ mathcal {B}} (Q)}$ am notat booleanul lui Q , adică ansamblul părților lui Q , adică colecția de subseturi de Q.

Elementele lui A sunt în general obiecte simple și se numesc litere ; pentru numărul lor scriem n : = | A |. Pentru fiecare dintre aceste scrisori o este asociată relația în cadrul Q constituit de către perechile de noduri pentru care scrie, folosind notația constructivă a relațiilor

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

{\ displaystyle a ^ {\ tau}: = (| q \ în Q \ mapsto \ tau (a, q) |)}

{\ displaystyle a ^ {\ tau}: = (| q \ în Q \ mapsto \ tau (a, q) |)}

.

Se observă că fiecare pereche $\,\langle Q,a^{\tau }\rangle$ ${\ displaystyle \, \ langle Q, a ^ {\ tau} \ rangle}$ ${\ displaystyle \, \ langle Q, a ^ {\ tau} \ rangle}$ identifică un digraf: prin urmare, o familie de digrame este asociată cu fiecare pluridigraf. Această asociație este o corespondență unu-la-unu și fiecare familie de digrame pe un set dat de noduri Q este asociată cu un grafograf.

Observații cu privire la termeni și notații

Trebuie remarcat faptul că termenul pluridigraf nu este folosit foarte frecvent și are diverse alternative: pare adecvat, totuși, din motive de claritate generală, să se facă referire precisă la acest termen și la alții prezenți printre elementele conexe ; din aceleași motive este avantajos să folosiți notații precum cele introduse în paragraful următor.

Termenul nedeterminist (stare finită) semiautom este, de asemenea, utilizat ca sinonim pentru pluridigraf. În cazul particular în care toate relațiile asociate cu elementele alfabetului sunt funcții, vorbim despre un semiautom determinist . Acest tip de structură relațională este fundamentală pentru tratamentul formal al automatelor .

Plurigrafele și monoizii

Având în vedere n : = | A | relațiile din cadrul Q derivate din pluridigraful P și compozițiile lor, se identifică un semigrup de relații; mai exact spunem semigrup asociat pluridigrafului P subgrupul generat de relații $a^{\tau }$ ${\ displaystyle a ^ {\ tau}}$ ${\ displaystyle a ^ {\ tau}}$ . Dacă luăm în considerare și relația de identitate a mulțimii Q obținem un monoid , monoidul asociat cu pluridigraful P pe care îl notăm cu Mnd (P); acest lucru este evident finit, întrucât este cuprins în monoidul relațiilor mulțimii Q pe care o denotăm MndRel (Q), o structură care, dată fiind $m\,:=\,|Q|$ ${\ displaystyle m \ ,: = \, | Q |}$ ${\ displaystyle m \ ,: = \, | Q |}$ , are cardinalitate $\,2^{m\times m}$ ${\ displaystyle \, 2 ^ {m \ ori m}}$ ${\ displaystyle \, 2 ^ {m \ ori m}}$ .

Aplicația care pentru fiecare șir de pe A asociază o relație în cadrul Q este un morfism al lui A ^* , monoidul liber de pe alfabetul A , în monoidul relațiilor din Q. Denotăm această cerere Mrph ( P ). Clasele de echivalență ale setului de șiruri A ^* corespunzătoare funcției Mrph ( P ) (vezi echivalența asociată cu o funcție ) sunt clase de congruență pentru operația binară de juxtapunere a șirurilor (vezi congruența asociată cu o operație binară ). Această congruență a speciilor de structură monoidă se numește congruența Myhill a pluridigrafului P și o denotăm cu Cngr (P).

Entitățile notate Mnd (P), Mrph (P) și Cngr (P) permit să înceapă studiul algebric al multidigrafelor care este baza studiului algebric al automatelor de stare finită (vezi teoria Krohn-Rhodes ).

Conexiunea dintre multidigrafe și semigrupuri este clarificată în continuare prin observarea că un monoid finit (M, ·) poate fi asociat cu multidigraful (M, M, τ) în care relația de tranziție este redusă la funcția simplă definită de produsul monoid:

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

{\ displaystyle p ^ {\ tau}: = (| q \ în M \ mapsto q \ cdot p |)}

{\ displaystyle p ^ {\ tau}: = (| q \ în M \ mapsto q \ cdot p |)}

.

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică