არამიმართული გრაფის მეტრიკული მახასიათებლები. მათემატიკური მოდელი

დამუშავებული მონაცემების საფუძველზე შეიძლება აშენდეს რამდენიმე მოდელი.

მართკუთხა რეალური ღირებულების მატრიცა

მონაცემთა დამუშავების შემდეგ მიიღეს მართკუთხა რეალური მატრიცა. ეს მატრიცა ასახავს ინფორმაციას m რეგიონებში დადებული კონტრაქტების ჯამური ღირებულების შესახებ (შეგახსენებთ, რომ m=86) OKPD კლასიფიკატორის n კლასისთვის (ყველა კონტრაქტი განხორციელდა 62 სხვადასხვა კლასიფიკატორის კოდის გამოყენებით). ასე რომ, შედეგად მიღებული მატრიცა შედგება m n-განზომილებიანი ვექტორებისგან.

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

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

1) ნორმალიზება რეგიონების მიხედვით

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

2) ნორმალიზება კლასიფიკატორის კოდებით

ნებისმიერი კლასიფიკატორის კოდისთვის, ჯ.

3) ნორმალიზება რეგიონების რაოდენობის მიხედვით

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

თქვენ ასევე შეგიძლიათ განიხილოთ მონაცემთა ნორმალიზების სტანდარტული მეთოდები:

1) მინი-მაქს ხაზოვანი ნორმალიზაცია

სად არის მინიმალური და მაქსიმალური ღირებულებახარჯები თითოეული რეგიონისთვის i ვექტორში.

ეს ნორმალიზება მოაქვს ყველა მონაცემს მნიშვნელობებამდე დიაპაზონში.

2) N ტიპის განაწილებამდე შემცირება (მონაცემთა სტანდარტიზაცია)

სად არის მათემატიკა. მოლოდინი,

ვექტორის სტანდარტული გადახრა.

3) არაწრფივი ნორმალიზაცია

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

კვადრატული მანძილის მატრიცა

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

მოდით შევხედოთ ყველაზე გავრცელებულ მეტრიკას:

1) ევკლიდეს მანძილი

ყველაზე გავრცელებული მეტრიკა არის გეომეტრიული მანძილი მრავალგანზომილებიან სივრცეში.

2) მინკოვსკის მეტრიკა

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

3) მანჰეტენის მეტრიკა

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

4) კოსინუსის მსგავსება

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

5) ჰემინგის მანძილი

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

სიახლოვის გრაფიკი

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

ზემოთ აღწერილი მოდელები უნივერსალურია განსახილველი პრობლემის ფარგლებში.

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

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

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

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

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

რადიუსიგრაფიკი არის წვეროების მინიმალური ექსცენტრიულობა და დიამეტრი გრაფიკი – წვეროების მაქსიმალური ექსცენტრიულობა.

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

პერიფერიულიწვეროებს აქვთ დიამეტრის ტოლი ექსცენტრიულობა.

მარტივი ჯაჭვი, რომლის სიგრძე ტოლია დიამეტრის დიამეტრს, ეწოდება დიამეტრული .

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

თეორემა 12.2.(იორდანია) ყველა ხეს აქვს ცენტრი, რომელიც შედგება ერთი ან ორისგან მიმდებარე წვეროები.

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

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

მაგალითი 12.5.იპოვეთ დიაგრამის რადიუსი, დიამეტრი და ცენტრი, რომელიც ნაჩვენებია ნახ. 12.1.

გამოსავალი.ამ ამოცანაში მოსახერხებელია გამოყენება მანძილის მატრიცა S. ამ კვადრატული სიმეტრიული მატრიცის ელემენტი უდრის წვეროებს შორის მანძილს მედა ზედა ჯ. ნახ. 12.1, მანძილის მატრიცას აქვს შემდეგი ფორმა:

. (12.2)

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

გრაფიკის რადიუსი რ– წვეროების მინიმალური ექსცენტრიულობა. ამ შემთხვევაში რ= 2. წვეროებს No2, No4 და No5 აქვთ ასეთი ექსცენტრიულობა. დათვლის დიამეტრი დ– წვეროების მაქსიმალური ექსცენტრიულობა. ამ შემთხვევაში დ= 3. მწვერვალებს No1 და No3 აქვთ ასეთი ექსცენტრიულობა, ეს არის გრაფის პერიფერია. შესწავლილ გრაფიკში წვეროები ცენტრალური ან პერიფერიული აღმოჩნდა. უმაღლესი რიგის გრაფიკებში არის სხვა წვეროები.

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

თეორემა 12.4. მოდით იყოს G გრაფიკის მიმდებარეობის მატრიცა მარყუჟების გარეშე და სადაც . შემდეგ უდრის k სიგრძის მარშრუტების რაოდენობას წვეროდან წვერომდე.

გრაფიკის თეორიის ამოცანების ამოხსნა გამოყენებით სხვადასხვა ტრანსფორმაციებიმიმდებარე მატრიცები ეწოდება ალგებრული მეთოდი .

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

