რა არის გრაფიკის თეორია და როგორ განისაზღვრება გრაფიკი, როგორც ასეთი?

1736 წელს, შვეიცარიელი ფიზიკოს-მათემატიკოსის ლეონჰარდ ეილერის (1707-1783) ნაშრომზე დაყრდნობით, დაფიქსირდა, რომ წვეროების თანმიმდევრობა განსაზღვრავს ბილიკი, თუმცა, თუ აღნიშნული გზა შედგება სხვადასხვა წვეროებისგან, კიდეების განმეორების გარეშე, მას უწოდებენ გზას ან ბილიკს. ეილერიანი; თუ დამატებით მივალთ საწყის წერტილში, თითოეულ კიდეს მხოლოდ ერთხელ გადავკვეთთ, მაშინ გვექნება ეილერის ციკლი (წრე).

ციტატა (APA)

ალექსანდრე ბარაზა | ივლისი. 2022
დიპლომი ფიზიკაში

თავის მხრივ, ჩვენ განვსაზღვრავთ გრაფიკს, როგორც მოწესრიგებულ წყვილს (მიდის) სადაც ვ მიუთითებს გრაფის ყველა წვერის ან კვანძის (არა ცარიელი) სიმრავლეს, ხოლო ა განსაზღვრავს სიმრავლეს (ის შეიძლება იყოს ცარიელი) ყველა კიდეებისა თუ ხაზებისა, რომლებიც უერთდებიან გრაფის წვეროებს. ნაკრების ელემენტები ა შეიძლება განისაზღვროს, როგორც უწესრიგო წყვილი {v, w} სადაც v და w არის ელემენტები (კვანძები ან წვეროები) ვ, ამ გზით შემდეგ ამბობენ, რომ v და w არიან მიმდებარე წვეროები (ისინი უერთდებიან კიდეს).

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

კონიგსბერგის შვიდი ხიდის პრობლემა

ეილერმა კენიგსბერგის მოდელირება მოახდინა, როგორც გრაფიკი, სადაც თითოეული წერტილი (წვერო ან კვანძი) წარმოადგენს ხიდს და თითოეული ხაზი (კიდე) ბილიკს ხმელეთზე:

რა არის ამ პრობლემის გამოსავალი?

არ არის ერთი გამოსავალი რომელიც აკმაყოფილებს დაწესებულ პირობებს, რადგან, როგორც ეილერმა აჩვენა, წვეროები არ არის ლუწი ხარისხის, ანუ ლუწი წრფეების რაოდენობა არ მოქმედებს თითოეულ წერტილზე _[3]. როგორც ჩანს, ჩვენ არ შეგვიძლია ბევრი რამის გაკეთება ასე მარტივად განსაზღვრული სტრუქტურით, თუმცა, როგორც ეს ხშირად ხდება მათემატიკა, ზოგჯერ ყველაფერი ისე არ არის, როგორც ჩანს. ამრიგად, ერთ-ერთი ყველაზე ნაყოფიერი, განივი და ინტერდისციპლინარული სფერო _[4] ადამიანის ცოდნის, გრაფიკის თეორია.

ეილერის გრაფიკები თუ ეილერის ტრაექტორიით?

შემდეგ გრაფიკებს აქვთ ევლერის ბილიკები _[5]. ყველა მათგანს აქვს ეილერის ციკლი?

ავიღოთ მესამე გრაფიკი:

მოდით დავთვალოთ წვეროები:

შემდეგ ჩვენ ვხედავთ, რომ გზა, რომელიც განსაზღვრულია მიმდევრობით {3,4,6,2,1,3,7,6,5,4,2} არის ევლერის გზა, რადგან ის გადის მთელ გრაფიკს კიდეების გამეორების გარეშე, მაგრამ ეს არ არის ეილერის ციკლი, რადგან ის არ აღწევს საწყის წერტილს. რა მოხდებოდა, წვეროები სხვანაირად რომ დავთვალოთ? არც ისე ბევრი, გარდა იმისა, რომ ახლა გზა განისაზღვრა სხვა თანმიმდევრობით. რა მოხდებოდა, თუ ჩვენ მივყვებოდით განსხვავებულ გზას, ვიდრე ჩვენს თავდაპირველ გადაწყვეტაში იყო შემოთავაზებული? ამ კითხვაზე პასუხის გაცემა ცოტა უფრო რთულია და ის მოიცავს ალგორითმებს, რომლებითაც პროგრამული უზრუნველყოფის ინჟინრები ჩვეულებრივ აღფრთოვანებულნი არიან. პროგრამირება.

