Გრაფიკის კომპიუტერულ მეცნიერებაში: განმარტება, ტიპის გამოყენების მაგალითები. გრაფთა თეორია კომპიუტერულ მეცნიერებათა

ითვლის კომპიუტერული მეთოდით განსაზღვრის ურთიერთობები შერწყმული ელემენტებით. ეს არის ძირითადი ობიექტები სასწავლო გრაფაში თეორია.

ძირითადი ცნებები

რა არის გრაფაში კომპიუტერულ მეცნიერებაში? იგი მოიცავს გავურბივარ ობიექტების მოუწოდა კვანძების და წვეროების, ზოგიერთი წყვილი რომლებიც დაკავშირებულია მ. N. ნეკნები. მაგალითად, გრაფაში ფიგურა (a) შედგება ოთხი კვანძების, აღნიშნა, A, B, C და D, B, რომელიც დაკავშირებულია თითოეული სხვა სამი vertices ნეკნები, C და D ასევე უკავშირდება. ორი კვანძების მიმდებარე თუ ისინი დაკავშირებულია პირას. ნახაზზე ტიპიური გზა თუ როგორ უნდა ავაშენოთ გრაფიკის კომპიუტერულ მეცნიერებაში. Circles წარმოადგენს ოსტატი და ხაზები დამაკავშირებელი თითოეული წყვილი მათ, ნეკნები.

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

ქსელის მოდელები

გრაფიკის კომპიუტერულ მეცნიერებაში მათემატიკური მოდელი ქსელის სტრუქტურებში. შემდეგ ნახაზზე სტრუქტურა ინტერნეტი, მაშინ გამოიყენა სახელი ARPANET, დეკემბერში 1970 წელს, როდესაც იგი მხოლოდ 13 ქულა. კვანძების დამუშავების ცენტრების და ნეკნები დააკავშირებს ორი vertices feedforward therebetween. თუ არ ყურადღება მიაქციონ შეერთებული შტატები დაკისრებული რუკა, დანარჩენი იმიჯი არის 13-node გრაფაში მსგავსი წინა. ამ შემთხვევაში, ფაქტობრივი პოზიცია წვერი არ არის აუცილებელი. მნიშვნელოვანია, რომ, რომელიც კვანძების უკავშირდება ერთმანეთს.

განაცხადის გრაფიკის კომპიუტერული საშუალებას იძლევა, თუ როგორ არის ან ფიზიკური ან ლოგიკურად ერთმანეთთან ქსელის სტრუქტურა. 13-node ARPANET არის მაგალითი საკომუნიკაციო ქსელის, რომელშიც კომპიუტერი ან სხვა მოწყობილობების შეუძლია გადასცეს შეტყობინებები და კიდეები წარმოადგენს პირდაპირი ბმული რომელთა შესახებ ინფორმაცია შეიძლება გადაეცეს.

მარშრუტები

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

ეს იდეა აღძრავს განმარტება მარშრუტი, როგორც რიგი კვანძების აკავშირებს კიდეები. ზოგჯერ აუცილებელია განიხილოს მარშრუტი, რომელიც შეიცავს არა მხოლოდ კომპონენტები, არამედ თანმიმდევრობით edges დამაკავშირებელი მათ. მაგალითად, თანმიმდევრობა vertices MIT, BBN, RAND, UCLA მარშრუტი ARPANET ინტერნეტ გრაფაში. დროთა კვანძების და კიდეები შეიძლება განმეორდეს. მაგალითად, შრი, STAN, UCLA, SRI, UTAH, MIT ასევე მარშრუტი. გზა, რომლითაც ნეკნები არ განმეორდეს, მოუწოდა ჯაჭვი. თუ კვანძების არ განმეორდეს, მას უწოდებენ მარტივი ჯაჭვი.

ციკლის

