Az irányított és irányítatlan grafikon közötti különbség

Irányított vs iránytalan gráf

A grafikon egy matematikai struktúra, amely csúcsok és élek halmazából áll. A grafikon olyan objektumok halmazát képviseli (csúcsok képviselik), amelyek egyes linkeken keresztül kapcsolódnak (élek képviselik). Matematikai jelölések felhasználásával egy gráfot G-vel ábrázolhatjuk, ahol G = (V, E) és V a csúcsok halmaza, E pedig az élek halmaza. Egy irányítatlan gráfban a csúcsokat összekötő élekhez nem tartozik irány. Egy irányított gráfban van egy olyan irány, amely a csúcsokat összekötő élekhez kapcsolódik.

Irányítatlan grafikon

Mint korábban említettük, a nem irányított gráf olyan grafikon, amelyben nincs olyan irány az élekben, amelyek a gráf csúcsait összekötik. Az 1. ábra egy irányítatlan gráfot ábrázol, amelynek csúcsai V = V1, V2, V3. A fenti grafikon éleinek halmaza V = (V1, V2), (V2, V3), (V1, V3) lehet. Azt is meg kell jegyezni, hogy semmi sem akadályozza meg az élek halmazának V = (V2, V1), (V3, V2), (V3, V1) írását, mivel az éleknek nincs iránya. Ezért az irányítatlan gráf élei nem rendeződnek párokba. Ez a nem irányított gráf fő jellemzője. Az irányítatlan gráfok felhasználhatók a csúcsok által ábrázolt objektumok közötti szimmetrikus kapcsolatok ábrázolására. Például egy kétirányú úthálózat, amely összeköti a városok halmazát, irányítatlan gráf segítségével ábrázolható. A városokat ábrázolhatjuk a grafikon csúcsaival, az élek pedig a városokat összekötő kétirányú utakkal.

Irányított grafikon

Az irányított gráf egy olyan grafikon, amelyben a csúcsokat összekötő éleknek iránya van. A 2. ábra egy irányított gráfot ábrázol, amelynek csúcsai V = V1, V2, V3. A fenti grafikon éleinek halmaza V = (V1, V2), (V2, V3), (V1, V3) lehet. A nem irányított gráf szélét párba rendezzük. Formálisan az e szél egy irányított gráfban az e = (x, y) rendezett párral reprezentálható, ahol x a csúcs, amelyet e szél eredetének, forrásának vagy kiindulási pontjának nevezünk, és y csúcsot terminálnak nevezünk. , csúcspont vagy végpont. Például egy úthálózat, amely a városok halmazát egyirányú utakkal köti össze, átirányíthatatlan grafikon segítségével ábrázolható. A városokat ábrázolhatjuk a grafikonban lévő csúcsokkal, és az irányított élek jelzik az utak, amelyek összekötik a városokat, figyelembe véve azt az irányt, amelyben a forgalom az útban folyik.

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 rendezett pár, ahol a rendezett pár a két csúcsot összekötő él irányát jelöli. Másrészről, egy irányítatlan gráfban az él rendezetlen pár, mivel nincs egy élhez rendelt irány. Az irányítatlan gráfok felhasználhatók az objektumok közötti szimmetrikus kapcsolatok ábrázolására. Az egyes csomópontok fokozatlan és túllépési foka egy irányítatlan gráfban egyenlő, de ez nem igaz egy irányított gráfra. Ha egy mátrixot használ egy irányítatlan gráf ábrázolására, akkor a mátrix mindig szimmetrikus gráfvá válik, de ez nem igaz egy irányított gráfra. Az irányítatlan gráfot átalakíthatjuk irányított gráfká, ha minden élt kicserélünk két, egymással ellentétes irányba eső irányra. Ugyanakkor nem lehet konvertálni egy irányított gráfot nem irányított gráfdá.