უფრო მკაცრი დასამტკიცებლად, თუ რა არის აქ გამოვლენილი, უნდა მივმართოთ შემდეგ შედეგს:

"იყავი გ დაკავშირებული გრაფიკი _[6]. მაშინ კი გ აქვს ა წრე ეილერი, თითოეული წვერის ხარისხი ლუწია, ხოლო თუ გ აქვს ეილერის გზა, G-ს აქვს უცნაური ხარისხის ზუსტად ორი წვერო _[7] (ზუსტად წვეროები, სადაც იწყება და მთავრდება გზა)".

ჩვენ შეგვიძლია დავადასტუროთ, რომ რეალურად, ჩვენს მიერ აღებულ გრაფიკში, მხოლოდ 3 და 6 წვეროებს აქვთ უცნაური ხარისხი (ეს მოხდება მაშინაც კი, თუ წვეროების ნუმერაცია განსხვავებული იყო), ამიტომ აღნიშნულ გრაფიკს აქვს გზა ეილერიანული _[8]. დანარჩენი გრაფიკებისთვის ჩვენ შეგვიძლია გავაგრძელოთ ანალოგიურად და გადავამოწმოთ, აქვთ თუ არა მათ ბილიკები და ეილერის ციკლები, ან სხვაგვარად რომ ვთქვათ, შეგვიძლია დავხატოთ ასეთი გრაფიკები ფანქრის აკრეფისა და გამეორების გარეშე? ხაზები? ამ კითხვაზე პასუხის დადგენა შესაძლებელია აქამდე ახსნილიდან, თუმცა, ეს არის სავარჯიშო საინტერესოა საავტომობილო უნარების, გამომგონებლობისა და მოთმინების თვალსაზრისით, მკითხველს ვპატიჟებ იპოვონ და დახატონ 6 ან მეტი გრაფიკი ვერტიკებთან ერთად ტრაექტორია ეილერიანი.

არსებობს სხვა ტიპის გრაფიკები? აქვს თუ არა გრაფიკების თეორიას გამოყენება "რეალურ" სამყაროში?

ეს გრაფიკები, რომლებიც ძალიან მოკლედ განვიხილეთ, არის მხოლოდ ერთი იმ მრავალი ტიპის გრაფიკიდან, რომელსაც ვპოულობთ გრაფიკების თეორიაში. ჩვენ ასევე შეგვიძლია ვიპოვოთ გრაფიკები, როგორიცაა ხეები, ძალიან წარმომადგენლობითი სიმრავლეებში, სადაც მათი ელემენტები შეიძლება კლასიფიცირდეს იერარქიებში და დათვლის გამოთვლებში და ალბათობა_[9], დიგრაფები, ჰამილტონის გრაფიკები _[10]და ა.შ.

გრაფიკული მოდელებისა და ქსელების გამოსახულება ფსიქოში. რუისი, ანა მარია.

ამ იდუმალებებს, თუ ასე გვინდა ვუწოდოთ, უზარმაზარი გამოყენებადია დღევანდელ მსოფლიოში, ისეთ მრავალფეროვან სიტუაციებში, როგორიცაა: ბიოლოგია მოლეკულური _[11], გამოთვლა_[12], ტელეკომუნიკაცია _[13] და ქსელის ანალიზი _[14]. მაშინ ღირს კითხვა: არ არის მაინც საინტერესო, რომ პრობლემა თითქმის ბანალური იქნება მათემატიკის ერთ-ერთი ყველაზე საინტერესო და თვალსაჩინო შედეგი? ალბათ, ამისთვის აუცილებელი იყო კაცობრიობის ერთ-ერთი ყველაზე გამორჩეული გონების წვლილი.