Multigráf

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

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), 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.

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, míg mások az ilyen gráfokat pszeudográfnak nevezik, fenntartva a multigráf nevet a hurokmentes esetekre.

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,
• $s:A\rightarrow V$, minden élt a forrás csúcshoz rendel,
• $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 $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
• $\Sigma _{V}$ és $\Sigma _{A}$ véges ábécék a lehetséges csúcs-, illetve irányítottél-címkékkel,
• $s\colon A\rightarrow \ V$ és $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,
• $\ell _{V}\colon V\rightarrow \Sigma _{V}$ és $\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.

Jegyzetek

• Graph Theory. McGraw-Hill (1997). ISBN 0-07-005489-4 
• Modern Graph Theory, Graduate Texts in Mathematics. Springer (2002). ISBN 0-387-98488-7 
• A First Course in Graph Theory. Dover (2012). ISBN 978-0-486-48368-9 
• Graph Theory, 4th, Graduate Texts in Mathematics, Springer (2010). ISBN 978-3-642-14278-9 
• Graph Theory and Its Applications. CRC Press (1998). ISBN 0-8493-3982-0 
• Handbook of Graph Theory. CRC (2003). ISBN 1-58488-090-2 
• Graph Theory. Addison Wesley (1995). ISBN 0-201-41033-8 
• (1993) „The birth of the giant component”. Random Structures and Algorithms 4 (3), 231–358. o. DOI:10.1002/rsa.3240040303. ISSN 1042-9832.  
• Graphs, Colourings and the Four-Colour Theorem. Oxford Science Publ. (2002). ISBN 0-19-851062-4 
• CRC Standard Mathematical Tables and Formulae, 31st, Chapman & Hall/CRC (2002). ISBN 1-58488-291-3 

További információk

• Ez a szócikk a NIST Paul E. Black által szerkesztett Dictionary of Algorithms and Data Structures közkincs művének részleteit tartalmazza.