Графи: преброяване на ребрата и върховете



Дата24.10.2018
Размер21.77 Kb.

Графи:преброяване на ребрата и върховете


Определение 1. Ще казваме, че е зададен граф, ако е зададено множеството от неговите върхове и за всяка двойка от тези върхове е казано, дали те са свързани с ребро или не (ще разглеждаме само двойки от по два различни върха).

Примери. а) Граф на познанствата: върховете са учениците, ребрата – приятелствата; б) Карта: върховете са страните (държавите), а ребрата – двойките страни с общ граничен участък; в) градовете и пътищата; г) Граф (шахм.) на царя (на офицера, топа, дамата, …): върховете са клетките, ребрата – двойките клетки, при които от едната царят (офицерът, топът, дамата, …) може да минава в другата за един ход.
1. а) Върховете и ребрата на граф – това са върховете и ръбовете на куб. Нарисувайте този граф така, че ребрата му да не се пресичат. Колко са върховете и ребрата в този граф? Напишете за всеки връх неговата степен и намерете сумата на степените на всички върхове.

б) Върховете на граф – това са клетките на дъска 23, а ребрата – ходовете на топа. Нарисувайте този граф така, че неговите ребра да не се пресичат. Колко са в този граф върховете и ребрата? Напишете за всеки връх неговата степен и намерете сумата на степените на всички върхове.

2. а) Нарисувайте граф с 4 върха, в който всяка двойка върхове е свързана с ребро. Колко са ребрата? Може ли да нарисувате графа така, че ребрата да не се пресичат? Напишете до всеки връх неговата степен и намерете сумата на степените.

б) Нарисувайте граф с 5 върха, в който има възможно най-много ребра. Колко е броят на тези ребра? Нарисувайте този граф така, че да има възможно най-малко пресичания на ребрата. Напишете до всеки връх неговата степен и намерете сумата на степените.

3. Колко е най-голямата степен на връх в графа

а) офицерът на дъска 88;

б) дамата на дъска 88?

4. Колко са ребрата в граф „Царят на дъска 44“?

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


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница