Задача била решена от по 5 ученика. Колко са били учениците, ако общо задачите са били 15?



Дата22.10.2018
Размер19.77 Kb.

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



Преброяване по два начина

1. а) В една игра всеки ученик решил по 3 задачи, а всяка задача била решена от по 5 ученика. Колко са били учениците, ако общо задачите са били 15?

б) В двуделен граф има 35 ребра. На колко е равна сумата от степените на черните върхове? А на белите?

2. В град Пятёркин всяка улица свързва два площада, а от всеки площад излизат по 5 улици. Докажете, че броят на площадите е четно число, а броят на улиците се дели на 5.

3. В един клас всяко момче дружи с три момичета, а всяко момиче – с четири момчета. 17 от децата обичат да играят математически боеве, а освен това в класната стая има 13 маси, на всяка от които седят 1 или 2 ученика. Колко са учениците в този клас?

Степени и свързаност

Определение. Един граф се нарича свързан, ако от кой да е негов връх може да се стигне по ребрата до всички други върхове.

4. Свързан граф ли е „Конят“
а) на дъска 33;
б) на дъска 44?

Определение Всеки граф се разпада на свързани парчета, които се наричат компоненти на свързаност (свързаният граф се състои от една компонента).

5. Колко най-малко компоненти на свързаност може да има в граф със 7 върха? А най-много?

6. а) В кръг растат 12 водни линии. Жаба може да скача през 3 празни водни лилии върху 4-тата. Ще считаме водните лилии за върхове на граф, а скоковете – за ребра на този граф. Колко са компонентите на свързаност в този граф?
б) А ако водните лилии са 9?
в) А ако водните лилии са 10?

7. В един граф изтрили едно ребро. Как може да се промени броят на компонентите на свързаност?

8. (Теорема) Нека е даден граф с N върха.
а) Ако графът е свързан, то в него има не по-малко от N-1 ребра.
б) Ако в графа има K компоненти на свързаност, то в него има не по-малко от N-K ребра.

9. От конструкцията на куб прерязали 8 ръба. Докажете, че конструкцията ще се разпадне на части.

10. От кибритени клечки е направен голям квадрат, състоящ се от 64 квадратни клетки със страна 1 клечка.
а) В лявата долна клетка стои бръмбар, който не може да пълзи през клечките. Колко най-малко клечки трябва да се премахнат, за да може бръмбарът да достигне (допълзи) до която си иска клетка?
б) Във всяка ъглова клетка стои по един бръмбар. Колко най-малко клечки трябва да се премахнат, за да може до всяка клетка да допълзи поне един бръмбар?
в) Колко най-малко клечки трябва да се премахнат така, че дъската да се разпадне на 8 еднакви многоъгълника?
г) Колко най-малко клечки трябва да се премахнат така, че дъската да се разпадне на 4 еднакви многоъгълника?

Лозенец, 5-6 класс, 18 августа 2018 г, г http://www.ashap.info/Uroki/Burgas/2018/56.html


Поделитесь с Вашими друзьями:


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

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