გრაფიკი შედგება ვერტიკებისა და კიდეებისგან. წვერები უკავშირდება კიდეებს გარკვეული თვისების მიხედვით - ინციდენტური მიმართება, რომელიც განსაზღვრავს კიდეების ნაკრებებს. ამ შემთხვევაში შეიძლება ჩამოყალიბდეს მარყუჟები და იზოლირებული წვერები.
ინსტრუქციები
Ნაბიჯი 1
მოდით მოცემული იყოს გრაფიკის კიდეების ნაკრები და მოცემულია მიმართება, რომლის გასწვრივ არის შესაძლებელი ზღვარზე ერთი მწვერვალიდან მეორეზე გადატანა. მაგალითად, წვერების სიმრავლე {1, 2, 3, 4, 5, 6, 7, 8}, ორი მწვერვალები x და y შეფარდებით x + y <8.
ნაბიჯი 2
ააშენეთ ვერტექსის მიმდებარე მატრიცა. ამისათვის ააშენეთ კვადრატული მაგიდა, ცხრილში სტრიქონების და სვეტების რაოდენობა ემთხვევა ვერტიკების რაოდენობას. შემდეგ დააყენეთ 1 i რიგისა და j- ის სვეტის გადაკვეთაზე, თუ i და j წვეთები აკმაყოფილებს მოცემულ თანაფარდობას. დააყენეთ 0 i რიგისა და j- ე სვეტის გადაკვეთაზე, თუ შესაბამისი ელემენტების თანაფარდობა არ არის შესრულებული.
ჩვენს მაგალითში პირველი სტრიქონი შევსებულია შემდეგნაირად:
1 + 1 <8, ასე რომ 1 არის 1 რიგისა და 1 სვეტის გადაკვეთაზე
1 + 2 <8, ისევ 1
1 + 3 <8, ისევ 1
1 + 7 <8, არასწორი უტოლობა, ამიტომ ცხრილის ეს ელემენტი იქნება 0
1 + 8 <8, ისევ 0
ნაბიჯი 3
კიდეების რაოდენობის გასარკვევად, ითვლიან რიცხვების მიმდებარე მატრიცაში, კიდეების დუბლირების გარეშე.
მაგალითში, სიმეტრიული მატრიცა იქნა მიღებული, ამიტომ ჩვენ ჩავთვალეთ ჯერ მატრიცის მთავარი დიაგონალის ზემოთ (მონიშნულია ლურჯად), შემდეგ კი მთავარ დიაგონალზე (წითლად აღინიშნება). ნეკნების საერთო რაოდენობაა 12.
ნაბიჯი 4
შექმენით ინციდენტების (კიდეების) მატრიცა. ამისათვის დახაზეთ ცხრილი, მასში მწკრივების რაოდენობა ტოლია გრაფიკში მწვერვალებისა, ხოლო სვეტების რაოდენობა უდრის კიდეების რაოდენობას. განათავსეთ ერთეულები იმ ხაზებზე, რომლებიც ზღვარზე იქნება დაკავშირებული. წვეროდან მისკენ მიმავალ კიდეებს ეწოდება მარყუჟები და ემატება მატრიცის ბოლოს. მარყუჟების შესაბამის სვეტებში არის მხოლოდ ერთი ერთეული, დანარჩენი კიდეებისგან განსხვავებით.
ნაბიჯი 5
ახლა დახაზეთ გრაფიკი. ვერტიკალურად მოათავსეთ ქაღალდზე წვერები და დააკავშირეთ ისინი კიდეებით აშენებული ცხრილების გამოყენებით. ვერტიკებს, რომლებიც არ არის დაკავშირებული კიდეებით, იზოლირებულს უწოდებენ.
