Multigráf
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Multi-pseudograph.svg/220px-Multi-pseudograph.svg.png)
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.
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,
- , minden élt a forrás csúcshoz rendel,
- , 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 rendezett nyolcas, ahol
- V a csúcsok halmaza, A az irányított élek halmaza
- és véges ábécék a lehetséges csúcs-, illetve irányítottél-címkékkel,
- és két hozzárendelés, amik meghatározzák az egyes irányított élek forrását és nyelőjét,
- és 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
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