ძირითადი მასალა

კომპიუტერული მეცნიერება

კურსი: კომპიუტერული მეცნიერება > თემა 1

გაკვეთილი 10: დიაგრამის გამოსახვა

დიაგრამის გამოსახვა

არსებობს გრაფების წარმოდგენის რამდენიმე გზა, თითოეულ მათგანს აქვს საკუთარი უპირატესობა და სისუსტე. ზოგიერთი სიტუაცია ან ალგორითმი, რომელთა გამოყენებაც გრაფებზე გვსურს, მოითხოვს წარმოდგენის ერთ ხერხს, სხვები კი მოითხოვენ წარმოდგენის სხვა ხერხებს. აქ ვნახავთ გრაფების წარმოდგენის სამ გზას.

შევხედავთ სამ კრიტერიუმს. ერთი არის საჭირო მეხსიერების (იგივე ადგილის) რაოდენობა თითოეულ წარმოდგენის ხერხში. ამისათვის გამოვიყენებთ ასიმპტოტურ ნოტაციას. დიახ, ასიმპტოტური ნოტაციის გამოყენება სამუშაო დროის გარდა სხვა რაღაცებისთვისაც შეგვიძლია! ეს, რეალურად, არის ფუნქციების დახარისხების გზა და ფუნქციებმა შეიძლება, აღწერონ მუშაობის დრო, საჭირო ადგილის რაოდენობა, ან რაიმე სხვა რესურსი. დანარჩენი ორი კრიტერიუმი, რომელსაც გამოვიყენებთ, დაკავშირებულია დროსთან. ერთი არის იმის აღწერა, თუ რამდენი ხანი სჭირდება იმის დადგენას, არის თუ არა მოცემული წიბო გრაფში. მეორე არის იმის დადგენა, თუ რამდენი ხანი სჭირდება მოცემული წვეროს მეზობლების პოვნას.

გავრცელებული პრაქტიკაა წვეროების იდენტიფიკაცია რიცხვებით, და არა სახელებით (როგორც „ოდრი“, „ბოსტონ“, ან „სვიტრი“). ანუ, ზოგადად, გადავნომრავთ

| V |

წვეროს 0-დან

| V | - 1

-მდე. აი, სოციალური ქსელის გრაფი, რომლის 10 წვეროს აწერია ნომრები და არა — სახელები:

წიბოთა სიები

გრაფის წარმოდგენის ერთ-ერთი მარტივი გზა არის სია ან მასივი

| E |

წიბოთი, რომელსაც ვუწოდებთ წიბოების სიას. წიბოს წარმოსადგენად გვაქვს მასივი, რომელშიც თითოეული ობიექტი არის წვეროების აღმწერი ორი რიცხვი. ეს რიცხვები წარმოადგენენ იმ წვეროებს, რომლებსაც წიბოები ეხებიან. თუ წიბოებს აქვთ წონები, დაამატეთ მასივს ან მესამე ელემენტი, ან დაამატეთ ობიექტს ინფორმაცია, რომლითაც წიბოს მისცემთ წონას. ვინაიდან თითოეული წიბო შეიცავს მხოლოდ ორ ან სამ რიცხვს, წიბოების სიისთვის საჭირო ჯამური ადგილი არის

Θ (E)

. მაგალითად, აი, როგორ წარმოვადგენთ JavaScript-ში წიბოების სიას სოციალური ქსელის გრაფისთვის:

[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]

წიბოების სიები მარტივია, მაგრამ თუ გვინდა, გავარკვიოთ, მოცემული გრაფი შეიცავს თუ არა კონკრეტულ წიბოს, უნდა ვეძებოთ მთელ წიბოების სიაში. თუ წიბოების სიაში წიბოები განაწილებული არ არის რაიმე კონკრეტული მიმდევრობით, ამისათვის წრფივი დრო დაგვჭირდება:

| E |

