დიაგრამის აღწერა

აი, სოციალური ქსელის წარმოდგენის ერთ-ერთი გზა:

ორ სახელს შორის ხაზი ნიშნავს, რომ ისინი ერთმანეთს იცნობენ. თუ ორ სახელს შორის ხაზი არ არის, მაშინ ეს ორი ადამიანი ერთმანეთს არ იცნობს. დამოკიდებულება „ერთმანეთს იცნობენ“ ორმხრივია; მაგალითად, ვინაიდან ოდრი იცნობს გეილს, ეს ნიშნავს, რომ გეილი იცნობს ოდრის.

ეს სოციალური ქსელი არის გრაფი. სახელები არის გრაფის წვეროები (ინგლ. vertices) (თუ მხოლოდ ერთ-ერთ წვეროზე საუბრობთ, ინგლისურად იწერება როგორც vertex). თითოეული ხაზი არის წიბო, რომელიც ორ წვეროს აერთებს ერთმანეთთან. $u$‍ და $v$‍ წვეროების შემაერთებელ წიბოს აღვნიშნავთ $(u,v)$‍-თი. ვინაიდან „ერთმანეთს იცნობენ“ დამოკიდებულება ორმხრივია, ეს გრაფიკი არის არამიმართული. არამიმართული წიბო $(u,v)$‍ არის იგივე, რაც $(v,u)$‍. მოგვიანებით ვნახავთ მიმართულ გრაფებს, მათ შემთხვევაში წვეროებს შორის დამოკიდებულებები შეიძლება, არ იყოს ორმხრივი. არამიმართულ გრაფში წიბო ორ წვეროს შორის, როგორიცაა წიბო ოდრისა და გეილს შორის, ეხება ამ ორ წვეროს და ვამბობთ, რომ წიბოს მიერ დაკავშირებული წვეროები არიან ერთმანეთის მხები ან მეზობლები. წვეროს მხები წიბოების რაოდენობა არის ამ წვეროს ხარისხი.

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

როდესაც გზა ბრუნდება კონკრეტული წვეროდან ამავე წვეროზე, ეს არის ციკლი. სოციალური ქსელი შეიცავს ბევრ ციკლს; მათ შორის ერთ-ერთი არის შემდეგნაირი: ოდრი-ბილი-ემილი-ჯეფი-ჰარი-ილანა და მერე ისევ ოდრი. არსებობს უფრო მცირე ცილკიც, რომელიც ოდრის შეიცავს, ის ნაჩვენებია ქვემოთ: ოდრი-ბილი-გეილი და ისევ ოდრი. სხვა რა ციკლების პოვნა შეგიძლიათ?

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

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

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

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

მიმართულ წიბოებზე სხვადასხვა ტერმინოლოგიას ვიყენებთ. ვამბობთ, რომ მიმართული წიბო გამოდის ერთი წვეროდან და შედის მეორეში. მაგალითად, ერთი მიმართული წიბო გამოდის მკერდის დამცავის წვეროდან და შედის სვიტრის წვეროში. თუ მიმართული წიბო გამოდის წვერო $u$‍-დან და შედის წვერო $v$‍-ში, მას აღვნიშნავთ შემდეგნაირად: $(u,v)$‍, წყვილის მიმდევრობა მნიშვნელოვანია. წვეროდან გამომავალი წიბოების რაოდენობა არის ამ წვეროს გარე ხარისხი და შემომავალი წიბოების რაოდენობა არის შიდა ხარისხი.

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

როდესაც გრაფებთან ვმუშაობთ, გვეხმარება წიბოების სიმრავლესა და წვეროების სიმრავლეზე ლაპარაკის შესაძლებლობა. წვეროების სიმრავლეს ძირითადად აღვნიშნავთ $V$‍ სიმბოლოს გამოყენებით და წიბოების სიმრავლეს აღვნიშნავთ $E$‍ სიმბოლოს გამოყენებით. როდესაც წარმოვადგენთ გრაფს ან გრაფზე ვუშვებთ ალგორითმს, ხშირად გვჭირდება წვეროებისა და წიბოების სიმრავლეთა ზომების გამოყენება ასიმპტოტურ ნოტაციაში. მაგალითად, წარმოიდგინეთ, რომ გვსურს სამუშაო დროზე საუბარი, რომელიც წვეროების რაოდენობის მიმართ წრფივია. უფრო ზუსტად: $\mathrm{\Theta }(|V|)$‍, $|\cdot |$‍ ნოტაციის გამოყენებით სიმრავლის ზომის აღსანიშნავად. მაგრამ სიმრავლის ამ ნოტაციის გამოყენება ასიმპტოტურ ნოტაციაში მოუხერხებელია, ამიტომ ვიღებთ აღნიშვნას ასიმპტოტურ ნოტაციაში და მხოლოდ ასიმპტოტურ ნოტაციაში, ვაშორებთ სიმრავლის ზომის ნოტაციას იმის გააზრებით, რომ სიმრავლეთა ზომებზე ვსაუბრობთ. ასე რომ, $\mathrm{\Theta }(|V|)$‍-ს დაწერის ნაცვლად ვწერთ მხოლოდ $\mathrm{\Theta }(V)$‍-ს. ანალოგიურად, $\mathrm{\Theta }(\lg |E|)$‍,-ს ნაცვლად ვწერთ $\mathrm{\Theta }(\lg E)$‍-ს.

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