Multigraf
În matematică, mai exact în teoria grafurilor, un multigraf este un graf căruia i se permite să aibă muchii multiple[1][2][3] (numite și muchii paralele[2][3]), adică muchii care au aceleași noduri la capete. Astfel, două noduri pot fi conectate prin mai mult de o muchie.
Există două noțiuni distincte de margini multiple:
- Muchii fără identitate proprie: Identitatea unei muchii este definită numai de cele două noduri pe care le conectează. În acest caz, termenul „muchii multiple” înseamnă că aceeași muchie poate apărea de mai multe ori între aceste două noduri.
- Muchii cu identitate proprie: Muchiile sunt entități primitive la fel ca nodurile. Când mai multe muchii conectează două noduri, acestea sunt muchii diferite.
Un multigraf este diferit de un hipergraf, care este un graf în care o muchie poate conecta orice număr de noduri, nu doar două.
Pentru unii autori termenii „pseudograf” și „multigraf” sunt sinonime. Pentru alții, un pseudograf este un multigraf căruia i se permite să aibă bucle.
Notă: DEX conține o definiție care corespunde unei alte noțiuni decât cea care face subiectul articolului.[4] (Însă eliminând particula „nu” din definiție se obține o definiție similară noțiunii de aici, ceea ce suspectează o greșeală în MDN 2000.)
Multigrafuri neorientate (muchii fără identitate proprie)
[modificare | modificare sursă]Un multigraf G este o pereche ordonată G := (V, E) cu
- V o mulțime de noduri,
- E o multimulțime de perechi neordonate de noduri, numite muchii.
Multigrafuri neorientate (muchii cu identitate proprie)
[modificare | modificare sursă]Un multigraf G este un 3-tuplu(d) G := (V, E, r) cu
- V o mulțime de noduri,
- E o multimulțime de muchii.
- r : E → {{x,y} : x, y ∈ V}, atribuind fiecărei muchii la capete o pereche neordonată de noduri.
Unii autori permit multigrafurilor să aibă bucle, adică o muchie care conectează un vârf la sine însuși,[1][5][6] în timp ce alții le numesc pe acestea „pseudografuri”, rezervând termenul multigraf pentru cazul fără bucle.[3][7] Alții[1] folosesc aceste denumiri invers, numind „pseudografuri” multigrafurile fără bucle.
Multigrafuri orientate (muchii fără identitate proprie)
[modificare | modificare sursă]Un multigraf orientat (multidigraf) este un graf orientat căruia i se permite să aibă arce multiple, adică arce cu aceleași noduri sursă și destinație. Un multidigraf G este o pereche ordonată G := (V, A) cu
- V o mulțime de noduri,
- A o multimulțime de perechi ordonate de noduri, numite muchii orientate, arce sau săgeți.
Un multigraf mixt G := (V, E, A) poate fi definit la fel cu un graf mixt(d).
Multigrafuri orientate (muchii cu identitate proprie)
[modificare | modificare sursă]Un multidigraf tolbă(d) G este un 4-tuplu G := (V, A, s, t) cu
- V o mulțime de noduri,
- A o mulțime de muchii.
- , atribuirea fiecărei muchii nodul său sursă,
- , atribuirea fiecărei muchii nodul său destinație.
Această noțiune ar putea fi folosită pentru a modela posibilele conexiuni de zboruri oferite de o companie aeriană. În acest caz, multigraful ar fi un graf orientat cu perechi de laturi paralele orientate care leagă orașe pentru a arăta că este posibil să se zboare atât la cât și de la aceste destinații.
În teoria categoriilor, o categorie mică poate fi definită ca un multidigraf (cu muchii având identitate proprie) echipat cu o lege de compoziție asociativă și o buclă distinctă în fiecare nod care servește pentru compunere ca element neutru la stânga și la dreapta. Din acest motiv, în teoria categoriilor, termenul graf este în mod standard considerat multidigraf, iar multidigraful de bază al unei categorii este numit digraful suport[1] al acesteia.
Etichetare
[modificare | modificare sursă]Multigrafurile și multidigrafurile admit noțiunea de etichetare a unui graf, într-un mod similar cu etighetarea grafurilor. Totuși, nu există o unitate în terminologie.
Note
[modificare | modificare sursă]- ^ a b c d Mircea Marin, Combinatorică și Teoria Grafurilor, Timișoara, Editura UVT, 2021, ISBN: 978-973-125-829-4, cap 2.1 Vocabularul teoriei grafurilor, p. 108
- ^ a b en Balakrishnan, V. K. (). Graph Theory. McGraw-Hill. p. 1. ISBN 0-07-005489-4.
- ^ a b c en Chartrand, Gary; Zhang, Ping (). A First Course in Graph Theory. Dover. p. 26. ISBN 978-0-486-48368-9.
- ^ „multigraf” la DEX online
- ^ en Bollobás, Béla (). Modern Graph Theory. Graduate Texts in Mathematics. 184. Springer. p. 7. ISBN 0-387-98488-7.
- ^ en Diestel, Reinhard (). Graph Theory. Graduate Texts in Mathematics. 173 (ed. 4th). Springer. p. 28. ISBN 978-3-642-14278-9.
- ^ en Wilson, Robert A. (). Graphs, Colourings and the Four-Colour Theorem. Oxford Science Publ. p. 6. ISBN 0-19-851062-4.
Bibliografie
[modificare | modificare sursă]- en Gross, Jonathan L.; Yellen, Jay (). Graph Theory and Its Applications. CRC Press. ISBN 0-8493-3982-0.
- en Gross, Jonathan L.; Yellen, Jay, ed. (). Handbook of Graph Theory. CRC Press. ISBN 1-58488-090-2.
- en Harary, Frank (). Graph Theory. Addison Wesley. ISBN 0-201-41033-8.
- en Janson, Svante; Knuth, Donald E.; Luczak, Tomasz; Pittel, Boris (). „The birth of the giant component”. Random Structures and Algorithms. 4 (3): 231–358. arXiv:math/9310236
. Bibcode:1993math.....10236J. doi:10.1002/rsa.3240040303. ISSN 1042-9832. MR 1220220.