განსაკუთრებით მნიშვნელოვანი სახეობების კომპიუტერული გრაფიკის - ეს ციკლები, რომელიც წარმოადგენს ბეჭედი სტრუქტურა, როგორიცაა რიგითობა კვანძების LINC, CASE, CARN, Harv, BBN, MIT, LINC. მარშრუტები მინიმუმ სამი ნეკნები, რომელიც პირველი და ბოლო კვანძის იგივეა, ხოლო დანარჩენი სხვადასხვა, წარმოადგენს ციკლური გრაფიკის კომპიუტერულ მეცნიერებაში.

მაგალითები: შრი ციკლი, STAN, UCLA, SRI არის უმოკლესი და შრი, STAN, UCLA, RAND, BBN, UTAH, SRI მნიშვნელოვნად მეტია.

პრაქტიკულად ყველა ARPANET ზღვარზე გრაფაში ეკუთვნის ციკლი. ეს განზრახ გაკეთდა, თუ რომელიმე მათგანი ვერ, იქნება შესაძლებლობა გადასვლას ერთი კვანძის სხვა. ციკლის კავშირგაბმულობისა და ტრანსპორტის სისტემები იმყოფება redundancy - ისინი ალტერნატიული მარშრუტების კიდევ ერთი ციკლი გზას. სოციალური ქსელები ხშირად შესამჩნევი ციკლები. როდესაც თქვენ, მაგალითად, რომ ახლო სკოლის მეგობარს დეიდაშვილი ცოლის რეალურად მუშაობს თქვენი ძმა, ეს არის ციკლი, რომელიც შედგება თუ არა, შენი ცოლი, მისი დეიდაშვილი, მისი მეგობარი სკოლიდან, მისი თანამშრომელი (ie. E. შენი ძმა), და ბოლოს კიდევ ერთხელ.

Connected გრაფაში: განმარტება (კომპიუტერული მეცნიერების)

ბუნებრივია, საინტერესოა, შესაძლებელია თუ არა, თითოეული კვანძის მიიღოს ნებისმიერი სხვა კვანძის. გრაფაში არის დაკავშირებული, თუ არსებობს გზას შორის თითოეული წყვილი წვერები. მაგალითად, ARPANET ქსელი - დაკავშირებული გრაფაში. იგივე შეიძლება ითქვას, რომ უმრავლესობა საკომუნიკაციო და სატრანსპორტო ქსელები, მათი მიზანია, პირდაპირი მიმოსვლის ერთი კვანძის სხვა.

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

კომპონენტები

იმ შემთხვევაში, თუ სვეტი არ არის დაკავშირებული კომპიუტერი, ისინი ბუნებრივად მოხვდება კომპლექტი დაკავშირებული ფრაგმენტები, ჯგუფების კვანძების რომ იზოლირებული და არ იკვეთება. მაგალითად, სურათზე გამოსახულია სამი ასეთი ნაწილად: პირველი - A და B, მეორე - C, D და E, და მესამე შედგება დარჩენილი წვეროების.

კომპონენტები გრაფაში წარმოადგენს subset კვანძების, რომელშიც:

• თითოეული vertex ქვეჯგუფი აქვს მარშრუტი ნებისმიერი სხვა;
• subset ნაწილი არ არის დიდი ნაკრები, რომელიც თითოეული კვანძის აქვს მარშრუტი ნებისმიერ სხვა.

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

მაქსიმალური კომპონენტი

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

არის ეს დაკავშირებული? ალბათ, არა. დაკავშირებადობა - საკმაოდ მყიფე ქონება და ქცევის ერთი კვანძის (ან მცირე კომპლექტი მათ) შეუძლია შეამციროს არაფერი. მაგალითად, ერთი ადამიანი არ ცხოვრობს მეგობარი არის კომპონენტი შედგება ერთი vertex, და, შესაბამისად, რაოდენობა არ იქნება დაკავშირებული. ან დისტანციური ტროპიკულ კუნძულზე, რომელიც შედგება ადამიანები, რომლებიც არ კონტაქტში გარე სამყაროსთან, იქნება მცირე კომპონენტი ქსელი, რომელიც ადასტურებს მისი incoherence.

Global ქსელი მეგობრები

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

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

