Сколько всего ребер в графе степени вершин которого равны 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 больше, чем зелёных. Какое наименьшее число компонент связности может иметь этот граф?
Сколько всего ребер в графе степени вершин которого равны 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
Вершину, не принадлежащую ни одному ребру, называют
изолированной
Сколько всего ребер в графе степени вершин которого равны 3 4 5 3 4 5 3 4 5
Задача 1:
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Решение:
Предположим, что это возможно. Рассмотрим тогда граф, вершины которого соответствуют телефонам, а ребра – соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна пяти. Подсчитаем количество ребер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено дважды (оно ведь соединяет две вершины!). Поэтому число ребер графа должно быть равно 15 • 5/2. Но это число нецелое! Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.
При решении этой задачи мы выяснили, как подсчитать число ребер графа, зная степени всех его вершин. Для этого нужно просуммировать степени вершин и полученный результат разделить на два.
Задача 2:
В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
Решение:
Общее число дорог равно 100 • 4/2 = 200.
Задача 3:
В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 – по 4 друга, а 10 – по 5 друзей?
Решение:
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 – степень 4, 10 – степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме.
Задача 4:
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?
Решение:
Нельзя. Примените теорему о числе нечетных вершин.
Задача 5:
У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?
Решение:
Нет, не может. В противном случае получился бы граф соседства баронств с нечетным количеством нечетных вершин.
Задача 6:
Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?
Решение:
Если в государстве k городов, то дорог – 3k/2. Это число не может быть равно 100.
Задача 7:
Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?
Решение:
Да, верно, иначе нарушается теорема о числе нечетных вершин.
Задача 8:
Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.
Решение:
Это в точности теорема о нечетных вершинах.
Задача 9:
Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?
Решение:
Нет, нельзя. Примените теорему к графу, вершины которого – данные отрезки, а ребро соединяет две вершины тогда, когда два соответствующих отрезка пересекаются.