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

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

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

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

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

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

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

გავრცელებული პრაქტიკაა წვეროების იდენტიფიკაცია რიცხვებით, და არა სახელებით (როგორც „ოდრი“, „ბოსტონ“, ან „სვიტრი“). ანუ, ზოგადად, გადავნომრავთ vertical bar, V, vertical bar წვეროს 0-დან vertical bar, V, vertical bar, minus, 1-მდე. აი, სოციალური ქსელის გრაფი, რომლის 10 წვეროს აწერია ნომრები და არა — სახელები:

წიბოთა სიები

გრაფის წარმოდგენის ერთ-ერთი მარტივი გზა არის სია ან მასივი vertical bar, E, vertical bar წიბოთი, რომელსაც ვუწოდებთ წიბოების სიას. წიბოს წარმოსადგენად გვაქვს მასივი, რომელშიც თითოეული ობიექტი არის წვეროების აღმწერი ორი რიცხვი. ეს რიცხვები წარმოადგენენ იმ წვეროებს, რომლებსაც წიბოები ეხებიან. თუ წიბოებს აქვთ წონები, დაამატეთ მასივს ან მესამე ელემენტი, ან დაამატეთ ობიექტს ინფორმაცია, რომლითაც წიბოს მისცემთ წონას. ვინაიდან თითოეული წიბო შეიცავს მხოლოდ ორ ან სამ რიცხვს, წიბოების სიისთვის საჭირო ჯამური ადგილი არის \Theta, left parenthesis, E, right parenthesis. მაგალითად, აი, როგორ წარმოვადგენთ 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] ]

წიბოების სიები მარტივია, მაგრამ თუ გვინდა, გავარკვიოთ, მოცემული გრაფი შეიცავს თუ არა კონკრეტულ წიბოს, უნდა ვეძებოთ მთელ წიბოების სიაში. თუ წიბოების სიაში წიბოები განაწილებული არ არის რაიმე კონკრეტული მიმდევრობით, ამისათვის წრფივი დრო დაგვჭირდება: vertical bar, E, vertical bar. კითხვა დასაფიქრებლად: რას გაუკეთებდით წიბოების სიას, რომ მასში წიბოს მოძებნისთვის O, left parenthesis, \lg, E, right parenthesis დრო იყოს საჭირო? პასუხი არც ისე მარტივია.

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

vertical bar, V, vertical bar-წვეროიანი გრაფისთვის მოსაზღვრეობის მატრიცა არის vertical bar, V, vertical bar, times, vertical bar, V, vertical bar მატრიცა 0-ებითა და 1-ებით, რომელშიც i მწკრივსა და j სვეტში მდებარე მონაცემი არის 1 მაშინ და მხოლოდ მაშინ, თუ left parenthesis, i, comma, j, right parenthesis წიბო არსებობს გრაფში. თუ გსურთ წიბოს წონის მითითება, ჩასვით ის 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, მაშინ შეგვიძლია, წიბო left parenthesis, i, comma, j, right parenthesis მოვითხოვოთ გრაფში graph[i][j]-ზე შეხედვით. მაშინ რა არის მოსაზღვრეობის მატრიცის სისუსტე? მას ორი სისუსტე აქვს. პირველი, მას მიაქვს \Theta, left parenthesis, V, squared, right parenthesis ადგილი, მაშინაც კი, თუ გრაფი არის მეჩხერი (დაბინდული): შედარებით ნაკლები წიბოთი. სხვა სიტყვებით, მეჩხერი გრაფის შემთხვევაში მოსაზღვრეობის მატრიცა ძირითადად შედგება 0-ებით და ვიყენებთ დიდ ადგილს მხოლოდ რამდენიმე წიბოს წარმოსადგენად. მეორე, თუ გსურთ, გაიგოთ, რომელი წვეროებია მოცემული წვერო i-ს მეზობლები, უნდა შეხედოთ ყველა vertical bar, V, vertical bar მონაცემს i მწკრივში, მაშინაც კი, როცა i წვეროს მცირე რაოდენობის მეზობლები ჰყავს.

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

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

გრაფის წარმოდგენა მოსაზღვრეობის სიებით აერთიანებს მოსაზღვრეობის მატრიცებს წიბოების სიებთან. თითოეული წვერო i-სთვის ვინახავთ მის მხებ (მეზობელ) წვეროებს. ძირითადად, გვაქვს vertical bar, V, vertical bar მოსაზღვრეობის სიის მასივი, ერთი მოსაზღვრეობის სია თითოეული წვეროსთვის. აი, სოციალური ქსელის გრაფის მოსაზღვრეობის სიის სახით წარმოდგენა:

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] ]

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

თითოეული წვეროს მოსაზღვრე სიასთან მისვლა შეგვიძლია მუდმივ დროში, რადგან ამისთვის მხოლოდ მასივის ინდექსის მითითება გვჭირდება. იმის გასარკვევად, left parenthesis, i, comma, j, right parenthesis წიბო არსებობს თუ არა გრაფში მივდივართi-ს მოსაზღვრეობის სიასთან მუდმივ დროში და შემდეგ ვეძებთ j-ს i-ს მოსაზღვრეობის სიაში. რა დრო სჭირდება ამას ცუდ შემთხვევაში? პასუხი არის \Theta, left parenthesis, d, right parenthesis, სადაც d არის i წვეროს ხარისხი, რადგან სწორედ ამ სიგრძის არის i-ს მოსაზღვრეობის სია. i-ს ხარისხი შეიძლება, იყოს vertical bar, V, vertical bar, minus, 1-ის ტოლი (თუ i არის ყველა სხვა vertical bar, V, vertical bar, minus, 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]);
}

რა ადგილი მიაქვთ მოსაზღვრეობის მატრიცებს? გვაქვს vertical bar, V, vertical bar სია და მიუხედავად იმისა, რომ თითოეულ სიას შეიძლება ჰქონდეს vertical bar, V, vertical bar, minus, 1 წვერო, არამიმართული გრაფების მოსაზღვრეობის სიები ჯამში შეიცავენ 2, vertical bar, E, vertical bar ელემენტს. რატომ 2, vertical bar, E, vertical bar? მოსაზღვრეობის სიაში თითოეული წიბო left parenthesis, i, comma, j, right parenthesis გვხვდება ზუსტად ორჯერ, ერთხელ i-ს სიაში და ერთხელ j-ს სიაში და სულ გვაქვს vertical bar, E, vertical bar წიბო. მიმართული გრაფის შემთხვევაში მოსაზღვრეობის სიები შეიცავენ ჯამში vertical bar, E, vertical bar ელემენტს, თითო ელემენტს თითო მიმართულ წიბოზე.

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

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

შესვლა

დავალაგოთ:

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

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