გამოსავალი.ამ გრაფიკის მიმდებარეობის მატრიცა უდრის:

.

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

.

მანძილის მატრიცის დიაგონალური ელემენტები არის ნულები. გაამრავლეთ მიმდებარეობის მატრიცა თავისთავად:

.

თეორემის მიხედვით, 2 და 3 წვეროებს შორის, 1 და 4 და ა.შ. არის 2 სიგრძის მარშრუტების გარკვეული რაოდენობა (რადგან მატრიცის ხარისხი არის ორი). მარშრუტების რაოდენობა აქ არ არის გამოყენებული მარშრუტის არსებობის ფაქტი და მისი სიგრძე, რაც მითითებულია მატრიცის ხარისხის არანულოვანი ელემენტით, რომელიც არ ემთხვევა მარშრუტის გაანგარიშებისას აღნიშნულ ელემენტს; უფრო მოკლე სიგრძე. მანძილის მატრიცის ცარიელ ელემენტებში ვსვამთ 2-ს და ვიღებთ შემდეგ მიახლოებას:

.

მანძილი 1 და 3 წვეროებს შორის უცნობი რჩება. ჩვენ გავამრავლებთ მიმდებარეობის მატრიცას თავის თავზე მატრიცამდე ნულოვანი ელემენტი არ გამოჩნდება . შემდეგ მანძილის მატრიცის შესაბამისი ელემენტი ძალაუფლების ტოლიმიმდებარე მატრიცები: . შემდეგ ეტაპზე ჩვენ ვიღებთ

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

ამისათვის გაიხსენეთ მატრიცის გამრავლების წესები. მოყვანილი იყოს თვითნებური მატრიცები რიცხვითი ელემენტებით: $A$ განზომილების $n\ჯერ m$ ელემენტებით $a_(ik)$ და $B$ განზომილების $m\ჯერ q$ მატრიცა $b_(kj)$ ელემენტებით. . $C$ განზომილების $n\ჯერ q$ მატრიცას ეწოდება $A$ მატრიცის ნამრავლი $B$-ით (მიმდევრობა მნიშვნელოვანია), თუ მისი ელემენტები $c_(ij)$ განისაზღვრება შემდეგნაირად: $c_(ij) ) = \sum\limits_( k = 1)^m (a_(ik) b_(kj))$. მატრიცების ნამრავლი იწერება ჩვეულებრივი გზით $AB=C$. როგორც ვხედავთ, მატრიცების პროდუქტი მოითხოვს თანმიმდევრულობას პირველი და მეორე ფაქტორების ზომებში (პირველი ფაქტორის მატრიცის სვეტების რაოდენობა უდრის მეორე ფაქტორის მატრიცის რიგების რაოდენობას). ეს მოთხოვნა ქრება, თუ განვიხილავთ იმავე რიგის კვადრატულ მატრიცებს და, შესაბამისად, შეგვიძლია განვიხილოთ კვადრატული მატრიცის თვითნებური ძალა. ეს არის ერთ-ერთი უპირატესობა კვადრატული მატრიცებიმართკუთხა პირობამდე. კიდევ ერთი უპირატესობა ის არის, რომ ჩვენ შეგვიძლია მივცეთ გრაფიკის ინტერპრეტაცია მიმდებარე მატრიცის ხარისხის ელემენტებს.

დაე, მიმდებარე მატრიცას $A$ ჰქონდეს ფორმა: $A = \left(((\begin(მასივი)(*c) (a_(11) ) & (a_(12) ) & (...) & (a_ (1n ) ) \\ (a_(21) ) & (a_(22) ) & (...) & (a_(2n) ) \\ (...) & (...) & (... ) & (...) \\ (a_(n1) ) & (a_(n2) ) & (...) & (a_(nn) ) \\ \ბოლო (მასივი) )) \მარჯვნივ)$, და მისი $ k$th ხარისხი — $A^k = \left(((\ დასაწყისი(მასივი)(*c) (a_(11)^((k))) & (a_(12)^((k)) ) & (...) & (a_(1n)^((k)) ) \\ (a_(21)^((k)) ) & (a_(22)^((k)) ) & (. .) & (a_(2n)^((k)) ) \\ (...) & (...) & (...) & (...) \\ (a_(n1)^( (k)) ) & (a_(n2)^((k)) ) & (...) & (a_(nn)^((k)) ) \\ \ბოლო (მასივი) )) \მარჯვნივ)$ , სადაც $k = 2,3,...$ ცხადია, $A^k$, ისევე როგორც $A$ მატრიცა, იქნება სიმეტრიული მატრიცა.

