Бағытталған және бағытталмаған график
График – бұл төбелер мен жиектер жиынынан тұратын математикалық құрылым. График кейбір сілтемелер (жиектермен көрсетілген) арқылы қосылған объектілер жиынын (төбелермен көрсетілген) білдіреді. Математикалық белгілерді қолдана отырып, графикті G арқылы көрсетуге болады, мұнда G=(V, E) және V – төбелер жиыны, ал E – жиектер жиыны. Бағытталмаған графикте төбелерді қосатын жиектермен байланысты бағыт жоқ. Бағытталған графикте төбелерді қосатын жиектермен байланысты бағыт бар.
Бағытсыз график
Бұрын айтылғандай, бағытталмаған график – бұл графиктің төбелерін байланыстыратын жиектерінде ешқандай бағыт жоқ график.1-суретте V={V1, V2, V3} шыңдары жиыны бар бағытталмаған график бейнеленген. Жоғарыдағы графиктегі жиектер жиынын V={(V1, V2), (V2, V3), (V1, V3)} түрінде жазуға болады. Сондай-ақ, жиектер жиынын V={(V2, V1), (V3, V2), (V3, V1)} ретінде жазуға ешнәрсе кедергі келтірмейтінін атап өтуге болады, өйткені жиектерде бағыт жоқ. Сондықтан бағытталмаған графиктің жиектері реттелген жұптар емес. Бұл бағытталмаған графиктің негізгі сипаттамасы. Бағытталмаған графиктерді төбелермен берілген нысандар арасындағы симметриялық қатынастарды көрсету үшін пайдалануға болады. Мысалы, қалалар жиынтығын байланыстыратын екі жақты жол желісін бағытталмаған график арқылы көрсетуге болады. Қалаларды графиктегі шыңдармен, ал жиектерді қалаларды байланыстыратын екі жақты жолдарды көрсетуге болады.
Бағытталған график
Бағытталған график – графтың төбелерін байланыстыратын жиектерінің бағыты болатын график. 2-суретте V={V1, V2, V3} шыңдары жиыны бар бағытталған график бейнеленген. Жоғарыдағы графиктегі жиектер жиынын V={(V1, V2), (V2, V3), (V1, V3)} түрінде жазуға болады. Бағыты жоқ графиктің жиектері реттелген жұптар. Формальды түрде бағытталған графиктегі e шеті реттелген e=(x, y) жұбымен ұсынылуы мүмкін, мұнда x - е жиегінің басы, көзі немесе бастапқы нүктесі деп аталатын төбе, ал у төбесі - соңғы нүкте деп аталады., аяқталатын шың немесе терминал нүктесі. Мысалы, бір жақты жолдар арқылы қалалар жиынтығын байланыстыратын жол желісі бағытталмаған графиктің көмегімен ұсынылуы мүмкін. Қалаларды графикте шыңдармен көрсетуге болады, ал бағытталған жиектер жолдағы көлік қозғалысының бағытын ескере отырып, қалаларды байланыстыратын жолдарды білдіреді.
Бағытталған график пен бағытталмаған графиктің айырмашылығы неде?
Бағытталған графикте жиек реттелген жұп болып табылады, мұнда реттелген жұп екі шыңды байланыстыратын жиектің бағытын білдіреді. Екінші жағынан, бағытталмаған графикте жиек реттелмеген жұп болып табылады, өйткені жиекпен байланысты ешқандай бағыт жоқ. Бағытталмаған графиктерді объектілер арасындағы симметриялық қатынастарды көрсету үшін пайдалануға болады. Бағытсыз графиктегі әрбір түйіннің дәрежелі және сыртқы дәрежесі тең, бірақ бұл бағытталған график үшін дұрыс емес. Матрицаны бағытталмаған графикті көрсету үшін пайдаланған кезде матрица әрқашан симметриялық графикке айналады, бірақ бұл бағытталған графиктер үшін дұрыс емес. Бағыты жоқ графикті әр жиекті қарама-қарсы бағытта жүретін екі бағытталған жиектермен ауыстыру арқылы бағытталған графқа түрлендіруге болады. Дегенмен, бағытталған графикті бағытталмаған графқа түрлендіру мүмкін емес.
