Multigraf

În teoria grafurilor, un multigraf (sau pseudograf ) este un graf care permite prezența mai multor muchii (sunt numite și „paralele” [1] ), adică muchii care au aceleași vârfuri de capăt . Astfel, două vârfuri pot fi conectate prin mai mult de o muchie (astfel, multigrafele diferă de hipergrafele , în care fiecare muchie poate conecta orice număr de vârfuri, nu exact două).

Există două moduri diferite de a eticheta marginile unui multigraf. Unii spun că, ca și în cazul graficelor fără muchii multiple, o muchie este definită de vârfurile pe care le conectează, dar fiecare muchie poate fi repetată de mai multe ori. Alții definesc muchiile ca elemente egale ale graficului cu vârfuri și trebuie să aibă propria lor identificare.

Multigrafe nedirecționate (muchii fără autoidentificare)

Formal, un multigraf G este o pereche ordonată G :=( V , E ) în care

V este mulțimea de vârfuri ,
E este un multiset de perechi neordonate de vârfuri. Elementele acestui set se numesc muchii .

Multigrafele pot fi folosite pentru a reprezenta posibilele căi de aer ale unei aeronave. În acest caz, multigraful devine orientat și o pereche de margini paralele orientate care leagă orașele arată că este posibil să zbori în ambele direcții - de la oraș sau la oraș.

Unii autori permit ca multigrafele să aibă bucle , adică muchii care conectează un vârf cu el însuși [2] , în timp ce alții numesc astfel de grafice pseudografe , lăsând termenul multigraf pentru graficele fără bucle [3] .

Multigrafe dirijate (muchii fără autoidentificare)

Un multidigraf este un grafic direcționat care permite mai multe arce , adică arce care au aceleași vârfuri de început și de sfârșit.

Un multidigraf G este o pereche ordonată G :=( V , A ) în care

V este mulțimea de vârfuri ,
A este un multiset de perechi ordonate de vârfuri. Elementele acestei mulțimi se numesc arce .

Un multigraf mixt G :=( V , E , A ) poate fi definit în același mod ca un grafic mixt .

Multigrafe dirijate (muchii cu autoidentificare)

Un multidigraf (sau tolbă ) G este un cvadruplu ordonat G :=( V , A , s , t ) în care

V este mulțimea de vârfuri ,
A este un set de arce ,
$s:A\rightarrow V$ atribuie fiecărui arc un vârf de început,
$t:A\rightarrow V$ atribuie fiecărui arc un vârf de capăt.

În teoria categoriilor, categoriile mici pot fi definite ca multidigrafe (cu arce având propria identitate) echipate cu o lege de construcție și bucle pentru fiecare vârf, servind drept identificare stânga și dreapta pentru construcție. Din aceste motive, în teoria categoriilor, termenul graf este de obicei înțeles ca un „multidigraf”, iar multidigraful de bază al unei categorii se numește digraf de bază .

Markup

Multigrafele și multidigrafele susțin noțiunea de etichetare în același mod, dar în acest caz nu există o unitate de terminologie.

Definițiile multigrafelor etichetate și ale multidigrafelor etichetate sunt similare, așa că aici oferim doar definiția unui multidigraf.

Definiția 1 : Un multidigraf etichetat este un grafic etichetat cu etichete pe arce și vârfuri.

Formal: Un multidigraf G etichetat este un tuplu de 8 elemente în care $G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})$

V este o mulțime de vârfuri și A este o mulțime de arce,
$\Sigma _{V}$ și este alfabetul final disponibil pentru etichetarea arcurilor și vârfurilor, $\Sigma _{A}$
$s\coloan A\rightarrow \ V$ și sunt două mapări care definesc vârfurile de început și de sfârșit ale arcului, $t\colon A\rightarrow \ V$
$\ell _{V}\colon V\rightarrow \Sigma _{V}$ și sunt două mapări care descriu etichetarea vârfurilor și arcelor. $\ell _{A}\colon A\rightarrow \Sigma _{A}$

Definiția 2 : Un multidigraf etichetat este un digraf etichetat cu mai multe arce etichetate , adică arce cu aceleași capete și aceleași etichete (acesta este diferit de conceptul dat în articolul „ Etichetare grafică ”).

Vezi și

Note

↑ De exemplu, vezi Balakrishnan, p. 1.
↑ De exemplu, vezi cărțile lui Bollobás, pagina 7, sau Diestel, pagina 25.
↑ Robert A. Wilson. Grafice, colorații și teorema celor patru culori. - 2002. - S. 6. - ISBN 0-19-851062-4 .

Link -uri

Bela Bollobas. Teoria modernă a grafurilor. - Springer, 2002. - ISBN 0-387-98488-7 .
VK Balakrishnan. teoria grafurilor. - McGraw-Hill, 1997. - ISBN 0-07-005489-4 .
Reinhard Distel. Teoria grafurilor. - Novosibirsk: Editura Institutului de Matematică, 2002. - ISBN 5-86134-101-X .
Jonathan L Gross, Jay Yellen. Teoria grafurilor și aplicațiile sale. - McGraw-Hill, 1998. - ISBN 0-8493-3982-0 .
Jonathan L Gross, Jay Yellen. Manual de teorie a grafurilor. - McGraw-Hill, 2003. - ISBN 1-58488-090-2 .
F. Harari. Teoria grafurilor. - Moscova: Editorial URSS, 2003. - ISBN 5-354-00301-6 .
Daniel Zwillinger. Tabele și formule matematice standard CRC. - Chapman & Hall/CRC, 2002. - ISBN 1-58488-291-3 .
Svante Janson, Donald E. Knuth, Tomasz Luczak, Boris Pittel. Nașterea componentei gigant // Structuri aleatoare și algoritmi. - 1993. - T. 4 , nr. 3 . - S. 231-358 . - doi : 10.1002/rsa.3240040303 .

Link- uri externe

Paul E. Black, Multigraph la Dicționarul NIST de algoritmi și structuri de date.