ზოგიერთ იშვიათ შემთხვევებში, როდესაც ორი კომპონენტის მაქსიმალური თანამშრომლობის არსებობდა დიდი ხანია ნამდვილი ქსელი, მათი კავშირი მოულოდნელი იყო, დრამატული და, საბოლოო ჯამში, აქვს კატასტროფული შედეგები მოჰყვა.

Accident კომპონენტი შერწყმა

მაგალითად, ჩამოსვლის შემდეგ ევროპელი მოგზაურები, რომ ცივილიზაცია დასავლეთ ნახევარსფეროში დაახლოებით ნახევარი ათასწლეულის წინ, იყო გლობალური cataclysm. საწყისი თვალსაზრისით ქსელში, თითქოს ეს: ხუთი ათასი წლის გლობალური სოციალური ქსელი, ალბათ შედგებოდა ორი გიგანტური კომპონენტი - ერთი ჩრდილოეთ და სამხრეთ ამერიკაში, ხოლო მეორე - ევრაზიაში. ამ მიზეზით, ტექნოლოგია განვითარდა დამოუკიდებლად ორი კომპონენტი, და კიდევ უარესი, როგორც განვითარებული და ადამიანის დაავადება, და ასე შემდეგ. D. როდესაც ორი კომპონენტი საბოლოოდ დაუკავშირდა ტექნიკა და დაავადება სწრაფად და კატასტროფულად overflowed მეორე.

ამერიკული უმაღლესი სკოლის

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

მანძილი და სიგანის პირველი ძიება

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

ამისათვის, განსაზღვრავს მარშრუტის სიგრძე ტოლი რაოდენობის ნაბიჯები, რომ ის შეიცავს თავიდან ბოლომდე, ანუ. E. რაოდენობა edges თანმიმდევრობით, რომ არის. მაგალითად, MIT, BBN, RAND, UCLA მარშრუტი სიგრძე 3 და MIT, UTAH - 1. გამოყენება სიგრძის გზა, ჩვენ შეგვიძლია ვთქვათ, რომ თუ ორი კვანძების მოწყობილი სვეტი ერთმანეთთან ახლოს ან შორს მანძილი ორ მწვერვალები განისაზღვრება, როგორც ხანგრძლივობა უმოკლეს გზაზე მათ შორის. მაგალითად, შორის მანძილი LINC და SRI 3, თუმცა, იმისათვის, რომ ეს აუცილებელია, რათა გადაამოწმონ არარსებობის სიგრძე ტოლია 1 ან 2, therebetween.

სიგანის პირველი ძებნის ალგორითმი

იყიდება პატარა გრაფაში მანძილი ორ კვანძების გამოთვლა მარტივად. მაგრამ რთული არ არის საჭირო სისტემატური მეთოდის განსაზღვრის დისტანციებზე.

ყველაზე ბუნებრივი გზა ამის გაკეთება და, აქედან გამომდინარე, ყველაზე ეფექტური ასეთია (მაგალითად, გლობალური ქსელი მეგობრების):

• ყველა მეგობრები განაცხადა მდებარე მანძილი 1.
• ყველა მეგობრები მეგობრები (თუ არ ჩავთვლით უკვე აღინიშნა) გამოაცხადა at მანძილი 2.
• ყველა მათი მეგობრები (კიდევ ერთხელ, თუ არ ჩავთვლით შეაფასა ადამიანი) განაცხადა დისტანციური მანძილი 3.

გრძელდება ამ გზით, ძებნის ხორციელდება მომდევნო ფენა, რომელთაგან თითოეული - ერთეული, რომელიც წინა. ყოველი ახალი ფენა შედგება კვანძების, რომ მონაწილეობა არ წინა პირობა, და რომ დაეცემა პირას საწყისი vertex წინა ფენა.

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

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

მცირე მსოფლიოში

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

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

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

მათ შორის 64 ჯაჭვების რომ მიაღწიეს სამიზნე, საშუალო ხანგრძლივობა იყო ექვსი დამადასტურებელი ნომერი დაასახელა ორი ათეული წლის განმავლობაში ადრე პიესა Dzhona Gera სათაური.

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