მოდით $k=2$. შემდეგ $a_(ij)^((2)) = \sum\limits_(k = 1)^n (a_(il) a_(lj))$ ($i,j = 1,2,...,n $), და თითოეული წევრი $a_(il) a_(lj)$ უდრის $0$ ან $1$-ს. შემთხვევა, როდესაც $a_(il) a_(lj) = 1$ ნიშნავს, რომ გრაფიკში არის ორი კიდე: ზღვარი $\(i,l\)$ (რადგან $a_(il) = 1)$ და კიდე $\( l,j\)$ (რადგან $a_(lj) = 1$) და, შესაბამისად, გზა $\(( \(i,l\), \(l,j\) )\)$ $i-დან $-th წვერო ორი სიგრძის $j$th წვეროზე (ორი კიდეების ბილიკი). აქ ჩვენ ვსაუბრობთ გზაზე და არა ჯაჭვზე, რადგან მითითებული მიმართულება არის $i$th წვეროდან $j$th წვერომდე. ამრიგად, $a_(ij)^((2))$ გვაძლევს ყველა ბილიკის რაოდენობას გრაფაზე (გრაფიკის გეომეტრიულ ინტერპრეტაციაში) სიგრძით 2, რომელიც $i$th წვეროდან $j$th-მდე მიდის. წვერო.

თუ $k=3$, მაშინ $A^3 = A^2A = AA^2 = AAA$ და $a_(ij)^((3)) = \sum\limits_(l_1 = 1)^n (a_( il_1 ) ) a_(l_1 j)^((2)) = $$\sum\limits_(l_1 = 1)^n (a_(il_1) ) \left((\sum\limits_(l_2 = 1)^n ( a_(l_1 l_2 ) a_(l_2 j) ) \right) =$ $\sum\limits_(l_1 = 1)^n (\sum\limits_(l_2 = 1)^n (a_(il_1)) ) a_( l_1 l_2 ) a_(l_2 j) = \sum\limits_(l_1 ,l_2 = 1)^n (a_(il_1) a_(l_1 l_2) a_(l_2 j) )$.

ტერმინი $a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) $ თუ ის 1-ის ტოლია, განსაზღვრავს 3 სიგრძის გზას, რომელიც მიდის $i$-th წვეროდან $j$-th-მდე და გადის წვეროები $l_1$ და $l_2$. შემდეგ $a_(ij)^((3))$ გვაძლევს 3 სიგრძის ბილიკების რაოდენობას, რომლებიც აკავშირებენ $i$th და $j$th წვეროებს. ზოგადად, $a_(ij)^((k))$ განსაზღვრავს $k$ სიგრძის ბილიკების რაოდენობას, რომელიც აკავშირებს $i$-th და $j$-th წვეროებს. ამ შემთხვევაში, $a_(ij)^((k)) = \sum\limits_(l_1 ,l_2 ,...,l_(k - 1) = 1)^n (a_(il_1) a_(l_1 l_2) .. .) a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j)$.

ნათელია, რომ $a_(ii)^((k)) $ სიდიდე გვაძლევს $k$ სიგრძის დახურული ბილიკების რაოდენობას დაწყებული და $i$ წვეროზე დამთავრებული. ამრიგად, 2 სიგრძის ბილიკი - $a_(il) a_(li)$ ნიშნავს ბილიკს, რომელიც გადის $\( i,l \)$ კიდეზე $i$ წვეროდან $l$-მდე და უკან. ამიტომ $a_(ii)^((2)) = s_i$, ე.ი. $A^2$ მატრიცის დიაგონალური ელემენტები უდრის შესაბამისი წვეროების ხარისხებს.

ახლა $A$ მატრიცასთან ერთად განვიხილოთ $\dot (A)$ მატრიცა, რომელიც განსხვავდება $A$ მატრიცისგან მხოლოდ იმით, რომ მისი ელემენტები (რიცხვები 0 ან 1) განიხილება ლოგიკური ალგებრის ელემენტებად. ამიტომ, ასეთი მატრიცებით მოქმედებები განხორციელდება ლოგიკური ალგებრის წესების მიხედვით. ვინაიდან ლოგიკური ელემენტებით მატრიცების დამატებისა და გამრავლების მოქმედებები მცირდება ამ მატრიცების ელემენტების დამატებისა და გამრავლების მოქმედებებზე ლოგიკური არითმეტიკის წესების მიხედვით, ვიმედოვნებთ, რომ ეს არ გამოიწვევს სირთულეებს. ლოგიკური ელემენტების მქონე მატრიცას ეწოდება ლოგიკური მატრიცა. აშკარაა, რომ ლოგიკური მატრიცების შეკრებისა და გამრავლების ოპერაციები დახურულია ლოგიკური მატრიცების სიმრავლეზე, ე.ი. ამ ოპერაციების შედეგი კვლავ იქნება ლოგიკური მატრიცა.

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

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

