ЗАБА Математические олимпиады и олимпиадные задачи
Задачная база >> Разное >> Материалы Кировской ЛМШ, 2001 г, 7 класс >> Тест по графамПоказать решения
Разное. Материалы Кировской ЛМШ, 2001 г, 7 класс. Тест по графам

Задача 1: Сколько рёбер в полном графе с 20 вершинами?

Задача 2: Сколько всего рёбер в графе, степени вершин которого равны 3, 4, 5, 3, 4, 5, 3, 4, 5 ?

Задача 3: В дереве имеется 100 вершин степени 5, 100 вершин степени 3, а остальные – висячие. Сколько висячих вершин в этом дереве?

Задача 4: Какое число рёбер нужно убрать из полного графа с 15 вершинами, чтобы оставить его скелет?

Задача 5: Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?

Задача 6: Лес состоит из 10 деревьев. Всего в лесу 200 вершин. Сколько в нем рёбер?

Задача 7: Однажды Рома сказал: «Если степень каждой вершины 100-вершинного графа не меньше N, то этот граф связен». При каком наименьшем значении N Рома сможет это доказать, если известно, что его не зря взяли в профи?

Задача 8: Из нескольких кусочков проволоки спаяна проволочная решетка 8 × 8 клеток. Какое наименьшее число кусочков для этого могло потребоваться?

Задача 9: Во дворе живут 4 пёсика: Бобик, Робик, Тобик и Толстолобик. Каждому из них случалось драться с кем-нибудь из остальных, причём у Бобика, Робика и Тобика число тех, с кем они дрались – разное. Со сколькими собаками двора дрался Толстолобик?

Задача 10: В стране 6 городов. Авиасообщение осуществляют несколько авиакомпаний. Каждая обслуживает 3 авиалинии, связывающие попарно некоторые три города (между двумя городами могут летать самолеты нескольких компаний). Каждые два города связаны по крайней мере одной линией. При каком наименьшем числе компаний это возможно?

Задача 11: Каждое ребро графа покрасили в синий или зелёный цвет так, что ни из одной вершины не выходит двух одноцветных рёбер. Синих рёбер оказалось на 5 больше, чем зелёных. Какое наименьшее число компонент связности может иметь этот граф?



Задачная база >> Разное >> Материалы Кировской ЛМШ, 2001 г, 7 класс >> Тест по графамПоказать решения