Сколько всего ребер в графе степени вершин которого равны 3 4 5 3 4 5 3 4 5
Задача 1: Сколько рёбер в полном графе с 20 вершинами?
Решение: 190
Задача 2: Сколько всего рёбер в графе, степени вершин которого равны 3, 4, 5, 3, 4, 5, 3, 4, 5 ?
Решение: 18
Задача 3: В дереве имеется 100 вершин степени 5, 100 вершин степени 3, а остальные – висячие. Сколько висячих вершин в этом дереве?
Решение: 402
Задача 4: Какое число рёбер нужно убрать из полного графа с 15 вершинами, чтобы оставить его скелет?
Решение: 91
Задача 5: Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?
Решение: 14
Задача 6: Лес состоит из 10 деревьев. Всего в лесу 200 вершин. Сколько в нем рёбер?
Решение: 190
Задача 7: Однажды Рома сказал: «Если степень каждой вершины 100-вершинного графа не меньше N, то этот граф связен». При каком наименьшем значении N Рома сможет это доказать, если известно, что его не зря взяли в профи?
Решение: 50
Задача 8: Из нескольких кусочков проволоки спаяна проволочная решетка 8 × 8 клеток. Какое наименьшее число кусочков для этого могло потребоваться?
Решение: 14
Задача 9: Во дворе живут 4 пёсика: Бобик, Робик, Тобик и Толстолобик. Каждому из них случалось драться с кем-нибудь из остальных, причём у Бобика, Робика и Тобика число тех, с кем они дрались – разное. Со сколькими собаками двора дрался Толстолобик?
Решение: 2
Задача 10: В стране 6 городов. Авиасообщение осуществляют несколько авиакомпаний. Каждая обслуживает 3 авиалинии, связывающие попарно некоторые три города (между двумя городами могут летать самолеты нескольких компаний). Каждые два города связаны по крайней мере одной линией. При каком наименьшем числе компаний это возможно?
Решение: 6
Задача 11: Каждое ребро графа покрасили в синий или зелёный цвет так, что ни из одной вершины не выходит двух одноцветных рёбер. Синих рёбер оказалось на 5 больше, чем зелёных. Какое наименьшее число компонент связности может иметь этот граф?
Сколько рёбер в этом графе (см)?
У графа пять вершин имеют степень 5, шесть вершин — степень 6, семь вершин — степень 7. Сколько рёбер в этом графе?
Для начала отметим, что степень вершины графа (узла) это число ребер, которые соединяют эту вершину с другими вершинами. Понятно, что если у обычного графа две вершины, то степень каждой вершины 1, ребро только одно, если три вершины, то степень каждой равен 2, а ребер 2. И так далее, получается, что число ребер равно половине суммы всех степеней графа (так как при подсчете каждое ребро учитывается дважды). Сумма степеней данного графа равна 5*5 + 6*6 + 7*7 = 25+36+49=110. Значит ребер 55 (110/2). Ответ: 55.
Выберите верное утверждение
1. Сколькими способами можно составить расписание одного учебного дня из 5 различных уроков?
2. Сколькими способами можно закрасить 6 клеток так, чтобы 2 клетки были закрашены красным цветом, а 4 другие – белым, черным, зеленым и синим? (каждый своим цветом).
3. В 9«Б» классе 32 учащихся. Сколькими способами можно сформировать команду из 4 человек для участия в математической олимпиаде?
4. Сколько существует различных двузначных чисел, в записи которых можно использовать цифры 1, 2, 3, 4, 5, 6, если цифры в числе должны быть различными?
5. Вычислить: 6! -5!
6. Вычислите число размещений по формуле .
7. Упростите выражение:
8. Сколько различных перестановок можно составить из букв слова АБАКАН?
9. Из пяти отличников 1 А" класса и четырех отличников 1 "В" класса надо выбрать двух человек (из каждого класса по одному) для поездки на новогоднюю елку в Кремль. Сколькими способами это можно сделать?
10. Есть три карандаша и четыре ручки. Выбирают пару из одного карандаша и одной ручки. Выберите правильное утверждение.
а) количество способов выбора одного карандаша равно 4;
б) количество способов выбора одной ручки равно 3;
в) каждому выбору одного карандаша соответствует четыре возможности выбрать одну ручку в пару;
г) количество способов выбора пары из одного карандаша и одной ручки равно 3 + 4.
11. Укажите связные вершины графа:
12. Сколько ребер нужно провести, чтобы достроить граф, изображенный на рисунке, до полного?
| а) 1; б) 2; г) 3; д) 4. |
13. Назвать наибольшее число висячих вершин, дерева с 10-ю вершинами.
14. Чему равна сумма степеней входа всех вершин графа, если сумма степеней выхода всех вершин равна 47?
15. В деревне Вишкиль 9 домов. Из каждого дома тянется четыре шланга к четырём другим домам. Сколько шлангов в деревне?
16. Эйлерова характеристика любого дерева равна
17. Сколько всего рёбер в графе, степени вершин которого равны 3, 4, 5, 3, 4, 5, 3, 4, 5?
18. Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?
19. В дереве имеется 100 вершин степени 5, 100 вершин степени 3, а остальные – висячие. Сколько висячих вершин в этом дереве?
а) 100;
б) 108;
в) 200;
г) 402.
20. Если степень вершины графа равна 0, то вершина называется …
г) степень вершины не может равняться 0.
| № вопроса | Правильный ответ |
| в | |
| б | |
| б | |
| г | |
| а | |
| б | |
| в | |
| б | |
| a | |
| в | |
| б | |
| б | |
| в | |
| a | |
| в | |
| в | |
| г | |
| a | |
| г | |
| б |
Вариант 2
1. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5?
2. Разложите на простые множители число 30. Сколькими способами можно записать в виде произведения простых множителей число 30?
3. Имеются помидоры, огурцы, лук. Сколько различных салатов можно приготовить, если в каждый салат должно входить 2 различных вида овощей?
4. Сколькими способами из 9 учебных предметов можно составить расписание учебного дня из 6 различных уроков.
6. Вычислите число размещений по формуле .
7. Упростите выражение:
8. Сколько перестановок можно сделать из букв слова «Миссисипи»
9. Из четырех юношей и двух девушек — артистов школьного театра — надо выбрать юношу и девушку — ведущих концерта. Сколькими способами это можно сделать?
10. Переставляют три буквы М, Н, K всеми возможными способами. Выберите правильное утверждение.
а) Можно выполнить только такие перестановки: М, Н, K или М, K, Н, или K, М, Н;
б) Можно выполнить только такие перестановки: М, Н, K или М, K, Н, или K, М, Н, или K, Н, М;
в) Можно выполнить только такие перестановки: М, Н, К или М, K, Н, или Н, K, М, или Н, М, K, или K, М, Н, или K, Н, М;
г) Всего существует только 4 способа выполнить перестановки трех букв М, Н, K.
11. Укажите ребро, которое является мостом графа, изображенного на рисунке
| а) ГД; б) ВГ; в) АБ; г) БЗ. |
12. Сколько ребер нужно провести, чтобы достроить граф, изображенный на рисунке, до полного?
| а) 1; б) 2; в) 3; г) 0. |
13. Сколько можно изобразить различных деревьев, вершинами которых являются три точки.
14. Чему равна сумма степеней входа всех вершин графа, если сумма степеней выхода всех вершин равна 33?
15. В деревне 7 домов. Из каждого дома тянется 3 дороги к трем колодцам. Сколько дорог?
16. Вершину, не принадлежащую ни одному ребру, называют
17. Сколько рёбер в полном графе с 20 вершинами?
18. Лес состоит из 10 деревьев. Всего в лесу 200 вершин. Сколько в нем рёбер?
а) 200;
19. Каждое ребро графа покрасили в синий или зелёный цвет так, что ни из одной вершины не выходит двух одноцветных рёбер. Синих рёбер оказалось на 5 больше, чем зелёных. Какое наименьшее число компонент связности может иметь этот граф?
а) 4;
б) 10;
в) 5;
20. Ребро графа называется инцидентным вершине, если оно
а) начинается и заканчивается в этой вершине;
б) не соединяет эту вершину с какой-либо другой вершиной графа;
в) имеет длину 1;
г) соединяет эту вершину с какой-либо другой вершиной графа.
| № вопроса | Правильный ответ |
| d | |
| a | |
| a | |
| б | |
| б | |
| г | |
| б | |
| a | |
| в | |
| в | |
| г | |
| a | |
| б | |
| в | |
| a | |
| a | |
| в | |
| б | |
| в | |
| г |
Вариант 3
1. Сколькими способами можно расставить 4 различные книги на книжной полке?
2. Сколькими способами можно закрасить 6 клеток таким образом, чтобы 3 клетки были красными, а 3 оставшиеся были закрашены (каждая своим цветом) былым, черным и зеленым?
3. Сколько диагоналей имеет выпуклый семиугольник?
4. В футбольной команде 11 человек. Необходимо выбрать капитана и его заместителя. Сколькими способами это можно сделать?
5. Сократите дробь:
6. Вычислите число сочетаний
8. Сколько перестановок можно получить из букв слова КОЛОКОЛА?
9. Из пяти членов правления кооператива нужно выбрать делегацию из двух человек для переговоров со спонсором. Сколько делегаций можно составить?
10. В ящике лежат один белый, один черный и один красный шары. Наугад вынимают один шар. Выберите правильное утверждение.
а) если вынуть один шар, то он может быть только черным или красным;
б) количество разных способов вынуть один шар равно 3;
в) существует два разных способа вынуть один белый шар;
г) если вынуть один шар, то он может быть только белым.
11. Сколько мостов можно построить в случае графа, представленного на рисунке?
| а) 10; б) 12; в) 18; г) 15. |
12. Сколько ребер нужно провести, чтобы достроить граф, изображенный на рисунке, до полного?
| а) 2; б) 3; в) 4; г) 5. |
13. Назвать наименьшее число висячих вершин дерева с 15-ю вершинами.
14. Сколько ребер нужно провести, чтобы достроить граф, изображенный на рисунке, до полного?
| а) 1; б) 2; в) 3; г) 0. |  |
15. В деревне 6 домов. Из каждого дома тянется телефонный кабель к другим домам. Сколько таких проводов?
16. Граф, у которого все вершины имеют одну и ту же степень, называется
17. Какое число рёбер нужно убрать из полного графа с 15 вершинами, чтобы оставить его скелет?
18. Однажды Рома сказал: «Если степень каждой вершины 100-вершинного графа не меньше N, то этот граф связен». При каком наименьшем значении N Рома сможет это доказать?
19. В стране 6 городов. Авиасообщение осуществляют несколько авиакомпаний. Каждая обслуживает 3 авиалинии, связывающие попарно некоторые три города (между двумя городами могут летать самолеты нескольких компаний). Каждые два города связаны по крайней мере одной линией. При каком наименьшем числе компаний это возможно?
а) 2;
Выберите верное утверждение
а) Петлей называется ребро, начинающееся и заканчивающееся в разных вершинах;
б) Граф называется взвешенным или нагруженным, если каждой вершине поставлено в соответствие некоторое число;
в) Кратными ребрами называется ребра смежные с одной и той же вершиной;
г) Вершина называется изолированной, если ее степень равна 1.
| № вопроса | Правильный ответ |
| a | |
| в | |
| б | |
| г | |
| в | |
| б | |
| a | |
| в | |
| б | |
| б | |
| г | |
| г | |
| г | |
| a | |
| в | |
| б | |
| a | |
| г | |
| б | |
| б |
Вариант 4
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Сколько всего ребер в графе степени вершин которого равны 3 4 5 3 4 5 3 4 5
Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64
Лучшие эксперты по данной тематике
 |