ახლა მოდით განვმარტოთ $\dot (A)^2$ ლოგიკური მიმდებარეობის მატრიცის მეორე ხარისხი $\dot (a)_(ij)^((2)) = \sum\limits_(l = 1)^ n (\dot (a)_(il) \dot (a)_(lj) )$. ნათელია, რომ $\dot (a)_(ij)^((2)) = 1$ თუ მინიმუმ ერთი ტერმინი $\dot (a)_(il) \dot (a)_(lj) $ ტოლია 1-მდე და $\dot (a)_(ij)^(2)) = 0$ თუ ყველა წევრი 0-ის ტოლია. თუ მატრიცა $\dot (A)$ არის რომელიმე გრაფის მიმდებარე მატრიცა, ე.ი. არის სიმეტრიული (0,1) მატრიცა ნულოვანი მთავარი დიაგონალით, მაშინ $\dot (A)^2$ მატრიცა, ზოგადად რომ ვთქვათ, არ არის გრაფის მიმდებარე მატრიცა იმ გაგებით, რასაც ჩვენ ვიღებთ, რადგან მისი ყველა დიაგონალური ელემენტი უდრის 1-ს (თუ გრაფიკს არ აქვს იზოლირებული წვეროები). ასე რომ, ასეთი მატრიცები შეიძლება განიხილებოდეს როგორც მიმდებარე მატრიცები, ჩვენ უნდა მივცეთ საშუალება, რომ ზოგიერთი წვეროები ერთმანეთთან იყოს დაკავშირებული. "ზღვარი", რომელიც განსაზღვრავს გარკვეული წვერის კავშირს საკუთარ თავთან, ეწოდება მარყუჟი. გარდა ამისა, როგორც ადრე, სიტყვა გრაფაში ვიგულისხმებთ გრაფიკს მარყუჟების გარეშე, ხოლო მარყუჟების მქონე გრაფიკის შესახებ, თუ ეს არ არის ნათელი კონტექსტიდან, ასე ვიტყვით - გრაფიკი მარყუჟებით.

განვიხილოთ ჯამი $\dot (A)^() = \dot (A) + \dot (A)^2$. $\dot (A)^()$ მატრიცა გვაძლევს ორიგინალიდან მიღებულ დიაგრამას 2 სიგრძის ბილიკების შესაბამისი დამატებითი კავშირებით "გაჯერებით". ანუ ახალ გრაფიკში $i$ და $ წვეროები. j$ მომიჯნავეა, თუ ისინი მეზობლად არიან თავდაპირველ გრაფიკში, ან ეს წვეროები დაკავშირებულია 2 სიგრძის ბილიკით, ხოლო $i$ და $j$ წვეროები არამეზობელია, თუ ისინი არ არიან მეზობლად თავდაპირველ გრაფიკში და იქ. არ არის 2 სიგრძის ბილიკი, რომელიც აკავშირებს ამ წვეროებს.

$\dot (A)^() = \dot (A) + \dot (A)^2 + \dot (A)^3$ განისაზღვრება ანალოგიურად. ანუ, დიაგრამაში, რომელიც განსაზღვრულია $\dot (A)^()$ მატრიცით, $i$ და $j$ წვეროები მეზობელია, თუ ისინი მეზობლად არიან გრაფაში $\dot (A)^()$ ან ამ თავდაპირველ გრაფიკში წვეროები დაკავშირებულია 3 სიგრძით, ხოლო $i$ და $j$ წვეროები არამეზობელია, თუ ისინი არამეზობელნი არიან გრაფიკზე $\dot (A)^()$ და არ არსებობს 3 სიგრძის გზა. აკავშირებს ამ წვეროებს თავდაპირველ გრაფიკში. და ასე შემდეგ.

ზოგადად, $\dot (A)^([k]) = \sum\limits_(i = 1)^k (\dot (A)^i) $. ადვილი მისახვედრია, რომ ყველა $\dot (A)^([k])$ $k \ge n - 1$-ისთვის, სადაც $n$ არის $\dot (A)$ მატრიცის რიგი, ტოლია ერთმანეთს. მართლაც, თუ $i$ და $j$ წვეროები დაკავშირებულია, მაშინ არის ბილიკი (ჯაჭვი), რომელიც აკავშირებს ამ წვეროებს და, შესაბამისად, არის მარტივი გზა (მარტივი ჯაჭვი), რომელიც აკავშირებს ამ წვეროებს. $n$-ვერტექს გრაფაში მაქსიმალური შესაძლო მარტივი გზა აქვს $n-1$ (მარტივი გზა, რომელიც აკავშირებს გრაფის ყველა განსხვავებულ წვეროს). ამიტომ, თუ $\dot (A)^()$ მატრიცაში არის 1 $(i,j)$-ზე, მაშინ $\dot (A)^([k] მატრიცაში იმავე ადგილას. )$-ზე $k \ge n - 1$ ასევე იქნება 1, ვინაიდან $\dot (A)^()$ მატრიცა $\dot (A)^([ ლოგიკური ტერმინის სახით შედის მატრიცის განმარტებაში. კ])$. თუ $\dot (A)^()$ მატრიცაში არის 0 $(i,j)$-ის ნაცვლად, მაშინ ეს ნიშნავს, რომ არ არის მარტივი ჯაჭვი გრაფიკში, რომელიც აკავშირებს $i$-th-ს და $j-ს. $- წვეროები და, შესაბამისად, ამ წვეროების დამაკავშირებელი ჯაჭვი საერთოდ არ არსებობს. ეს ნიშნავს, რომ განსახილველ შემთხვევაში და $\dot (A)^([k])$ მატრიცაში $k \ge n - 1$ იქნება 0 ადგილზე ($i$,$j)$. ეს არის ის, რასაც ჩვენი განცხადება ამტკიცებს $\dot (A)^([k])$ $k \ge n - 1$ მატრიცის $\dot (A)^()$ მატრიცის ტოლობის შესახებ და, შესაბამისად, , ერთმანეთს.

