Задачи
1. Найдите сумму степеней вершин изображенного на рисунке графа и уменьшите найденную сумму на количество ребер графа.
Решение. Граф имеет одну вершину степени 5 и три вершины степени 3, сумма степеней вершин равна 14. В графе 7 ребер. Значит разность равна 7.
Ответ: 7.
2. Найдите сумму степеней вершин изображенного на рисунке графа и уменьшите найденную сумму на количество ребер графа.
Решение. Граф имеет четыре вершины степени 3, сумма степеней вершин равна 12. В графе 6 ребер. Искомая разность равна 6.
Ответ: 6.
3. В графе 4 вершин, каждая из которых имеет индекс 3. Сколько у него ребер?
Решение. Количество ребер графа равно половине суммы степеней его вершин, поэтому количество ребер равно
Ответ: 6
Для решения следующей задачи нужно знать!
Индексом вершины графа называется число ребер, сходящихся в этой вершине (ребра, с началом и концом в данной вершине считаются дважды).
4. В графе 5 вершин, каждая из которых имеет индекс 4. Сколько у него ребер?
Решение. Количество ребер графа равно половине суммы степеней его вершин, поэтому количество ребер равно
Ответ: 10
5. У графа 7 вершин степени 4 и еще 6 вершин степени 3. Сколько ребер в этом графе?
Решение. Количество ребер графа равно половине суммы степеней его вершин, поэтому количество ребер равно
Ответ: 23
6. В графе 45 рёбер, а каждая вершина имеет индекс 9. Сколько у него вершин?
Решение. Сумма степеней вершин графа вдвое больше количества его ребер, поэтому она равна 90. Каждая вершина имеет индекс 9, следовательно, вершин 90 : 9 = 10.
Ответ: 10.
7.В графе 12 рёбер, а каждая вершина имеет индекс 3. Сколько у него вершин?
Решение. Сумма степеней вершин графа вдвое больше количества его ребер, поэтому она равна 24. Каждая вершина имеет индекс 3, следовательно, вершин 24 : 3 = 8.
Ответ: 8.
8. Сколько графов, изображенных на рисунке, можно нарисовать, не отрывая карандаша от бумаги и проводя каждое ребро ровно один раз?
Решение. Рисуя граф так, как требуется в условии, в каждую вершину, за исключением начальной и конечной, нужно войти столько же раз, сколько выйти из нее. Поэтому в графе либо ровно две вершины нечетной степени (начальная и конечная), либо вершин нечетной степени нет, если конечная вершина совпадает с начальной.
У графа, изображенного на рисунке 1, ровно две вершины нечетной степени, одну из них можно взять за начало, другая будет концом. Граф, изображенный на рисунке 2, содержит четыре вершины нечетного индекса. Нарисовать его, не отрывая карандаша от бумаги, невозможно.
Ответ: 1.
9.Можно ли обойти все рёбра тетраэдра, пройдя по каждому ребру ровно один раз? В ответе запишите 1, если это возможно, или 0, если невозможно.
Решение. Будем считать вершины тетраэдра вершинами графа, а ребра тетраэдра — ребрами графа. Обход всех ребер тетраэдра означает, что граф можно нарисовать, не отрывая карандаша от бумаги, пройдя все ребра по одному разу.
Рисуя граф так, как требуется в условии, в каждую вершину, за исключением начальной и конечной, нужно войти столько же раз, сколько выйти из нее. Поэтому в графе должно быть либо ровно две вершины нечетной степени (начальная и конечная), либо вершин нечетной степени нет, если конечная вершина совпадает с начальной.
Но в этом графе 4 вершины нечетного индекса, поэтому требуемое невозможно.
Ответ: 0.
10. Можно ли обойти все рёбра октаэдра, пройдя по каждому ребру ровно один раз? В ответе запишите 1, если это возможно, или 0, если невозможно.
Решение. Такой обход можно совершить различными способами. Один из них приведен на рисунке, начать можно из любой вершины.
Ответ: 1.
P.S.:Вы можете связаться со мной, если хотите понять математику, улучшить свои навыки или подготовиться к экзаменам.
Телеграмм: Волоснова Дарья
!!Ссылка на следующий урок ↩️