Irányított vs irányítatlan gráf
A gráf egy matematikai struktúra, amely csúcsok és élek halmazából áll. A gráf olyan objektumok halmazát ábrázolja (amelyeket csúcsok ábrázolnak), amelyek bizonyos hivatkozásokon keresztül kapcsolódnak egymáshoz (élekkel ábrázolva). Matematikai jelölésekkel egy gráfot ábrázolhatunk G-vel, ahol G=(V, E) és V a csúcsok halmaza, E pedig az élek halmaza. Egy irányítatlan gráfban nincs irány társítva a csúcsokat összekötő élekhez. Egy irányított gráfban a csúcsokat összekötő élekhez egy irány tartozik.
Irányítatlan grafikon
Amint korábban említettük, az irányítatlan gráf olyan gráf, amelyben nincs irány a gráf csúcsait összekötő élekben. Az 1. ábra egy irányítatlan gráfot ábrázol V={V1, V2, V3} csúcsokkal. A fenti gráf éleinek halmaza a következőképpen írható fel: V={(V1, V2), (V2, V3), (V1, V3)}. Azt is megjegyezhetjük, hogy semmi akadálya annak, hogy az élhalmazt V={(V2, V1), (V3, V2), (V3, V1)} alakban írjuk, mivel az éleknek nincs irányuk. Ezért egy irányítatlan gráf élei nem rendezett párok. Ez az irányítatlan gráf fő jellemzője. Irányítatlan gráfok használhatók a csúcsokkal ábrázolt objektumok közötti szimmetrikus kapcsolatok ábrázolására. Például egy kétirányú úthálózat, amely városokat köt össze, irányítatlan gráf segítségével ábrázolható. A városok a gráf csúcsaival ábrázolhatók, az élek pedig a kétirányú utakat, amelyek összekötik a városokat.
Irányított grafikon
Az irányított gráf olyan gráf, amelyben a gráf csúcsait összekötő éleinek iránya van. A 2. ábra egy irányított gráfot ábrázol V={V1, V2, V3} csúcsokkal. A fenti gráf éleinek halmaza a következőképpen írható fel: V={(V1, V2), (V2, V3), (V1, V3)}. Az irányítatlan gráf élei rendezett párok. Formálisan az e él egy irányított gráfban az e=(x, y) rendezett párral ábrázolható, ahol x az a csúcs, amelyet az e él origójának, forrásának vagy kezdőpontjának, az y csúcsot pedig végpontnak nevezzük., lezáró csúcs vagy végpont. Például egy úthálózat, amely városokat egyirányú utakon köt össze, irányítatlan gráf segítségével ábrázolható. A városok a gráf csúcsaival ábrázolhatók, az irányított élek pedig azokat az utakat, amelyek a városokat összekötik, figyelembe véve, hogy milyen irányban halad a forgalom az úton.
Mi a különbség az irányított gráf és az irányítatlan gráf között?
Egy irányított gráfban az él egy rendezett pár, ahol a rendezett pár a két csúcsot összekötő él irányát jelöli. Másrészt egy irányítatlan gráfban az él egy rendezetlen pár, mivel az élhez nincs irány társítva. Irányítatlan gráfok használhatók az objektumok közötti szimmetrikus kapcsolatok ábrázolására. Az irányítatlan gráf minden csomópontjának be- és kilépési foka egyenlő, de ez nem igaz irányított gráfra. Ha mátrixot használunk egy irányítatlan gráf ábrázolására, a mátrix mindig szimmetrikus gráf lesz, de ez nem igaz irányított gráfokra. Egy irányítatlan gráf irányított gráfrá alakítható, ha minden élt két, ellentétes irányú irányított élre cserélünk. Az irányított gráfot azonban nem lehet irányítatlan gráfrá alakítani.