$\dot (A)^()$ მატრიცას ეწოდება მატრიცის გარდამავალი დახურვის მატრიცა$\dot (A)$, ასევე $\dot (A)$ მატრიცით განსაზღვრული გრაფის გარდამავალი დახურვის მიმდებარე მატრიცა. სავსებით აშკარაა, რომ დაკავშირებული გრაფის გარდამავალი დახურვის მატრიცა იქნება სრული გრაფის მიმდებარეობის მატრიცა, ე.ი. კვადრატული მატრიცა, რომელიც შედგება მხოლოდ ერთისაგან. ეს დაკვირვება ასევე გვაძლევს მეთოდს გრაფიკის კავშირის დასადგენად: გრაფიკი დაკავშირებულია, თუ და მხოლოდ იმ შემთხვევაში, თუ მისი მიმდებარე მატრიცის გარდამავალი დახურვის მატრიცა შედგება მხოლოდ ერთისაგან (ეს იქნება სრული გრაფიკის მატრიცა).

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

ახლა ვაჩვენებთ, თუ როგორ გვაძლევს ტრანზიტიული დახურვის პროცედურა საშუალებას ავაშენოთ ეგრეთ წოდებული "დისტანციის მატრიცა". ამისათვის ჩვენ განვსაზღვრავთ მანძილს $i$ და $j$ წვეროებს შორის. თუ $i$ და $j$ წვეროები დაკავშირებულია, მაშინ მანძილიმათ შორის ჩვენ ვუწოდებთ ამ წვეროების დამაკავშირებელი მინიმალური (გავლილი კიდეების რაოდენობის მიხედვით) მარტივი გზის სიგრძეს; თუ $i$ და $j$ წვეროები გათიშულია, მაშინ ჩვენ ვაყენებთ მანძილს ნულის ტოლი (ნული, როგორც ამ წვეროების დამაკავშირებელი ნებისმიერი ბილიკის უარყოფა). მანძილის ამ განსაზღვრებით, მანძილი წვეროსა და საკუთარ თავს შორის უდრის 2-ს (გზის სიგრძე კიდეზე და უკან). თუ წვეროზე არის მარყუჟი, მაშინ წვეროსა და საკუთარ თავს შორის მანძილი უდრის 1-ს.

$n$-წვერო გრაფიკისთვის მანძილის მატრიცის შესაქმნელად $A$ მიმდებარე მატრიცით, რომელიც მიუთითებს მანძილს ნებისმიერ ორ წვეროს შორის, ჩვენ გავითვალისწინებთ $A^(\(k\)) = A^ მატრიცებს. ([k]) - A^()$, სადაც $k = 2,3,...,n - 1$ და $A^(\(1\)) = A^() = A$. მატრიცის აღნიშვნის ზემოთ წერტილების არარსებობა მიუთითებს იმაზე, რომ ჩვენ განვიხილავთ $A^([k])$ ($k = 1,2,...,n - 1)$ მატრიცებს, როგორც ციფრულ (0,1)-მატრიცებს, ბუნებრივად მიღებული $\dot (A)^([k])$ მატრიცებიდან (ახლა ჩვენ განვიხილავთ ლოგიკურ ელემენტებს 0 და 1 როგორც 0 და 1 რიცხვები). $A^([k])$ მატრიცების აგების მეთოდიდან გამომდინარეობს, რომ $A^([k]) \ge A^()$ ($k = 2,3,...,n - 1$) და, შესაბამისად, $A^(\(k\))$ ($k = 1,2,...,n - 1$) არის (0,1)-მატრიცები. უფრო მეტიც, $A^(\(2\))$ მატრიცა შეიცავს 1-ს მხოლოდ იმ ადგილებში, სადაც ამ ადგილით განსაზღვრული წვეროები (მწკრივის ნომერი და სვეტის ნომერი) დაკავშირებულია ორი სიგრძის ბილიკით და არ არის დაკავშირებული უფრო მოკლე ბილიკით. გზა. ანალოგიურად, $A^(\(3\))$ შეიცავს 1-ს მხოლოდ იმ ადგილებში, სადაც ამ ადგილით განსაზღვრული წვეროები დაკავშირებულია სამი სიგრძის ბილიკით და არ არის დაკავშირებული რაიმე უფრო მოკლე სიგრძის ბილიკით და ა.შ. ამრიგად, მატრიცა $D = \sum\limits_(k = 1)^(n - 1) (k \cdot A^(\(k\)))$ იქნება საჭირო მანძილის მატრიცა. ამ მატრიცის $d_(ij)$ ელემენტი ტოლი იქნება $i$ და $j$ წვეროებს შორის მანძილის. $u$ და $v$ წვეროებს შორის მანძილი ასევე აღინიშნა როგორც $d(u,v)$.

