§1. ნამრავლისა და ჯამის წესი, ფაქტორიალი
ამ ნაწილის ტერმინები (2)
- ნამრავლის წესი
- თუ ორი არჩევანი ერთად გვჭირდება, არჩევის გზების რაოდენობებს ვამრავლებთ.მაგალითი: 4 მაისური და 3 შარვალი: კომპლექტი გზით შედგება.
- ფაქტორიალი
- რიცხვების ნამრავლი 1-დან მოცემულ რიცხვამდე.მაგალითი: ; შეთანხმებით .
ნამრავლის წესი. თუ პირველ არჩევანს გზა აქვს და მისი ყოველი შედეგის შემდეგ მეორე არჩევანს გზა, ორივე არჩევანი ერთად გზითაა შესაძლებელი. სამი არჩევანისას ვწერთ .
ჯამის წესი. თუ ობიექტს ვირჩევთ ან ერთი ჯგუფიდან ( გზა), ან მეორე ჯგუფიდან ( გზა) და ჯგუფებს საერთო ობიექტი არ აქვთ, სულ გზაა.
როგორ ვიცნობთ: „და" (ორივე არჩევანი ერთად) — ვამრავლებთ; „ან" (ერთი არჩევანი ორი ჯგუფიდან) — ვკრებთ.
ფაქტორიალი. . მაგალითად, , , , . შეთანხმებით და . ფაქტორიალის შემოკლებისას ვიყენებთ : .
მაგალითი 1
მაღაზიაში 4 სახის მაისური და 3 სახის შარვალია. რამდენი კომპლექტის (ერთი მაისური და ერთი შარვალი) შედგენა შეიძლება?
ამოხსნა
- კომპლექტში მაისურიც გვჭირდება „და" შარვალიც, ამიტომ ვამრავლებთ.
- მაისურს ვირჩევთ 4 გზით და მის ყოველ არჩევანთან შარვალს — 3 გზით.
- .
პასუხი: 12
მაგალითი 2
თაროზე 5 რომანი და 7 ლექსების კრებულია. რამდენი გზით შეიძლება: (ა) ერთი წიგნის არჩევა; (ბ) ორი წიგნის არჩევა — ერთი რომანი და ერთი კრებული?
ამოხსნა
- (ა) წიგნი არის რომანი „ან" კრებული, ამიტომ ვკრებთ: .
- (ბ) ორივე წიგნი ერთად „და" გვჭირდება, ამიტომ ვამრავლებთ: .
პასუხი: (ა) 12; (ბ) 35
მაგალითი 3
რამდენი სამნიშნა რიცხვი არსებობს, რომლის ჩანაწერში არ გვხვდება ციფრები 1, 2 და 3?
ამოხსნა
- დასაშვებია 7 ციფრი: 0, 4, 5, 6, 7, 8, 9.
- პირველ ადგილზე 0 ვერ დგას (რიცხვი სამნიშნა უნდა იყოს): 6 გზა.
- მეორე და მესამე ადგილზე დასაშვებია ნებისმიერი ციფრი: თითოეულზე 7 გზა.
- ნამრავლის წესით: .
პასუხი: 294
მაგალითი 4
გამოთვალეთ: (ა) ; (ბ) ; (გ) .
ამოხსნა
- (ა) .
- (ბ) .
- (გ) ჯერ ფაქტორიალებს ვითვლით: , , ამიტომ .
პასუხი: (ა) 42; (ბ) 45; (გ) 30
მაგალითი 5
რამდენი ოთხნიშნა რიცხვია, რომელიც მარცხნიდან და მარჯვნიდან ერთნაირად იკითხება (მაგალითად, 3443)?
ამოხსნა
- ასეთი რიცხვი სახისაა: პირველი და მეოთხე ციფრი ერთნაირია, მეორე და მესამეც.
- შეიძლება იყოს 1-დან 9-მდე (0 არა): 9 გზა.
- შეიძლება იყოს 0-დან 9-მდე: 10 გზა.
- .
პასუხი: 90
შეამოწმე თავი
- 3 ქუდი და 4 შარფი გვაქვს. რამდენი კომპლექტის (ერთი ქუდი და ერთი შარფი) შედგენა შეიძლება?
- რამდენი სამნიშნა რიცხვი შეიძლება დაიწეროს ციფრებით 1, 2, 3, 4, 5, თუ ციფრები შეიძლება მეორდებოდეს?
- გამოთვალეთ .
პასუხები: 1) 12 2) 125 3) 30
§2. გადანაცვლება, წყობა, ჯუფთება
ამ ნაწილის ტერმინები (3)
- გადანაცვლება
- რამდენიმე სხვადასხვა ელემენტის ყველა შესაძლო განლაგება რიგში.მაგალითი: 3 ელემენტი რიგში წესით დგება.
- წყობა
- რამდენიმე ელემენტის არჩევა ისე, რომ არჩევის რიგს მნიშვნელობა აქვს.მაგალითი: 7 მორბენლიდან პირველ სამ ადგილზე გასვლა: წესით.
- ჯუფთება
- რამდენიმე ელემენტის არჩევა ისე, რომ რიგს მნიშვნელობა არა აქვს, მხოლოდ შემადგენლობა ითვლება.მაგალითი: 5 კაციდან 2 კაცის არჩევა: წესით.
ამოცანის ტიპს სამი კითხვა განსაზღვრავს:
- ყველა ელემენტი ლაგდება რიგში? — გადანაცვლება.
- ვირჩევთ ელემენტს -დან და რიგს მნიშვნელობა აქვს? — წყობა.
- ვირჩევთ ელემენტს -დან და რიგს მნიშვნელობა არ აქვს? — ჯუფთება.
გადანაცვლება — სხვადასხვა ელემენტის ყველა შესაძლო მიმდევრობა: . რატომ? პირველ ადგილზე გზაა, მეორეზე , ბოლო ადგილზე 1. ნამრავლის წესით . მაგალითად, -სგან მიმდევრობებია .
წყობა — ელემენტიდან ელემენტის არჩევა რიგის გათვალისწინებით: აქ მამრავლია: ადგილზე 1 გვაქვს გზა, ადგილზე 2 — და ა.შ.
ჯუფთება — ელემენტიდან ელემენტის არჩევა, რიგის გარეშე: რატომ ვყოფთ -ზე? ერთი და იგივე ელემენტი წყობებში -ჯერ მეორდება (სხვადასხვა რიგით), ჯუფთებაში კი ეს ერთი არჩევანია. მაგალითად, .
სიმეტრია: ( ელემენტის არჩევა იგივეა, რაც დარჩენილი -ის არჩევა). მაგალითად, .
გადანაცვლება გამეორებით. თუ ელემენტში ერთი სახე -ჯერ, მეორე -ჯერ და ა.შ. მეორდება, სხვადასხვა მიმდევრობების რაოდენობაა .
„მინიმუმ ერთი". ასეთ ამოცანაში ყველა არჩევანს გამოვაკლებთ ისეთებს, სადაც პირობა საერთოდ არ სრულდება.
მაგალითი 6
5 მეგობარი ერთ რიგში, 5 ადგილზე ჯდება. რამდენი წესითაა ეს შესაძლებელი: (ა) შეზღუდვის გარეშე; (ბ) თუ ორი კონკრეტული მეგობარი გვერდიგვერდ უნდა ისხდეს?
ამოხსნა
- (ა) ყველა ადამიანი ლაგდება: .
- (ბ) ორ მეგობარს ერთ ობიექტად ვთვლით. მაშინ გვაქვს 4 ობიექტი, რომელთა გადანაცვლებაა .
- ამ ორ მეგობარს ერთმანეთში ადგილების შეცვლა შეუძლია: 2 გზა.
- .
პასუხი: (ა) 120; (ბ) 48
მაგალითი 7
8 მოსწავლიდან უნდა აირჩიონ კლასის ხელმძღვანელი, მოადგილე და მდივანი (სხვადასხვა პირები). რამდენი წესით შეიძლება ამის გაკეთება?
ამოხსნა
- თანამდებობას მნიშვნელობა აქვს, ამიტომ ეს წყობაა: .
- ხელმძღვანელი 8 გზით, მოადგილე დარჩენილი 7-დან, მდივანი დარჩენილი 6-დან.
- .
პასუხი: 336
მაგალითი 8
კლუბში 5 კაცი და 6 ქალია. რამდენი წესით შეიძლება 2 კაცისა და 3 ქალის კომისიის შედგენა?
ამოხსნა
- კომისიაში რიგს მნიშვნელობა არ აქვს, ამიტომ ვიყენებთ ჯუფთებას.
- 2 კაცი 5-დან: .
- 3 ქალი 6-დან: .
- ორივე არჩევანი „და" გვჭირდება, ამიტომ ვამრავლებთ: .
პასუხი: 200
მაგალითი 9
რამდენი სხვადასხვა ექვსნიშნა რიცხვის დაწერა შეიძლება ციფრებით 1, 1, 2, 2, 2, 3 (თითოეული ციფრი იმდენჯერ, რამდენჯერაც ჩამოთვლილია)?
ამოხსნა
- ციფრები ექვსია, ამიტომ . ერთნაირ ციფრებს ერთმანეთში ადგილის გაცვლა რიცხვს არ ცვლის.
- ციფრი 1 მეორდება 2-ჯერ, ციფრი 2 — 3-ჯერ, ციფრი 3 — 1-ჯერ.
- .
პასუხი: 60
მაგალითი 10
ამოზნექილ მრავალკუთხედს 8 წვერო აქვს. იპოვეთ: (ა) რამდენი სამკუთხედის აგება შეიძლება მისი წვეროებით; (ბ) რამდენი დიაგონალი აქვს.
ამოხსნა
- (ა) სამკუთხედისთვის 3 წვეროს ვირჩევთ 8-დან, რიგი მნიშვნელობა არა აქვს: .
- (ბ) ორ წვეროს შორის მონაკვეთი სულ -ია.
- ამ 28 მონაკვეთიდან 8 გვერდია, დიაგონალი არაა: .
პასუხი: (ა) 56; (ბ) 20
მაგალითი 11
10 მოსწავლეში 4 გოგოა და 6 ბიჭი. რამდენი წესით შეიძლება 3 მოსწავლის არჩევა ისე, რომ მათ შორის ერთი გოგო მაინც იყოს?
ამოხსნა
- 3 მოსწავლის არჩევის ყველა გზა: .
- „ერთი გოგო მაინც" საწინააღმდეგოა პირობისა „გოგო არცერთი": სამივე ბიჭია, .
- .
პასუხი: 100
მაგალითი 12
სიმრავლის ორელემენტიან ქვესიმრავლეთა რაოდენობა 36-ის ტოლია. რამდენი სამელემენტიანი ქვესიმრავლე აქვს სიმრავლეს?
ამოხსნა
- ვთქვათ -ში ელემენტია. მაშინ .
- . რიცხვი 72 წარმოდგება როგორც , ამიტომ .
- .
პასუხი: 84
შეამოწმე თავი
- 6 ადამიანი ერთ რიგში დგება. რამდენი წესით შეიძლება ამის გაკეთება?
- 10 ადამიანი ერთმანეთს ხელს ართმევს (ყოველი ორი ადამიანი ერთხელ). რამდენი ხელის ჩამორთმევაა?
- 7 მორბენალი მონაწილეობს შეჯიბრში. რამდენი სხვადასხვა გზით შეიძლება დაიკავონ პირველი, მეორე და მესამე ადგილი?
პასუხები: 1) 720 2) 45 3) 210
§3. ნიუტონის ბინომი და პასკალის სამკუთხედი
ამ ნაწილის ტერმინები (4)
- ბინომიალური კოეფიციენტი
- რიცხვი , რომელიც ნიუტონის ბინომის გაშლაში წევრის წინ დგას.მაგალითი: -ში წევრის კოეფიციენტია .
- ნიუტონის ბინომი
- ფორმულა, რომლითაც ორი წევრის ჯამის ხარისხს ვშლით წევრებად.მაგალითი: ; .
- პასკალის სამკუთხედი
- რიცხვების სამკუთხა ცხრილი, სადაც ყოველი რიცხვი ზემოთ მდგომი ორი რიცხვის ჯამია.მაგალითი: მე-4 ხაზია 1, 4, 6, 4, 1, რადგან და .
- ხე
- ბმული გრაფი, რომელშიც ციკლი არ არის.მაგალითი: ხეს 9 წვეროთი წიბო აქვს.
ნიუტონის ბინომის ფორმულა: გაშლას წევრი აქვს. რიცხვებს ბინომიალური კოეფიციენტები ჰქვია. -ე წევრია
რატომ? ერთნაირი ფრჩხილის ნამრავლია. წევრი მიიღება, როცა ზუსტად ფრჩხილიდან ავიღებთ -ს. ამ ფრჩხილს ვირჩევთ გზით. მაგალითად, -ში -ს კოეფიციენტია .
პასკალის სამკუთხედი. ყოველი რიცხვი ზემოთ მდგომი ორი რიცხვის ჯამია; ხაზი ნომრით -ის კოეფიციენტებს შეიცავს:
| კოეფიციენტები | |
|---|---|
| 0 | 1 |
| 1 | 1 1 |
| 2 | 1 2 1 |
| 3 | 1 3 3 1 |
| 4 | 1 4 6 4 1 |
| 5 | 1 5 10 10 5 1 |
| 6 | 1 6 15 20 15 6 1 |
თვისებები:
- და .
- პასკალის წესი: (მაგალითად, ).
- ჯამი: (ეს -ია). ესაა -ელემენტიანი სიმრავლის ქვესიმრავლეების რაოდენობაც.
- ყველა კოეფიციენტის ჯამის საპოვნელად გამოსახულებაში ცვლადის ნაცვლად 1-ს ვწერთ.
მაგალითი 13
გაშალეთ: (ა) ; (ბ) .
ამოხსნა
- (ა) მე-4 ხაზი პასკალის სამკუთხედში: 1, 4, 6, 4, 1. ამიტომ .
- (ბ) აქ , და . კოეფიციენტები 1, 3, 3, 1.
- .
- ; ; .
- .
პასუხი: (ა) ; (ბ)
მაგალითი 14
იპოვეთ -ის კოეფიციენტი -ის გაშლაში.
ამოხსნა
- ზოგადი წევრი: .
- -სთვის , ე.ი. .
- .
- შემოწმება პასკალის სამკუთხედით: მე-5 ხაზში მესამე რიცხვია 10; .
პასუხი: 80
მაგალითი 15
(ა) -ის გაშლაში -თან მდგომი კოეფიციენტი 66-ია. იპოვეთ . (ბ) იპოვეთ -ის კოეფიციენტი -ის გაშლაში.
ამოხსნა
- (ა) არის წევრი -ისთვის, ამიტომ .
- , . რიცხვი 132 არის , ამიტომ .
- (ბ) . -სთვის , ე.ი. .
- .
პასუხი: (ა) ; (ბ) 180
მაგალითი 16
იპოვეთ თავისუფალი წევრი (წევრი, რომელშიც არ არის) -ის გაშლაში.
ამოხსნა
- ზოგადი წევრი: .
- არ უნდა დარჩეს: , ე.ი. .
- .
პასუხი: 20
მაგალითი 17
(ა) იპოვეთ -ის გაშლაში ყველა კოეფიციენტის ჯამი. (ბ) რამდენი ქვესიმრავლე აქვს 6-ელემენტიან სიმრავლეს?
ამოხსნა
- (ა) კოეფიციენტების ჯამის საპოვნელად ვწერთ : .
- (ბ) ქვესიმრავლეთა რაოდენობაა .
პასუხი: (ა) 16; (ბ) 64
მაგალითი 18
იპოვეთ , თუ .
ამოხსნა
- პასკალის წესით .
- შემოწმება: , , ჯამი 715; .
- სიმეტრიით , ამიტომ ან .
პასუხი: ან
შეამოწმე თავი
- იპოვეთ -ის კოეფიციენტი -ის გაშლაში.
- -ის გაშლაში რამდენი წევრია და რას უდრის -ის კოეფიციენტი?
- იპოვეთ -ის კოეფიციენტი -ის გაშლაში.
პასუხები: 1) 135 2) 8 წევრი; 21 3) 40
§4. გრაფი: ძირითადი ცნებები
ამ ნაწილის ტერმინები (6)
- ბმული გრაფი
- გრაფი, რომელშიც ნებისმიერი ორი წვეროდან მეორემდე მარშრუტით მისვლა შეიძლება.მაგალითი: ორი ცალკეული სამკუთხედი ბმული არაა: ერთიდან მეორეში ვერ გადავალთ.
- გრაფი
- წერტილების (წვეროების) და მათ შორის ხაზების (წიბოების) სქემა.მაგალითი: ხუთი ქალაქი და მათ შორის არსებული გზები გრაფს ქმნის: 5 წვერო და გზათა რაოდენობის ტოლი წიბო.
- მარშრუტი
- წვეროების და მათ შემაერთებელი წიბოების მიმდევრობა, რომლითაც გრაფში ვიმოძრავებთ.მაგალითი: მარშრუტი სამი წიბოსგან შედგება: , , ; სიგრძე 3-ია.
- ციკლი
- ჯაჭვი, რომელიც იმავე წვეროში მთავრდება, საიდანაც დაიწყო, და სხვა წვერო არ მეორდება.მაგალითი: სამკუთხედის ციკლია, სიგრძე 3-ია.
- წვეროს ხარისხი
- რამდენი წიბო გადის ამ წვეროზე.მაგალითი: თუ წვეროს სამი წიბო ერთვის, .
- ჯაჭვი
- მარშრუტი, რომელშიც ერთი და იგივე წიბო ორჯერ არ გადის.მაგალითი: მარშრუტი ჯაჭვი არაა, რადგან წიბო ორჯერ გადის.
გრაფი — წვეროების სიმრავლე და წვეროთა წყვილების შემაერთებელი წიბოები. წვეროს წერტილით ვხატავთ, წიბოს — ხაზით. მნიშვნელობა აქვს მხოლოდ იმას, რომელი წვეროებია შეერთებული; ხაზის სიგრძე და ფორმა არა.
- ორი წვერო მოსაზღვრეა, თუ მათ წიბო აერთებს. ორი წიბო მოსაზღვრეა, თუ საერთო წვერო აქვს. წვერო და წიბო ინციდენტურია, თუ წვერო ამ წიბოს ბოლოა.
- მარყუჟი — წიბო, რომელიც წვეროს თავის თავთან აერთებს.
- ორიენტირებულ გრაფში წიბოს მიმართულება აქვს (ასეთ წიბოს რკალი ჰქვია); არაორიენტირებულში მიმართულება არ არის.
- წვეროს ხარისხი — მასზე გამავალი წიბოების რაოდენობა (მარყუჟი 2-ად ითვლება). კენტი ხარისხის წვეროს კენტი, ლუწი ხარისხისას ლუწი წვერო ჰქვია.
- მარშრუტი — წვეროებისა და წიბოების მიმდევრობა, სადაც ყოველი წიბო წინა და შემდეგ წვეროს აერთებს. მარშრუტის სიგრძე — მასში წიბოების რაოდენობა (წვეროების არა).
- ჯაჭვი — მარშრუტი, რომელშიც წიბო არ მეორდება. მარტივი ჯაჭვი — ჯაჭვი, რომელშიც წვეროც არ მეორდება. ციკლი — ჯაჭვი, რომელიც იმავე წვეროში მთავრდება, საიდანაც დაიწყო, და სხვა წვერო არ მეორდება.
- ბმული გრაფი — ნებისმიერ ორ წვეროს შორის მარშრუტი არსებობს.
ხარისხთა ჯამი. ყოველ წიბოს ორი ბოლო აქვს, ამიტომ წიბო ხარისხთა ჯამში ორჯერ ითვლება: შედეგად კენტი წვეროების რაოდენობა ყოველთვის ლუწია (კენტი რიცხვების ჯამი ლუწია მხოლოდ მაშინ, როცა ამ რიცხვების რაოდენობა ლუწია).
სრული გრაფი : წვეროა და ყოველი ორი წვერო შეერთებულია. წიბოების რაოდენობაა , ყოველი წვეროს ხარისხი კი .
ქვემოთ გამოვიყენებთ გრაფს : წვეროებია ; წიბოებია , , , , .
მაგალითი 19
იპოვეთ გრაფის ყველა წვეროს ხარისხი, წიბოების რაოდენობა და კენტი წვეროების რაოდენობა.
ამოხსნა
- -ზე გადის , : . -ზე გადის , : .
- -ზე გადის , , : . -ზე გადის , : . -ზე გადის : .
- ხარისხთა ჯამი: . ამიტომ , (სიაშიც 5 წიბოა).
- კენტია და : 2 წვერო.
პასუხი: ხარისხები 2, 2, 3, 2, 1; ; კენტი წვერო 2-ია
მაგალითი 20
გრაფში განსაზღვრეთ თითოეული მარშრუტის სიგრძე და სახე (მარტივი ჯაჭვი, ციკლი ან უბრალოდ მარშრუტი): (ა) ; (ბ) ; (გ) .
ამოხსნა
- (ა) წიბოებია . სიგრძე 4. წიბოც და წვეროც არ მეორდება: მარტივი ჯაჭვია.
- (ბ) წიბოებია . სიგრძე 5. წიბო ორჯერ გადის, ამიტომ ჯაჭვი არაა — უბრალოდ მარშრუტია.
- (გ) წიბოებია . სიგრძე 3. წიბო არ მეორდება, იწყება და მთავრდება -ში: ციკლია.
პასუხი: (ა) 4, მარტივი ჯაჭვი; (ბ) 5, მარშრუტი; (გ) 3, ციკლი
მაგალითი 21
(ა) 7 ადამიანიდან თითოეული ზუსტად 3 ადამიანს იცნობს. შესაძლებელია ეს? (ბ) გრაფის წვეროთა ხარისხებია 4, 3, 3, 2, 2, 2. რამდენი წიბო აქვს გრაფს?
ამოხსნა
- (ა) ადამიანები წვეროებია, ნაცნობობა — წიბო. ხარისხთა ჯამი იქნებოდა .
- ხარისხთა ჯამი ლუწია, 21 კი კენტია. ამიტომ ეს შეუძლებელია.
- (ბ) .
- , .
პასუხი: (ა) შეუძლებელია; (ბ) 8
მაგალითი 22
(ა) 6 წვეროიან სრულ გრაფში რამდენი წიბოა და რა ხარისხისაა თითოეული წვერო? (ბ) 5 გუნდი ერთმანეთთან თითო მატჩს თამაშობს. რამდენი მატჩი ტარდება?
ამოხსნა
- (ა) -ში ყოველი წვერო დანარჩენ წვეროსთანაა შეერთებული: ხარისხი 5.
- წიბოები: . შემოწმება ხარისხთა ჯამით: , .
- (ბ) გუნდები წვეროებია, მატჩი — წიბო: . .
პასუხი: (ა) 15 წიბო, ხარისხი 5; (ბ) 10 მატჩი
შეამოწმე თავი
- გრაფის წვეროთა ხარისხებია 4, 4, 3, 3, 2. რამდენი წიბო აქვს გრაფს?
- რამდენი წიბო აქვს 8 წვეროიან სრულ გრაფს?
- 10 წვეროიანი გრაფის ყოველი წვეროს ხარისხი 3-ია. რამდენი წიბო აქვს გრაფს?
პასუხები: 1) 8 2) 28 3) 15
§5. გრაფის მოცემის ხერხები და იზომორფიზმი
ამ ნაწილის ტერმინები (3)
- იზომორფული გრაფები
- ორი გრაფი, რომელთაგან ერთის წვეროების გადანომვრით მეორე მიიღება.მაგალითი: ორი ოთხკუთხედი დიაგონალით იზომორფულია, თუ წვეროებს ისე შევუსაბამებთ, რომ წიბოები წიბოებს ემთხვევა.
- ინციდენტურობის ცხრილი
- ცხრილი, რომლის სტრიქონები წვეროებია, სვეტები — წიბოები, და 1 აჩვენებს, რომელი წვეროა ამ წიბოს ბოლო.მაგალითი: 4 წვეროსა და 5 წიბოს შემთხვევაში ცხრილი -ია და მასში ერთიანია.
- მოსაზღვრეობის ცხრილი
- კვადრატული ცხრილი, რომელიც გვიჩვენებს, რომელი წვეროებია ერთმანეთთან შეერთებული.მაგალითი: 4 წვეროიანი გრაფისთვის ცხრილი -ია; -სა და -ს შორის წიბოა, თუ უჯრაში 1 წერია.
გრაფი სამი ხერხით შეიძლება მივცეთ. ქვემოთ ვიყენებთ გრაფს : წვეროებია ; წიბოებია , , , .
- მოსაზღვრეობის ცხრილი — კვადრატული ცხრილი ( წვეროების რაოდენობაა). სტრიქონისა და სვეტის გადაკვეთაზე წერია წვეროებს და შორის წიბოების რაოდენობა. არაორიენტირებული გრაფის ცხრილი სიმეტრიულია. სტრიქონის რიცხვების ჯამი წვეროს ხარისხია (მარყუჟის გარეშე); ყველა რიცხვის ჯამი -ია.
- ინციდენტურობის ცხრილი — სტრიქონები წვეროებია, სვეტები — წიბოები (ზომა ). უჯრაში 1 წერია, თუ წვერო ამ წიბოს ბოლოა, და 0 — სხვა შემთხვევაში. ყოველ სვეტში ორი ერთიანია.
- სია — ყოველი წვეროსთვის ჩამოვწერთ მისი მოსაზღვრე წვეროებს.
იზომორფული გრაფები — ისეთი გრაფები, რომელთა წვეროები შეიძლება ისე შევუსაბამოთ ერთმანეთს (ურთიერთცალსახად), რომ მოსაზღვრე წვეროები მოსაზღვრე წვეროებს შეესაბამებოდეს. ანუ ერთი გრაფის წვეროების გადანომვრით მეორე მიიღება. იზომორფულ გრაფებში ერთნაირია წვეროების რაოდენობა, წიბოების რაოდენობა და ხარისხთა ნაკრები. ეს პირობები აუცილებელია, მაგრამ საკმარისი არა.
მაგალითი 23
შეადგინეთ გრაფის მოსაზღვრეობის ცხრილი.
ამოხსნა
- ვწერთ 1-ს ყოველ წყვილზე, რომელიც წიბოთია შეერთებული: , , , ; დანარჩენ უჯრებში 0-ს.
- ცხრილი სიმეტრიულია, მთავარ დიაგონალზე 0-ებია (მარყუჟი არ არის).
| ჯამი | |||||
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 2 | |
| 1 | 0 | 1 | 0 | 2 | |
| 1 | 1 | 0 | 1 | 3 | |
| 0 | 0 | 1 | 0 | 1 |
- სტრიქონების ჯამები 2, 2, 3, 1 წვეროთა ხარისხებია.
პასუხი: ცხრილი ზემოთაა; ხარისხები 2, 2, 3, 1
მაგალითი 24
შეადგინეთ გრაფის ინციდენტურობის ცხრილი.
ამოხსნა
- 4 წვეროა და 4 წიბო, ამიტომ ცხრილი 4 სტრიქონისა და 4 სვეტისაა.
- სვეტში 1-ები დგას და სტრიქონებში; : , ; : , ; : , .
| 1 | 1 | 0 | 0 | |
| 1 | 0 | 1 | 0 | |
| 0 | 1 | 1 | 1 | |
| 0 | 0 | 0 | 1 |
- შემოწმება: ყოველ სვეტში 1-ების ჯამი 2-ია; სტრიქონების ჯამებია 2, 2, 3, 1 (ხარისხები).
პასუხი: ცხრილი ზემოთაა
მაგალითი 25
გრაფი მოცემულია მოსაზღვრეობის ცხრილით (წვეროები ): სტრიქონები , , , . იპოვეთ წიბოები, წვეროთა ხარისხები და წიბოების რაოდენობა.
ამოხსნა
- სტრიქონი : 1-ებია , , სვეტებში, ე.ი. წიბოები , , .
- სტრიქონი : 1-ებია და სვეტებში; ახალი წიბოა (დანარჩენი უკვე გვაქვს). სტრიქონები და ახალ წიბოს არ იძლევა.
- წიბოებია , , , : .
- სტრიქონების ჯამები: . ყველა რიცხვის ჯამი .
პასუხი: წიბოები ; ხარისხები 3, 2, 1, 2;
მაგალითი 26
დაამტკიცეთ, რომ გრაფები იზომორფულია. გრაფი : წვეროები , წიბოები . გრაფი : წვეროები , წიბოები .
ამოხსნა
- ორივეში 4 წვეროა და 5 წიბო. ხარისხები -ში: , , , . -ში: , , , .
- სამხარისხიან წვეროებს ვაწყვილებთ: , ; დანარჩენ ორ წვეროს — , .
- წიბოები გადადის: , , , , . ესენი -ის ყველა 5 წიბოა.
- შესაბამისობა მოსაზღვრეობას ინარჩუნებს, ამიტომ გრაფები იზომორფულია.
პასუხი: იზომორფულია: , , ,
მაგალითი 27
გრაფი 6 წვეროს მარტივი ციკლია (წიბოები ). გრაფი ორი სამკუთხედია (წიბოები და ). იზომორფულია თუ არა ისინი?
ამოხსნა
- ორივეში 6 წვეროა და 6 წიბო, ყოველი წვეროს ხარისხი 2-ია.
- განვიხილოთ ბმულობა. ბმულია: ნებისმიერი ორი წვეროს შორის მარშრუტი არსებობს.
- ბმული არაა: 1-დან 4-მდე მარშრუტი არ არსებობს.
- იზომორფულ გრაფებში ბმულობაც ერთნაირი უნდა იყოს, ამიტომ და იზომორფული არაა.
პასუხი: არა
შეამოწმე თავი
- გრაფი მოცემულია სიით: : ; : ; : ; : . რამდენი წიბო აქვს?
- გრაფს 5 წვერო და 7 წიბო აქვს. რა ზომისაა მისი ინციდენტურობის ცხრილი და რამდენი 1-ია მასში?
- გრაფის წვეროთა ხარისხებია 2, 2, 2, 2, ხოლო -ისა — 3, 1, 1, 1. იზომორფულია ისინი?
პასუხები: 1) 3 2) ; 14 ერთიანი 3) არა
§6. ხე, ბრტყელი გრაფი, გრაფის შემოვლა
ამ ნაწილის ტერმინები (2)
- გრაფის შემოვლა
- მარშრუტი, რომელიც გრაფის ყველა წიბოს ზუსტად ერთხელ გადის.მაგალითი: გრაფს 2 კენტი წვეროთი შემოვლა აქვს: ერთი მათგანიდან იწყება, მეორეში მთავრდება.
- ეილერის მახასიათებელი
- რიცხვი (წვეროები მინუს წიბოები პლუს წახნაგები) ბრტყელი გრაფისთვის; ის ყოველთვის 2-ია.მაგალითი: კუბის ჩონჩხისთვის .
ხე — ბმული გრაფი ციკლის გარეშე. წვეროიან ხეს ზუსტად წიბო აქვს. რატომ? ხეს ვაგებთ ერთი წვეროდან: ყოველ ახალ წვეროს ერთი წიბოთი ვამატებთ (ორი წიბო ციკლს მოგვცემდა).
ბრტყელი გრაფი — სიბრტყეზე ისე დახაზული გრაფი, რომ წიბოები მხოლოდ წვეროებში იკვეთება. ასეთი გრაფი სიბრტყეს წახნაგებად ყოფს; გარე, უსასრულო უბანიც წახნაგია. ბრტყელი ბმული გრაფისთვის ეილერის მახასიათებელი (რიცხვი ) ყოველთვის 2-ია: სადაც წვეროების, წიბოების და წახნაგების (გარე უბნითურთ) რაოდენობაა. შემოწმება ხეზე: , , ამიტომ .
გრაფის შემოვლა (უნიკურსალურობა) — ისეთი მარშრუტი, რომელიც ყოველ წიბოს ზუსტად ერთხელ გადის. ბმული გრაფის შემოვლა შესაძლებელია მაშინ და მხოლოდ მაშინ, თუ კენტი წვეროების რაოდენობა ორს არ აღემატება (0 ან 2).
- თუ კენტი წვერო არაა, შემოვლა ერთსა და იმავე წვეროში იწყება და მთავრდება.
- თუ კენტი წვერო ორია, შემოვლა ერთ მათგანში იწყება და მეორეში მთავრდება.
- ორზე მეტი კენტი წვეროს შემთხვევაში შემოვლა შეუძლებელია.
რატომ? შუალედურ წვეროში ყოველ შესვლას ერთი გასვლა მოსდევს, ამიტომ იქ წიბოები წყვილებადაა და ხარისხი ლუწია. კენტი ხარისხი შეიძლება მხოლოდ სასტარტო და ბოლო წვეროს ჰქონდეს.
მაგალითი 28
(ა) ხეს 9 წვერო აქვს. რამდენი წიბო აქვს? (ბ) ხეს 12 წიბო აქვს. რამდენი წვერო აქვს?
ამოხსნა
- (ა) წვეროიან ხეს წიბო აქვს: .
- (ბ) , ამიტომ .
პასუხი: (ა) 8; (ბ) 13
მაგალითი 29
ხეს 5 წვერო აქვს. ოთხი წვეროს ხარისხია 3, 1, 1, 1. იპოვეთ მეხუთე წვეროს ხარისხი.
ამოხსნა
- 5 წვეროიან ხეს წიბო აქვს.
- ხარისხთა ჯამი .
- ცნობილი ხარისხების ჯამია .
- მეხუთე წვეროს ხარისხი: .
პასუხი: 2
მაგალითი 30
(ა) კუბის ჩონჩხს 8 წვერო და 12 წიბო აქვს. რამდენ წახნაგად ყოფს იგი სიბრტყეს (გარე წახნაგითურთ)? (ბ) ბრტყელ ბმულ გრაფს 7 წვერო და 5 წახნაგი აქვს. რამდენი წიბო აქვს?
ამოხსნა
- (ა) ეილერის ფორმულა: . ვსვამთ: .
- . შემოწმება: კუბს 6 წახნაგი აქვს.
- (ბ) , ე.ი. .
- .
პასუხი: (ა) 6; (ბ) 10
მაგალითი 31
შეიძლება თუ არა შემდეგი ბმული გრაფის ერთი შემოვლა: (ა) წიბოებია ; (ბ) წიბოებია ? თუ შეიძლება, მიუთითეთ შემოვლა.
ამოხსნა
- (ა) ხარისხები: , , , , . კენტი წვერო არ არის (0), ამიტომ შემოვლა შესაძლებელია და იმავე წვეროში მთავრდება.
- მაგალითად, : წიბოებია — ყველა 6 წიბო ერთხელ.
- (ბ) ხარისხები: (), (), , , . კენტი წვერო ორია: და . შემოვლა შესაძლებელია: იწყება -ში, მთავრდება -ში.
- მაგალითად, : წიბოებია — ყველა 6 წიბო ერთხელ.
პასუხი: (ა) შესაძლებელია; (ბ) შესაძლებელია
მაგალითი 32
ქალაქში 4 ადგილია (ორი ნაპირი და ორი კუნძული) და 7 ხიდი. ერთი ადგილიდან 5 ხიდი გადის, დანარჩენი სამიდან — თითო 3 ხიდი. შეიძლება თუ არა ყველა ხიდზე ზუსტად ერთხელ გავიდეთ? (წვეროები ადგილებია, წიბოები — ხიდები.)
ამოხსნა
- წვეროების ხარისხებია 5, 3, 3, 3 (ჯამი — 7 ხიდი).
- კენტი წვეროების რაოდენობაა 4.
- , ამიტომ შემოვლა შეუძლებელია.
პასუხი: შეუძლებელია
მაგალითი 33
შესაძლებელია თუ არა სრული გრაფების -ისა და -ის შემოვლა?
ამოხსნა
- -ში ყოველი წვეროს ხარისხია , გრაფი ბმულია.
- : ყოველი ხარისხია 4 (ლუწი), კენტი წვერო 0-ია. შემოვლა შესაძლებელია.
- : ყოველი ხარისხია 3 (კენტი), კენტი წვერო 4-ია. შემოვლა შეუძლებელია.
პასუხი: -ისთვის შესაძლებელია; -ისთვის — არა
შეამოწმე თავი
- ხეს 15 წვერო აქვს. რამდენი წიბო აქვს?
- ბრტყელ ბმულ გრაფს 10 წვერო და 15 წიბო აქვს. რამდენი წახნაგი აქვს (გარე წახნაგითურთ)?
- შეიძლება თუ არა სრული გრაფის შემოვლა?
პასუხები: 1) 14 2) 7 3) არა
მოკლედ
- ნამრავლის წესი („და"): ; ჯამის წესი („ან"): ; ; .
- (ყველა ელემენტი ლაგდება); (რიგი მნიშვნელოვანია); (რიგი უმნიშვნელოა).
- გამეორებით: ; „მინიმუმ ერთი" = ყველა არცერთი.
- ; ; .
- -ის ზოგადი წევრი ; გაშლას წევრი აქვს; კოეფიციენტების ჯამი — ცვლადის ადგილას 1.
- გრაფი: ; კენტი წვეროების რაოდენობა ლუწია; -ს წიბო აქვს; მარშრუტის სიგრძე — წიბოების რაოდენობაა.
- მოსაზღვრეობის ცხრილი (ყველა რიცხვის ჯამი ); ინციდენტურობის ცხრილი (ყოველ სვეტში ორი 1); იზომორფულ გრაფებს ერთნაირი აქვთ წვეროები, წიბოები, ხარისხები, ბმულობა.
- ხეს წიბო აქვს; ბრტყელი ბმული გრაფისთვის (გარე წახნაგითურთ).
- ბმული გრაფის შემოვლა შესაძლებელია, თუ კენტი წვეროები 0 ან 2-ია.