ლემა 8.4.2
თუ D არის მიმართული აციკლური გრაფი, მაშინ D+ იქნება ნაწილობრივი დალაგება.
დალაგება იყოს ასეთი, თუ A წვერო უერთდება B წვეროს (წიბო B-სკენაა მიმართული), მაშინ B ნაკლებია A-ზე. ის, რომ გრაფი აციკლურია, ნიშნავს რომ და ანტისიმეტრიულობა დაცულია. დაცულია რეფლექსურობაც იმიტომ, რომ წვეროები საკუთარ თავს არ უერთდებიან. რეფლექსურობა დაცული იქნება D+-შიც, ანუ თუ დავასკვნით, რომ D+ ნაწილობრივი დალაგებაა, გამოვა რომ იგი მკაცრიცაა.
ამბროლას კონსპექტიდან - თუ გვაქვს გრაფი D, მაშინ შეიძლება განვიხილოთ ახალი გრაფი: a წვეროდან გავავლოთ ისარი b წვეროში, თუ a-დან შეიძლება b-ში მისვლა (ანუ, არსებობს რაღაც გზა). ამ ახალ გრაფს ეწოდება დადებითი გზის გრაფი და აღინიშნება ასე: D+.
ეს იმას ნიშნავს, რომ D+-ს შემოაქვს ტრანზიტულობა - თუ შეგვიძლია a-დან b-ში გადასვლა გადაჯდომით, ახლა შეგვიძლია პირდაპირადაც. ანუ: თუ a<k, k<e ..... e<b, მაშინ a<b.
problem 8.2
ტრივიალურია, გრაფი უნდა გაარჩიო. ასეთი არ მოვა (ალბათ).
problem 8.3
ამოცანა ვერ გავიგე. აზიზამ, ტრივიალურიაო, ამბროლამ უბრალოდ მაგალითი გვაჩვენაო.
თუ D არის მიმართული აციკლური გრაფი, მაშინ D+ იქნება ნაწილობრივი დალაგება.
დალაგება იყოს ასეთი, თუ A წვერო უერთდება B წვეროს (წიბო B-სკენაა მიმართული), მაშინ B ნაკლებია A-ზე. ის, რომ გრაფი აციკლურია, ნიშნავს რომ და ანტისიმეტრიულობა დაცულია. დაცულია რეფლექსურობაც იმიტომ, რომ წვეროები საკუთარ თავს არ უერთდებიან. რეფლექსურობა დაცული იქნება D+-შიც, ანუ თუ დავასკვნით, რომ D+ ნაწილობრივი დალაგებაა, გამოვა რომ იგი მკაცრიცაა.
ამბროლას კონსპექტიდან - თუ გვაქვს გრაფი D, მაშინ შეიძლება განვიხილოთ ახალი გრაფი: a წვეროდან გავავლოთ ისარი b წვეროში, თუ a-დან შეიძლება b-ში მისვლა (ანუ, არსებობს რაღაც გზა). ამ ახალ გრაფს ეწოდება დადებითი გზის გრაფი და აღინიშნება ასე: D+.
ეს იმას ნიშნავს, რომ D+-ს შემოაქვს ტრანზიტულობა - თუ შეგვიძლია a-დან b-ში გადასვლა გადაჯდომით, ახლა შეგვიძლია პირდაპირადაც. ანუ: თუ a<k, k<e ..... e<b, მაშინ a<b.
problem 8.2
ტრივიალურია, გრაფი უნდა გაარჩიო. ასეთი არ მოვა (ალბათ).
problem 8.3
ამოცანა ვერ გავიგე. აზიზამ, ტრივიალურიაო, ამბროლამ უბრალოდ მაგალითი გვაჩვენაო.
No comments:
Post a Comment