Grafik i drejtuar vs i padrejtuar
Një grafik është një strukturë matematikore që përbëhet nga një grup kulmesh dhe skajesh. Një grafik përfaqëson një grup objektesh (të përfaqësuara nga kulmet) që lidhen përmes disa lidhjeve (të përfaqësuara nga skajet). Duke përdorur shënime matematikore, një grafik mund të përfaqësohet me G, ku G=(V, E) dhe V është bashkësia e kulmeve dhe E është bashkësia e skajeve. Në një grafik të padrejtuar nuk ka drejtim të lidhur me skajet që lidhin kulmet. Në një grafik të drejtuar ka një drejtim të lidhur me skajet që lidhin kulmet.
Grafi i padrejtuar
Siç u përmend më herët, një graf i padrejtuar është një graf në të cilin nuk ka drejtim në skajet që lidhin kulmet në grafik. Figura 1 paraqet një graf të padrejtuar me grup kulmesh V={V1, V2, V3}. Seti i skajeve në grafikun e mësipërm mund të shkruhet si V={(V1, V2), (V2, V3), (V1, V3)}. Mund të vërehet gjithashtu se nuk ka asgjë që e pengon shkrimin e grupit të skajeve si V={(V2, V1), (V3, V2), (V3, V1)} pasi skajet nuk kanë drejtim. Prandaj, skajet në një graf të padrejtuar nuk janë çifte të renditura. Kjo është karakteristika kryesore e një grafi të padrejtuar. Grafikët e padrejtuar mund të përdoren për të përfaqësuar marrëdhëniet simetrike ndërmjet objekteve që përfaqësohen me kulme. Për shembull, një rrjet rrugor i dyanshëm që lidh një grup qytetesh mund të përfaqësohet duke përdorur një grafik të padrejtuar. Qytetet mund të përfaqësohen nga kulmet në grafik dhe skajet përfaqësojnë rrugët me dy drejtime që lidhin qytetet.
Grafiku i drejtuar
Grafik i drejtuar është një graf në të cilin skajet në grafik që lidhin kulmet kanë një drejtim. Figura 2 paraqet një grafik të drejtuar me grup kulmesh V={V1, V2, V3}. Seti i skajeve në grafikun e mësipërm mund të shkruhet si V={(V1, V2), (V2, V3), (V1, V3)}. Skajet në një graf të padrejtuar janë çifte të renditura. Formalisht, skaji e në një graf të drejtuar mund të përfaqësohet nga çifti i renditur e=(x, y) ku x është kulmi që quhet origjina, burimi ose pika fillestare e skajit e, dhe kulmi y quhet fundi., kulmi përfundimtar ose pika përfundimtare. Për shembull, një rrjet rrugor që lidh një grup qytetesh duke përdorur rrugë të njëanshme mund të përfaqësohet duke përdorur një grafik të padrejtuar. Qytetet mund të përfaqësohen nga kulmet në grafik dhe skajet e drejtuara paraqesin rrugët që lidhin qytetet duke marrë parasysh drejtimin që rrjedh trafiku në rrugë.
Cili është ndryshimi midis Grafikut të Drejtuar dhe Grafikut të Padrejtuar?
Në një graf të drejtuar një skaj është një çift i renditur, ku çifti i renditur përfaqëson drejtimin e skajit që lidh dy kulmet. Nga ana tjetër, në një grafik të padrejtuar, një skaj është një çift i parregulluar, pasi nuk ka drejtim të lidhur me një skaj. Grafikët e padrejtuar mund të përdoren për të përfaqësuar marrëdhëniet simetrike ndërmjet objekteve. Shkalla brenda dhe jashtë e secilës nyje në një graf të padrejtuar është e barabartë, por kjo nuk është e vërtetë për një graf të drejtuar. Kur përdoret një matricë për të përfaqësuar një graf të padrejtuar, matrica gjithmonë bëhet një graf simetrik, por kjo nuk është e vërtetë për një graf të drejtuar. Një graf i padrejtuar mund të konvertohet në një graf të drejtuar duke zëvendësuar çdo skaj me dy skaje të drejtuara që shkojnë në drejtim të kundërt. Megjithatë, nuk është e mundur të konvertohet një grafik i drejtuar në një grafik të padrejtuar.