. კითხვა დასაფიქრებლად: რას გაუკეთებდით წიბოების სიას, რომ მასში წიბოს მოძებნისთვის

O (\lg E)

დრო იყოს საჭირო? პასუხი არც ისე მარტივია.

მოსაზღვრეობის მატრიცები

| V |

-წვეროიანი გრაფისთვის მოსაზღვრეობის მატრიცა არის

| V | \times | V |

მატრიცა 0-ებითა და 1-ებით, რომელშიც

i

მწკრივსა და

j

სვეტში მდებარე მონაცემი არის 1 მაშინ და მხოლოდ მაშინ, თუ

(i, j)

წიბო არსებობს გრაფში. თუ გსურთ წიბოს წონის მითითება, ჩასვით ის

i

მწკრივსა და

j

სვეტში და შეინახეთ სპეციალური მნიშვნელობა (თუნდაც, null) არარსებული წიბოს მისათითებლად. აი, მოსაზღვრეობის მატრიცა სოციალური ქსელის გრაფისთვის:

JavaScript-ში ამ მატრიცას შემდეგნაირად წარმოვადგენთ:

[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]

მოსაზღვრეობის მატრიცის გამოყენებით მუდმივ (კონსტანტა) დროში შეგვიძლია, დავადგინოთ, წიბო არის თუ არა გრაფში, ამისთვის მხოლოდ შესაბამისი მონაცემის მოძებნა გვიწევს მატრიცაში. მაგალითად, თუ მოსაზღვრეობის მატრიცას ჰქვია graph, მაშინ შეგვიძლია, წიბო

(i, j)

მოვითხოვოთ გრაფში graph[i][j]-ზე შეხედვით. მაშინ რა არის მოსაზღვრეობის მატრიცის სისუსტე? მას ორი სისუსტე აქვს. პირველი, მას მიაქვს

Θ (V^{2})

ადგილი, მაშინაც კი, თუ გრაფი არის მეჩხერი (დაბინდული): შედარებით ნაკლები წიბოთი. სხვა სიტყვებით, მეჩხერი გრაფის შემთხვევაში მოსაზღვრეობის მატრიცა ძირითადად შედგება 0-ებით და ვიყენებთ დიდ ადგილს მხოლოდ რამდენიმე წიბოს წარმოსადგენად. მეორე, თუ გსურთ, გაიგოთ, რომელი წვეროებია მოცემული წვერო

i

-ს მეზობლები, უნდა შეხედოთ ყველა

| V |

მონაცემს

i

მწკრივში, მაშინაც კი, როცა

i

წვეროს მცირე რაოდენობის მეზობლები ჰყავს.

მიუმართავი (არამიმართული) გრაფის შემთხვევაში მოსაზღვრეობის მატრიცა სიმეტრიულია: მწკრივი

i

, სვეტი

j

მონაცემი არის 1 მაშინ და მხოლოდ მაშინ, როცა მწკრივი

j

, სვეტი

i

მონაცემი არის 1. მიმართულ გრაფში მოსაზღვრეობის მატრიცა შეიძლება, არ იყოს სიმეტრიული.

მოსაზღვრეობის სიები

გრაფის წარმოდგენა მოსაზღვრეობის სიებით აერთიანებს მოსაზღვრეობის მატრიცებს წიბოების სიებთან. თითოეული წვერო

i

-სთვის ვინახავთ მის მხებ (მეზობელ) წვეროებს. ძირითადად, გვაქვს

| V |

მოსაზღვრეობის სიის მასივი, ერთი მოსაზღვრეობის სია თითოეული წვეროსთვის. აი, სოციალური ქსელის გრაფის მოსაზღვრეობის სიის სახით წარმოდგენა:

JavaScript-ში ამ მოსაზღვრეობის სიებს შემდეგნაირად წარმოვადგენთ:

[ [1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]

არ არის აუცილებელი, რომ წვეროების რიცხვები მოსაზღვრეობის სიაში რაიმე კონკრეტული მიმდევრობით იყვნენ დალაგებული, თუმცა ხშირად მოსახერხებელია მათი ზრდადობით წარმოდგენა, როგორც ეს ამ მაგალითშია.

თითოეული წვეროს მოსაზღვრე სიასთან მისვლა შეგვიძლია მუდმივ დროში, რადგან ამისთვის მხოლოდ მასივის ინდექსის მითითება გვჭირდება. იმის გასარკვევად,

(i, j)

წიბო არსებობს თუ არა გრაფში მივდივართ

i

-ს მოსაზღვრეობის სიასთან მუდმივ დროში და შემდეგ ვეძებთ

j

-ს

i

-ს მოსაზღვრეობის სიაში. რა დრო სჭირდება ამას ცუდ შემთხვევაში? პასუხი არის

Θ (d)

, სადაც

d

არის

i

წვეროს ხარისხი, რადგან სწორედ ამ სიგრძის არის

i

-ს მოსაზღვრეობის სია.

i

-ს ხარისხი შეიძლება, იყოს

| V | - 1

-ის ტოლი (თუ

i

არის ყველა სხვა

| V | - 1

წვეროს მხები) ან 0 (თუ

i

იზოლირებულია, არც ერთი მეზობელი არ ჰყავს). მიუმართავ (არამიმართულ) გრაფში წვერო

j

არის წვერო

i

-ს მოსაზღვრეობის სიაში მაშინ და მხოლოდ მაშინ, როცა

i

არის

j

-ს მოსაზღვრეობის სიაში. თუ გრაფი შეწონილია, მაშინ მოსაზღვრეობის თითოეული სია არის ან ორი ელემენტის მასივი ან ობიექტი, რომელიც გვაძლევს წვეროს ნომერს და წიბოს წონას.

მოსაზღვრეობის სიაში ელემენტებზე იტერაციისთვის შეგიძლიათ, გამოიყენოთ for ციკლი. მაგალითად, წარმოიდგინეთ, რომ გაქვთ მოსაზღვრეობის სიის სახით წარმოდგენილი გრაფი ცვლადში graph, ანუ graph[i] არის წვერო

i

-ს მეზობლების შემცველი მასივი. მაშინ, ფუნქცია

i

-ს მეზობელ თითოეულ წვეროზე doStuff-ის გამოსაძახებლად შეგიძლიათ, გამოიყენოთ JavaScript-ის შემდეგი კოდი:

for (var j = 0; j < graph[i].length; j++) {
    doStuff(graph[i][j]);
}

თუ ორმაგი დაინდექსების ნოტაცია გაბნევთ, შეგიძლიათ, ასე იფიქროთ:

var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
    doStuff(vertex[j]);
}

რა ადგილი მიაქვთ მოსაზღვრეობის მატრიცებს? გვაქვს

| V |

სია და მიუხედავად იმისა, რომ თითოეულ სიას შეიძლება ჰქონდეს

| V | - 1

წვერო, არამიმართული გრაფების მოსაზღვრეობის სიები ჯამში შეიცავენ

2 | E |

ელემენტს. რატომ

2 | E |

? მოსაზღვრეობის სიაში თითოეული წიბო

(i, j)

გვხვდება ზუსტად ორჯერ, ერთხელ

i

-ს სიაში და ერთხელ

j

-ს სიაში და სულ გვაქვს

| E |

წიბო. მიმართული გრაფის შემთხვევაში მოსაზღვრეობის სიები შეიცავენ ჯამში

| E |

ელემენტს, თითო ელემენტს თითო მიმართულ წიბოზე.

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.

გსურთ, შეუერთდეთ დისკუსიას?

შესვლა

დავალაგოთ:

პოსტები ჯერ არ არის.

გესმით ინგლისური? დააწკაპუნეთ აქ და გაეცანით განხილვას ხანის აკადემიის ინგლისურენოვან გვერდზე.