Ответить на вопросы

Давайте разберём каждую из частей задачи по порядку. 1. **Нарисуй ориентированный граф, вершинами которого являются числа 1, 2, 3, 4, 6, 8. Причём от одной вершины X ведет стрелка к другой вершине Y только тогда, когда число X делится на число Y. Сколько ребер в этом графе?** Чтобы построить граф, нужно определить, где одно число делится на другое. Мы определяем стрелки таким образом: - 1 не делится ни на какое другое число. - 2 делится на 1. - 3 делится на 1. - 4 делится на 1 и 2. - 6 делится на 1, 2 и 3. - 8 делится на 1, 2 и 4. Ребра: - 2 → 1 - 3 → 1 - 4 → 1 - 4 → 2 - 6 → 1 - 6 → 2 - 6 → 3 - 8 → 1 - 8 → 2 - 8 → 4 Всего 10 рёбер. 2. **Сумма исходящих степеней всех вершин в ориентированном графе равна 2n. Чему равна сумма входящих степеней всех вершин? Сколько ребер в графе?** В ориентированном графе сумма всех исходящих степеней равна сумме всех входящих степеней. Поскольку по условию сумма исходящих степеней равна \(2n\), то и сумма входящих степеней равна \(2n\). Количество рёбер в графе равно либо сумме входящих, либо исходящих степеней, то есть \(2n\). 3. **Выбери верные высказывания:** а) Путь в графе, который проходит все ребра ровно один раз, называется эйлеровым. - Верно. Это определение эйлерового пути. б) Существует такой ориентированный граф, в котором сумма входящих степеней каждой вершины равна 2. - Возможно, но это не всегда верно для всех графов. в) Существует граф, вершин которого ровно 32, а сумма всех степеней вершин равна 22 и число рёбер обязательно нечётно. - В неориентированном графе сумма всех степеней вершин равна удвоенному числу рёбер, следовательно, сумма не может быть нечётной, если количество рёбер чётное. Если сумма степеней равна 22, то число рёбер 11. Поскольку число рёбер нечётное, то высказывание верно. г) Сумма степеней вершин равна 22 и число рёбер бывает чётным. - Это противоречит свойству графа, так как сумма степеней вершин это удвоенное количество рёбер для неориентированного графа. Для ориентированного графа сумма исходящих и входящих степеней равны и равны числу рёбер. Число рёбер не может быть чётным при нечётной сумме степеней. Вопросы б) и г) довольно сложные, так как исследуют особые случаи и зависимости в графе, но основываясь на общих свойствах графов, можно сделать такие выводы.