მიმართული vs არამიმართული გრაფიკი
გრაფია არის მათემატიკური სტრუქტურა, რომელიც შედგება წვეროებისა და კიდეებისგან. გრაფიკი წარმოადგენს ობიექტების ერთობლიობას (გამოსახული წვეროებით), რომლებიც დაკავშირებულია ზოგიერთი ბმულით (გამოსახულია კიდეებით). მათემატიკური აღნიშვნების გამოყენებით, გრაფიკი შეიძლება წარმოდგენილი იყოს 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 არის წვერო, რომელსაც ეწოდება e კიდის საწყისი, წყარო ან საწყისი წერტილი, ხოლო y წვერო ეწოდება ბოლო., ბოლო წვერო ან ტერმინალური წერტილი. მაგალითად, საგზაო ქსელი, რომელიც აკავშირებს ქალაქების ერთობლიობას ცალმხრივი გზების გამოყენებით, შეიძლება წარმოდგენილი იყოს არამიმართული გრაფიკის გამოყენებით. ქალაქები შეიძლება წარმოდგენილი იყოს წვეროებით გრაფიკზე, ხოლო მიმართული კიდეები წარმოადგენს გზებს, რომლებიც აკავშირებენ ქალაქებს გზაზე მოძრაობის მიმართულების გათვალისწინებით.
რა განსხვავებაა მიმართულ გრაფიკსა და არამიმართულ გრაფიკს შორის?
მიმართულ გრაფიკში კიდე არის მოწესრიგებული წყვილი, სადაც მოწესრიგებული წყვილი წარმოადგენს იმ კიდის მიმართულებას, რომელიც აკავშირებს ორ წვეროს. მეორეს მხრივ, არამიმართულ გრაფაში, კიდე არის დაუგეგმავი წყვილი, რადგან არ არსებობს მიმართულება, რომელიც ასოცირდება კიდესთან. არამიმართული გრაფიკები შეიძლება გამოყენებულ იქნას ობიექტებს შორის სიმეტრიული ურთიერთობების წარმოსაჩენად. არამიმართულ გრაფაში თითოეული კვანძის შიდა და გარე ხარისხი ტოლია, მაგრამ ეს ასე არ არის მიმართული გრაფისთვის. მატრიცის გამოყენებისას არამიმართული გრაფის წარმოსაჩენად, მატრიცა ყოველთვის ხდება სიმეტრიული გრაფიკი, მაგრამ ეს ასე არ არის მიმართული გრაფიკებისთვის. არამიმართული გრაფიკი შეიძლება გარდაიქმნას მიმართულ გრაფიკად, თითოეული კიდის ჩანაცვლებით საპირისპირო მიმართულებით მიმავალი ორი მიმართული კიდით. თუმცა, შეუძლებელია მიმართული გრაფის გადაყვანა არამიმართულ გრაფიკად.
