Multigráf

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
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[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)[szerkesztés]

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

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

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, yV}, 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)[szerkesztés]

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)[szerkesztés]

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[szerkeszté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[szerkesztés]

Fordítás[szerkeszté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.

Jegyzetek[szerkesztés]

  1. For example, see Balakrishnan 1997, p. 1 or Chartrand and Zhang 2012, p. 26.
  2. For example, see Bollobás 2002, p. 7 or Diestel 2010, p. 28.
  3. Lásd például Wilson 2002, p. 6 vagy Chartrand and Zhang 2012, pp. 26-27.

További információk[szerkesztés]