Коцюрбенко Алексей aka Жерар Статус: Профессор Рейтинг: 3759 • повысить рейтинг » |
CradleA Статус: Бакалавр Рейтинг: 2620 • повысить рейтинг » |
Абаянцев Юрий Леонидович aka Ayl Статус: Профессионал Рейтинг: 2096 • повысить рейтинг » |
/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика дискретная
| Номер выпуска: | 266 |
| Дата выхода: | 23.01.2012, 23:00 |
| Администратор рассылки: | Асмик (Академик) |
| Подписчиков / экспертов: | 53 / 60 |
| Вопросов / ответов: | 0 / 0 |
Статья отправлена Асмик (Академик)
дата отправки: 23.01.2012, 18:27
Тест по теории графов
Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?
14
В полном графе каждая вершина инцидентна 14 ребрам. Убрав эти ребра для одной из вершин, получим 1 одинокую вершину и полный граф с 14 вершинами.
Эйлерова характеристика любого дерева равна 1.
Разность В-Р, где В — число вершин, а Р — число ребер графа G, называется эйлеровой характеристикой графа.
Граф Петерсона — это пример графа
кубического
Чему равна сумма степеней входа всех вершин графа, если сумма степеней выхода всех вершин равна 45 ?
Тоже 45
Граф, у которого все вершины имеют одну и ту же степень, называется
регулярным
Сколько рёбер в полном графе с 20 вершинами?
190
В деревне Вишкиль 9 домов. Из каждого дома тянется четыре шланга к четырём другим домам. Сколько шлангов в деревне?
18
Сколько всего рёбер в графе, степени вершин которого равны 3, 4, 5, 3, 4, 5, 3, 4, 5?
18
Вершину, не принадлежащую ни одному ребру, называют
изолированной