კომენტარი.პროდუქტის კონკრეტული ვადა $a_(il_1 ) a_(l_1 l_2 ) ...a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j) = 1$ ელემენტი $a_(ij ) $A^k$ მიმდებარე მატრიცის $k$-th სიმძლავრის ^((k))$ განსაზღვრავს კონკრეტულ $(i,j)$-ბილიკს $i\(i,l_1\)l_1 \(l_1 , l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \)l_(k - 1) \(l_(k - 1) ,j\)j$ $i$ -th წვეროდან $j$-th-მდე. მიმდებარე წვეროების და მათ დამაკავშირებელი კიდეების თანმიმდევრობა $i\(i,l_1 \)l_1 \(l_1 ,l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \ )l_(k - 1) \(l_(k - 1) ,j\)j$ ასევე ე.წ. $(i,j)$-მარშრუტი. მარშრუტი განსხვავდება ჯაჭვისგან, რომელიც შედგება მხოლოდ სხვადასხვა მიმდებარე კიდეებისგან იმით, რომ მარშრუტი იძლევა საშუალებას თანაბარი კიდეები. მარტივი მარშრუტი შედგება სხვადასხვა მიმდებარე წვეროებისა და კიდეებისგან, ე.ი. პრაქტიკულად ემთხვევა მარტივ ჯაჭვს.

აშკარაა, რომ მანძილის მატრიცის $d_(ij) $ ელემენტი განსაზღვრავს მინიმალური ჯაჭვის სიგრძეს, რომელიც $i$th წვეროს $j$th წვეროსთან აკავშირებს.

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

ნახ. 1 (გრაფიკი $\გამა _1$, მიმდებარეობის მატრიცა $A_1$, მანძილის მატრიცა $D_1$).
$A_1 = \left(((\ დასაწყისი(მასივი)(*c) 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \ბოლო (მასივი) )) \მარჯვნივ), $
$D_1 = \left(((\ დასაწყისი(მასივი)(*c) 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end(მასივი) )) \მარჯვნივ) $

ბრინჯი. 2 (გრაფიკა $\გამა _2$, მიმდებარეობის მატრიცა $A_2$, მანძილის მატრიცა $D_2$).
$A_2 = \მარცხენა(((\ დასაწყისი(მასივი)(*c) 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0\ \ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \ბოლო (მასივი) )) \მარჯვნივ)$,
$D_2 = \left(((\ დასაწყისი(მასივი)(*c) 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & ​​3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2\ \ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \ბოლო (მასივი) )) \მარჯვნივ). $

$D_1$ და $D_2$ მატრიცებიდან მარტივად შეიძლება დადგინდეს დიამეტრები$d_1$ გრაფიკის $\Gamma _1$ და $d_2$ გრაფიკის $\Gamma _2$, როგორც ამ მატრიცების ელემენტების მაქსიმალური მნიშვნელობები. ასე რომ, $d_1 = 3$ და $d_2 = 6$.

გარდა მანძილის მატრიცისა, გრაფთა თეორია განიხილავს სხვა მატრიცებსაც, რომელთა ელემენტები განისაზღვრება ბილიკის სიგრძით. ეს, მაგალითად, არის გავლის მატრიცა. IN გავლის მატრიცა$(i,j)$th ელემენტი სიგრძის ტოლიყველაზე გრძელი გზა (ყველაზე გრძელი ჯაჭვი) $i$th წვეროდან $j$th წვერომდე და თუ ასეთი ბილიკები საერთოდ არ არსებობს, მაშინ მანძილის განმარტების შესაბამისად, $(i,j)$ გადაკვეთის მატრიცის მე-ერთი ელემენტი დაყენებულია ნულის ტოლი.

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

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

ექსცენტრიულობა$e(v)$ $v$ წვერის დაკავშირებულ დიაგრამაში $\Gamma$ განისაზღვრება, როგორც $d(u,v)$ მაქსიმუმი $u$ $\Gamma$-ის ყველა წვეროზე. რადიუსი$r(\გამა)$ არის წვეროების უმცირესი ექსცენტრიულობა. გაითვალისწინეთ, რომ ექსცენტრისიტეტებიდან ყველაზე დიდი უდრის გრაფიკის დიამეტრს. $v$ წვეროს ეწოდება $\Gamma$ გრაფიკის ცენტრალური წვერო, თუ $e(v) = r(\Gamma)$; ცენტრიგრაფიკი $\Gamma$ არის ყველა ცენტრალური წვეროების სიმრავლე.

