Графи: преброяване на ребрата и върховете
Изтегляне 22 Kb.
|
- Навигация на страницата:
- 8 . Лема (за ръкостисканията).
Графи:преброяване на ребрата и върховетеОпределение 1. Ще казваме, че е зададен граф, ако е зададено множеството от неговите върхове и за всяка двойка от тези върхове е казано, дали те са свързани с ребро или не (ще разглеждаме само двойки от по два различни върха). Примери. а) Граф на познанствата: върховете са учениците, ребрата – приятелствата; б) Карта: върховете са страните (държавите), а ребрата – двойките страни с общ граничен участък; в) градовете и пътищата; г) Граф (шахм.) на царя (на офицера, топа, дамата, …): върховете са клетките, ребрата – двойките клетки, при които от едната царят (офицерът, топът, дамата, …) може да минава в другата за един ход. 1. а) Върховете и ребрата на граф – това са върховете и ръбовете на куб. Нарисувайте този граф така, че ребрата му да не се пресичат. Колко са върховете и ребрата в този граф? Напишете за всеки връх неговата степен и намерете сумата на степените на всички върхове. б) Върховете на граф – това са клетките на дъска 2  3, а ребрата – ходовете на топа. Нарисувайте този граф така, че неговите ребра да не се пресичат. Колко са в този граф върховете и ребрата? Напишете за всеки връх неговата степен и намерете сумата на степените на всички върхове.
2. а) Нарисувайте граф с 4 върха, в който всяка двойка върхове е свързана с ребро. Колко са ребрата? Може ли да нарисувате графа така, че ребрата да не се пресичат? Напишете до всеки връх неговата степен и намерете сумата на степените. б) Нарисувайте граф с 5 върха, в който има възможно най-много ребра. Колко е броят на тези ребра? Нарисувайте този граф така, че да има възможно най-малко пресичания на ребрата. Напишете до всеки връх неговата степен и намерете сумата на степените. 3. Колко е най-голямата степен на връх в графа а) офицерът на дъска 8 8;
б) дамата на дъска 8 8?
4. Колко са ребрата в граф „Царят на дъска 4 4“?
5. (Лема) Сумата от степените на всички върхове е равна на удвоения брой на ребрата. 6. а) В граф има 12 върха, от които 3 върха имат степен 3, 4 върха – степен 4 и 5 върха – степен 5. Колко са в него ребрата? б) В 13-ъгълник построили 30 диагонала, като при това от 3 върха излизат по 3 диагонала, от 4 върха – по 4 диагонала и от 5 върха – по 5 диагонала. Колко диагонали излизат от последния връх? в) В една страна от всяко летище летят точно по 6 авиолинии до други летища в страната, а всичко авиолиниите между двойките летища са общо 30. Колко летища има в тази страна? 7. В един клас има 15 човека. Може ли 4 от учениците в него да имат точно по 4 приятели всеки, 5 от учениците – по 5 приятели и 6 от учениците – по 6 приятели? 8. Лема (за ръкостисканията). В граф броят на върховете с нечетна степен е четен. 9. Може ли да се поставят на масата 7 монети така, че всяка от тях да се допира до точно три от другите? 10. Борис един по един поставя царе върху шахматна дъска, записвайки за всеки колко от по-рано поставените царе той може да вземе. Дъската се запълнила. Докажете, че сборът на записаните числа не зависи от реда, по който са поставени. Колко е този сбор? Лозенец, 5-6 класс, 16 август 2018 г, г http://www.ashap.info/Uroki/Burgas/2018/56.html Каталог: Uroki -> Burgas -> Burgas18 Uroki -> Свържете се с графа Burgas18 -> Задача била решена от по 5 ученика. Колко са били учениците, ако общо задачите са били 15? Burgas -> 0. Около кръг с радиус r е описан многоъгълник с периметър Р. Намерете лицето на многоъгълник Изтегляне 22 Kb. Сподели с приятели:
|