Свържете се с графа



Дата15.10.2018
Размер21.66 Kb.

СВЪРЖЕТЕ СЕ С ГРАФА

1. Даден е модел на куб от арматура (т.е., ръбовете на куба са направени от арматура). Колко най-много ръба можем да премахнем така, че арматурата да не се разпадне на части?





2. От кибритени клечки е направена шахматна дъска 88, като страната на едно квадратче е една клечка (виж рис. 4). Бръмбар иска от произволна клетка да може да премине до всяка друга клетка без да пропълзява над клечка и без да излиза от пределите на дъската. Колко най-малко клечки трябва да премахнем, ако не можем да премахваме гранични клечки?

3. Колко най-малко клечки трябва да премахнем от дъската в зад.2 така, че от всяка клетка да може бръмбарът да отиде до границите на квадратната дъска?

4. На лист от тетрадка с квадратчета е начертан многоъгълник с лице n единични клетки. Контурът на многоъгълника е по линиите на квадратчетата на листа. Колко най-много може да бъде периметъра на многоъгълника?

5. Даден е клетъчен правоъгълник m×n. Всяка от неговите клетки е разрязана по един от диагоналите. На колко най-малко части може да се разпадне правоъгълникът?

Теорема за свързаност на граф:

Даден е свързан граф с n върха. Следователно в него има не по-малко от n–1 ребра.



Нека граф с с n върха се разпада на с свързани компоненти. Следователно в него има не по-малко от nc ребра.

6. а) Може ли ръбовете на куба да се оцветят в два цвята така, че между произволни два върха да има едноцветен път по ръбовете, както от единия, така и от другия цвят?
б) Дадена е квадратна мрежа 1010. Може ли във всяка клетка да се построи диагонал и да се оцветят страните и този диагонал на клетката в 3 цвята така, че от всеки връх на клетка до произволен друг връх да има едноцветен път по страните и диагоналите, както от единия, така и от другия, така и от третия цвят?

7. Лист от тетрадка на квадратчета оцветили (по клетки) в 23 цвята(при това всеки цвят присъства). Двойка цветове се нарича „ добра“ , ако съществуват две съседни клетки, оцветени в тези два цвята. Колко най-малко „ добри“ двойки има?

8. Домакиня изпекла за гостите си пица. На масата може да седнат или p гости, или q (p и q взаимно прости). На колко най-малко парчета (не задължително еднакви) тя трябва да разреже предварително пицата така, че във всеки от случаите да може да им раздаде по равен брой парчета?
9. Колко най-много клетки от дъска 99 може да се разрежат и по двата диагонала така, че дъската да не се разпадне на няколко части?

10. Квадратна мрежа 88 разрязали по линиите на три многоъгълника с равни периметри. Намерете най-голямата възможна стойност на този периметър.

Бургас, 9-10 класс, 21 июля 2016 г, www.ashap.info/Uroki/Bolgar/Burgas16/index.html


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

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