ასე რომ, $\Gamma _1$ გრაფიკისთვის 13-ის წვერის ექსცენტრიულობა იქნება 2-ის ტოლი ($e(13) = 2$). 3, 5 და 10 მწვერვალებს ექნებათ იგივე ექსცენტრიულობა ($e(3) = e(5) = e(10) = 2$). 2-ის ტოლი ექსცენტრიულობა უმცირესი იქნება გრაფიკისთვის $\Gamma _1$, ე.ი. $r(\გამა _1) = 2$. გრაფიკის ცენტრი $\Gamma _1$ შედგება 3, 5, 10 და 13 წვეროებისგან. უდიდესი ექსცენტრიულობა იქნება 3-ის ტოლი და ტოლი იქნება, როგორც ზემოთ აღინიშნა, დიამეტრის $\Gamma _1$. .

$\Gamma _2$ გრაფიკისთვის ნახ. 2, ერთადერთ 4 წვეროს ექნება ყველაზე პატარა ექსცენტრიულობა ($e(4) = r(\გამა _2) = 3$). შესაბამისად, გრაფის ცენტრი $\Gamma _2$ შედგება ერთი წვერისგან 4. გრაფის დიამეტრი $\Gamma _2$, როგორც ზემოთ აღინიშნა, არის 6.

გრაფიკი $\Gamma _2$ არის ხე და ნებისმიერი ხის ცენტრის სტრუქტურა აღწერილია ქვემოთ მოცემული თეორემით.

ჟორდანია-სილვესტერის თეორემა.თითოეულ ხეს აქვს ცენტრი, რომელიც შედგება ერთი ან ორი მიმდებარე წვეროსაგან.

მტკიცებულება.მოდით $K_1$-ით ავღნიშნოთ გრაფიკი, რომელიც შედგება ერთი იზოლირებული წვეროსაგან, ხოლო $K_2$-ით ავღნიშნოთ გრაფიკი, რომელიც შედგება კიდეებით დაკავშირებული ორი წვერით. განმარტებით, ჩვენ ვაყენებთ $e(K_1) = r(K_1) = 0$. მაშინ თეორემა იქნება მართალი $K_1$ და $K_2$. მოდით ვაჩვენოთ, რომ ნებისმიერ ხეს $T$ აქვს იგივე ცენტრალური წვეროები, როგორც ხეს $(T)"$, რომელიც მიიღება $T$-დან მისი ყველა ჩამოკიდებული წვერის ამოღებით. ნათელია, რომ მანძილი მოცემული $u$ წვეროდან ნებისმიერამდე. სხვა წვერო $v$ შეიძლება მიაღწიოს უმაღლესი ღირებულებამხოლოდ იმ შემთხვევაში, თუ $v$ არის დაკიდებული წვერო.

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

ახლა ვაჩვენებთ, თუ როგორ, მანძილის მატრიცის გამოყენებით, შეგვიძლია განვსაზღვროთ, მაგალითად, მინიმალური ჯაჭვი, რომელიც აკავშირებს 4 წვეროს 8 წვეროსთან გრაფიკზე $\Gamma _1$. $D_1$ მატრიცაში ელემენტი $d_(48) = 3$. ავიღოთ $D_1$ მატრიცის მე-8 სვეტი და ვიპოვოთ სვეტში ამ სვეტის ყველა ელემენტი 1-ის ტოლი. მინიმუმ ერთი ასეთი ელემენტი მოიძებნება გრაფის $D_1$ დაკავშირების გამო. სინამდვილეში, მე -8 სვეტში იქნება სამი ასეთი ერთეული და ისინი განლაგებულია მე -5, მე -6 და მე -7 რიგებში. ახლა ავიღოთ მე-4 რიგი და გადავხედოთ მასში არსებულ ელემენტებს, რომლებიც მდებარეობს მე-5, მე-6 და მე-7 სვეტებში. ეს ელემენტები იქნება 2, 3 და 3 შესაბამისად. მხოლოდ მე-5 სვეტში განთავსებული ელემენტი უდრის 2-ს და 1-თან ერთად, რომელიც მდებარეობს ადგილზე (5,8), იძლევა ჯამს 3. ეს ნიშნავს, რომ 5 წვერო შედის ჯაჭვში $\( \(4, ?\), \(? ,5\), \(5,8\) \)$. ახლა ავიღოთ მატრიცის მე-5 სვეტი და განვიხილოთ ამ სვეტის 1. ეს იქნება ელემენტები, რომლებიც მდებარეობს მე-3, მე-6, მე-7, მე-8, მე-10 და მე-13 ხაზებში. ჩვენ კვლავ ვუბრუნდებით მე-4 ხაზს და ვხედავთ, რომ მხოლოდ მესამე სვეტისა და მე-4 სტრიქონის გადაკვეთაზე არის 1, რომელიც ადგილზე 1-თან ერთად (3.5) იძლევა სულ 2-ს. შესაბამისად, სასურველი ჯაჭვი იქნება იყოს $\( \ (4,3\), \(3,5\), \(5,8\) \)$. 1-ლი სურათის გადახედვის შემდეგ, ჩვენ დავრწმუნდით ნაპოვნი გადაწყვეტის მართებულობაში.

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

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

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

2. თუ და მხოლოდ თუ ;

3. ;

4. სამკუთხედის უტოლობა მართალია:

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

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

.

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

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

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

ლუწი რიცხვი

მისი წვეროები და ერთიდან - თუ კენტი, და ნებისმიერი ციკლისთვის ყველა წვერო ცენტრალურია.

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

4.29. აქ

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

ვთქვათ, მაღაზიები. IN

მსგავსი სიტუაციები

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

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

მაგალითად, გრაფიკი ნაჩვენებია ნახ. 4.31 არის ეილერიანი, რადგან შეიცავს 1, 2, 3, 4, 5, 6, 4, 2, 6, 1 ეილერიანულ ციკლს. ნათელია, რომ ნებისმიერი ორი ასეთი ციკლი განსხვავდება ერთმანეთისგან მხოლოდ იმ თანმიმდევრობით, რომლითაც ისინი კვეთენ კიდეებს.

თეორემა 4.7.(ლ. ეილერი, 1736 წ .) დაკავშირებული გრაფიკი არის ეილერიანი, თუ და მხოლოდ მაშინ, თუ მისი ყველა წვეროს გრადუსი ლუწია.

ჯაჭვი ე.წ ეილერიანი, თუ იგი შეიცავს გრაფის ყველა კიდეს.

თეორემა 4.8(ლ. ეილერი, 1736 წ .) მულტიგრაფს აქვს ეილერის ჯაჭვი, თუ და მხოლოდ მაშინ, თუ ის დაკავშირებულია და წვეროების რაოდენობა უცნაური ხარისხიუდრის 0 ან 2.

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

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

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

1) განცხადება. თუ ორი წვეროსთვის არის მათი დამაკავშირებელი მარშრუტი, მაშინ აუცილებლად იქნება ამ წვეროების დამაკავშირებელი მინიმალური მარშრუტი. მოდით აღვნიშნოთ ამ მარშრუტის სიგრძედ(. ეს მანძილი აკმაყოფილებს მეტრულ აქსიომებს:განცხადება. თუ ორი წვეროსთვის არის მათი დამაკავშირებელი მარშრუტი, მაშინ აუცილებლად იქნება ამ წვეროების დამაკავშირებელი მინიმალური მარშრუტი. მოდით აღვნიშნოთ ამ მარშრუტის სიგრძედ(ღ) 0 დაw) = 0 თუ და მხოლოდ თუv=

2) w;

3) d(v, w) = d(w, v);

d(v, w) d(v, u) + d(u, w). დიამეტრიგანმარტება.

d(v, w) d(v, u) + d(u, w). დაკავშირებული გრაფიკის არის მაქსიმალური შესაძლო მანძილი მის ორ წვეროს შორის.ცენტრი რადიუსიგრაფის წვერო ისეთია, რომ მაქსიმალური მანძილი მასსა და ნებისმიერ სხვა წვეროს შორის ყველაზე მცირეა; ამ მანძილს ეძახიან

გრაფიკი.

მაგალითი 82.

ნახატზე ნაჩვენები G გრაფიკისთვის. 3.16, იპოვეთ რადიუსი, დიამეტრი და ცენტრები.

გამოსავალი.

გრაფიკის ცენტრების, რადიუსის, დიამეტრის დასადგენად გმოდი ვიპოვოთ მატრიცა დ(გ)მანძილი გრაფიკის წვეროებს, ელემენტებს შორის d ijრომელიც იქნება წვეროებს შორის მანძილი v iდა ვ ჯ. ამისთვის გამოვიყენებთ გრაფიკული წარმოდგენაგრაფიკი. გაითვალისწინეთ, რომ მატრიცა დ(გ)სიმეტრიულია მთავარი დიაგონალის მიმართ.

მიღებული მატრიცის გამოყენება გრაფიკის თითოეული წვეროსთვის გმოდით განვსაზღვროთ ყველაზე დიდი ამოღება გამონათქვამიდან: ამისთვის მე,j = 1, 2, ..., 5. შედეგად ვიღებთ: r(v 1) = 3,r(v 2) = 2,r(v 3) = 2,r(v 4) = 2,r(v 5) = 3.მიღებული რიცხვების მინიმუმი არის გრაფიკის რადიუსი გ, მაქსიმალური – გრაფიკის დიამეტრი გ. ნიშნავს, R(G) = 2და დ(G) = 3ცენტრები არის წვეროები v2,v 3,v 4.