Multigráf

A matematika, azon belül a gráfelmélet területén egy multigráf (ellentétben az egyszerű gráffal) olyan gráf, amiben létezhet többszörös él (más néven párhuzamos él^[1]), tehát olyan él, aminek ugyanazok a végpontjaik. Más szóval két csúcs egynél több éllel lehet összekötve.

Multigráf többszörös élekkel (piros) és hurokélekkel (kék). A multigráfok nem minden szerző szerint tartalmazhatnak hurkokat.

A „többszörös él” két különböző fogalmat takarhat:

• Saját identitás nélküli élek: egy élt kizárólag a két csúcs határoz meg, amit összeköt, az egyes élek nincsenek megkülönböztetve. Ebben az esetben a „többszörös él” azt jelenti, hogy ugyanaz az él több példányban megjelenik a két csúcs között.
• Saját identitással rendelkező élek: az élek primitív entitások, akárcsak a csúcsok. Ha két csúcs között több él van, azok egymástól megkülönböztetett élek.

A multigráf nem összetévesztendő a hipergráffal, ahol egy él kettőnél több csúcsot is összeköthet.

Egyes szerzőknél a pszeudográf a multigráf szinonimája. Más szerzőknél a pszeudográf olyan multigráf, melyben a hurokélek is megengedettek.

Irányítatlan multigráf (saját identitás nélküli élek)

Egy G multigráf egy G:=(V, E) rendezett pár, ahol

• V a csúcsok halmaza,
• E a csúcsok rendezetlen párjainak, az éleknek multihalmaza.

Irányítatlan multigráf (saját identitással rendelkező élek)

Egy G multigráf egy G:=(V, E, r) rendezett hármas, ahol

• V a csúcsok halmaza,
• E az élek halmaza,
• r : E → {{x,y} : x, y ∈ V}, minden élt a végponti csúcsok rendezetlen párosához rendel.

Egyes szerzők megengedik a hurokéleket, tehát egy csúcsot saját magával összekötő éleket,^[2] míg mások az ilyen gráfokat pszeudográfnak nevezik, fenntartva a multigráf nevet a hurokmentes esetekre.^[3]

Irányított multigráf (saját identitás nélküli élek)

Egy irányított multigráf vagy multifigráf olyan irányított gráf melyben létezhetnek többszörös irányított élek, tehát azonos forrással és nyelővel rendelkező élek. Egy G irányított multigráf a G:=(V,A) rendezett pár, ahol

• V a csúcsok halmaza,
• A az irányított éleknek vagy nyilaknak nevezett rendezett csúcspárok multihalmaza.

Egy G:=(V,E, A) vegyes multigráf hasonlóan definiálható, mint egy vegyes gráf.

Irányított multigráf (saját identitással rendelkező élek)

Egy G irányított multigráf vagy tegez olyan G:=(V, A, s, t) rendezett négyes, ahol

• V a csúcsok halmaza,
• A az élek halmaza,
• ${\displaystyle s:A\rightarrow V}$, minden élt a forrás csúcshoz rendel,
• ${\displaystyle t:A\rightarrow V}$, minden élt a nyelő csúcshoz rendel.

Ez a fogalom például felhasználható egy légitársaság által nyújtott lehetséges repülőút-kapcsolatok modellezésére. Ekkor a multigráf olyan irányított gráf, melyben a városokat összekötő párhuzamos irányított élek megmutatnák, hogy az egyes desztinációkba és onnan visszafelé is lehetséges utazni.

A kategóriaelmélet szerint a saját identitású élekkel rendelkező irányított bármely multigráf egy kis kategóriát alkot, ahol a csúcsok az objektumok, a multigráf élei morfizmusok, a kompozíció itt az irányított élek (nyílfolytonos) egymás után fűzése (konkatenációja), minden csúcs esetében a hurokél jelenti a kompozíció bal- és jobbidentitását. A kategóriaelméletben ezért a gráf kifejezés alatt rendszerint irányított multigráf értendő, és a kategória alap-irányított multigráfját csak alap-irányított gráfnak nevezik.

Címkézés

A multigráfok és irányított multigráfok teljesen hasonló módon címkézhetők, a terminológia azonban nem egységes.

A címkézett irányított gráf definíciója:

1. definíció: egy címkézett irányított gráf egy címkézett gráf, címkézett irányított élekkel.

Formálisan: Egy G címkézett irányított gráf multigráf címkézett csúcsokkal és irányított élekkel. Formálisan egy ${\displaystyle G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})}$ rendezett nyolcas, ahol

• V a csúcsok halmaza, A az irányított élek halmaza
• ${\displaystyle \Sigma _{V}}$ és ${\displaystyle \Sigma _{A}}$ véges ábécék a lehetséges csúcs-, illetve irányítottél-címkékkel,
• ${\displaystyle s\colon A\rightarrow \ V}$ és ${\displaystyle t\colon A\rightarrow \ V}$ két hozzárendelés, amik meghatározzák az egyes irányított élek forrását és nyelőjét,
• ${\displaystyle \ell _{V}\colon V\rightarrow \Sigma _{V}}$ és ${\displaystyle \ell _{A}\colon A\rightarrow \Sigma _{A}}$ két hozzárendelés, amik meghatározzák a csúcsok és az irányított élek címkéit.

2. definíció: Egy címkézett irányított multigráf olyan címkézett gráf, melyben a többszörös címkézett irányított élek esetében ha két irányított él kezdőpontja és végpontja megegyezik, akkor a címkéjük is.

Kapcsolódó szócikkek

• Irányított gráf

Fordítás

• Ez a szócikk részben vagy egészben a Multigraph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.