გრაფთა თეორია
გრაფთა თეორია — დისკრეტული მათემატიკის ნაწილი, რომელიც შეისწავლის წვეროებისა და წიბოებისაგან შემდგარ სტრუქტურას — გრაფებს. წერტილები შეიძლება ერთმანეთთან იყოს დაკავშირებული წიბოებით. გამოყოფენ მიმართულ და მარტივ გრაფებს. მიმართულია გრაფი, როდესაც ორ რომელიმე წერტილს შორის არის ცალმხრივი წიბო, ანუ თუ რომელიმე A წერტილიდან B წერტილში მიდის წიბო, არ არის აუცილებელი B წერტილიდანაც მიდიოდეს A -ში. მარტივი გრაფის შემთხვევაში კი რომელიმე A და B წერტილებს შორის თუ არსებობს წიბო, ესეიგი ეს ორი წერტილი ორმხრივადაა დაკავშირებული, ანუ ამ შემთხვევაში წიბოს მიმართულებას მნიშვნელობა არ აქვს.
ისტორია
რედაქტირება
გრაფთა თეორიის ჩამოყალიბება უკავშირდება ქალაქ კენიგსბერგს (დღევანდელ კალინინგრადს). მაცხოვრებლებში პოპულარული იყო ერთ-ერთი გასართობი: სეირნობისას ცდილობდნენ ქალაქის შვიდივე ხიდი მინიმუმ და მაქსიმუმ ერთხელ გადაეკვეთათ. ამ გასართობით იქამდე იყვნენ დაკავებულნი, სანამ ლეონარდ ეილერმა 1736 წელს არ სცადა ამ პრობლემის გადაუჭრელობის დამტკიცება.[1] მან ხმელეთის ყველა ცალკეული ნაწილი აღიქვა წვეროებად, ხოლო ამ ნაწილების შემაერთებელი ხიდები — წიბოებად. საბოლოოდ ეილერმა მიიღო წიბოებისა და წვეროებისაგან შემდგარი სურათი, რასაც შემდგომში ეილერის გრაფი ეწოდა.
ერთ-ერთი ყველაზე ცნობილი ამოცანა გრაფთა თეორიაში არის ოთხი ფერის პრობლემა, რაც შემდეგში მდგომარეობს: შესაძლებელია თუ არა სიბრტყეზე დახატული ნებისმიერი რუკის გაფერადება მაქსიმუმ ოთხი ფერით, ისე, რომ არც ერთი ორი მეზობელი ქვეყანა არ იყოს ერთი და იმავე ფერით გაფერადებული. პრობლემა პირველად 1852 წელს წარმოჭრა მათემატიკოსმა ფრენსის გოსრიმ, რაზე პასუხის გაცემასაც საუკუნეზე მეტი დასჭირდა. 1976 წელს აპელმა და ჰაკენმა ამოცანას დადებითი პასუხი გასცეს. [2][3]
გამოყენება
რედაქტირებაგრაფთა თეორიას თითქმის ყველა სფეროში აქვს გამოყენება: ფიზიკა, ბიოლოგია[4], სოციალური და ინფორმაციული სისტემები და სხვა. უამრავი პრაქტიკული პრობლემა გრაფთა თეორიის მეშვეობით იჭრება. ყველაზე ხშირად ის კომპიუტერულ მეცნიერებებში გამოიყენება. მაგალითად ვებსაიტი შესაძლოა აღვიქვად როგორც მიმართული გრაფი, სადაც წვეროები წარმოადგენს თითოეულ ვებგვერდს, ხოლო მიმართული წიბოები მისამართებს ერთი კონკრეტული გვერდიდან მეორეზე. ასევე დიდია მისი გამოყენება სოციალურ ქსელებში, სადაც წვეროებად აღებულია თითოეული მომხმარებელი და მათ შორის წიბო აღნიშნავს ამ ორ მომხმარებელს შორის არსებულ ურთიერთობას: იქნება ეს მეგობრობა, ოჯახის წევრობა, ნაცნობობა თუ სხვა. გრაფთა თეორია გამოიყენება ნებისმიერი მარშრუტის დაგეგმვისას. მიუხედავად იმისა, რომ დღესდღეობით ოპტიმალური მარშრუტის არჩევის ზუსტი ალგორითმი დაუდგენელია, გრაფთა თეორია გვაძლევს საშუალებას მივაღწიოთ ოპტიმალურთან მაქსიმალურად მიახლოებულ შედეგს.
გრაფის აგება
რედაქტირებაგრაფის ყველაზე გავრცელებული წარმოდგენაა წვეროებისა და წიბოების წყვილი G = (V, E), სადაც G აღნიშნავს გრაფს, ხოლო V და E შესაბამისად წვეროებისა და მათ შორის მდებარე წიბოების სიმრავლეებს.[5] გრაფი ვიზუალურად წარმოდგენილია წერტილებით ან წრეებით, რომელთაგანაც ზოგიერთი, ყველა ან არც ერთი შეერთებულია ხაზებით ან რკალებით (წიბოებით). თუ გრაფი მიმართულია, ხაზის ნაცვლად იქნება ისარი, მიმართული რომელიმე წვეროსაკენ.
სქოლიო
რედაქტირება- ↑ Biggs, N.; Lloyd, E.; Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press
- ↑ Appel, K.; Haken, W. (1977), "Every planar map is four colorable. Part I. Discharging", Illinois J. Math. 21: 429–490
- ↑ Appel, K.; Haken, W. (1977), "Every planar map is four colorable. Part II. Reducibility", Illinois J. Math. 21: 491–567
- ↑ Mashaghi, A.; et al. (2004). „Investigation of a protein complex network“. European Physical Journal B. 41 (1): 113–121. doi:10.1140/epjb/e2004-00301-0.
- ↑ "Albert R. Meyer", "Mathematics for Computer Science, Graph Theory "