82 Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Докажите, что среди них найдутся четверо, имеющих одинаковое число знакомых. 83 Рассмотрите рисунок 28 на с. 45. Является ли эйлеровым: а) граф куба; б) граф тетраэдра; в) граф октаэдра? 84 Дан граф (рис. 45). Какое наименьшее число рёбер нужно удалить из графа, чтобы оставшийся подграф был эйлеровым графом? Приведите пример. a) Рисунок 45 б) 85 Какой максимальный по числу рёбер эйлеров подграф можно выделить в данном графе (рис. 46)? a) Рисунок 46 б) 86 Нужно спаять из проволоки каркас куба, показанный на рисунке 47. На ка кое наименьшее число частей придётся разрезать проволоку?

83 Рассмотрите рисунок 28 на с. 45. Является ли эйлеровым:

Давай разберем, какие графы являются эйлеровыми.

Эйлеровым графом называется граф, в котором существует цикл, проходящий через каждое ребро графа ровно один раз. Для того, чтобы граф был эйлеровым, необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень (четное количество ребер, инцидентных вершине).

а) граф куба; Граф куба является эйлеровым, так как каждая вершина имеет степень 3, что нечетно. Однако, если добавить еще один цикл, то граф станет эйлеровым. Но исходный граф куба не эйлеров.

б) граф тетраэдра; Граф тетраэдра не является эйлеровым, так как каждая вершина имеет степень 3, что нечетно.

в) граф октаэдра? Граф октаэдра является эйлеровым, так как каждая вершина имеет степень 4, что четно, и граф связный.

Ответ: Граф октаэдра является эйлеровым.

84 Дан граф (рис. 45). Какое наименьшее число рёбер нужно удалить из графа, чтобы оставшийся подграф был эйлеровым графом? Приведите пример.

Давай рассмотрим граф на рисунке 45 (a).

В графе (a) вершины A, B, C, D, K, L, M, N имеют степень 3. Чтобы сделать все вершины четными, нужно удалить ребра так, чтобы у каждой вершины осталась четная степень. Например, можно удалить ребра AL, BM, CN, DK. Тогда степени всех вершин станут равны 2, и граф станет эйлеровым.

Минимальное число ребер, которые нужно удалить, равно 4.

Рассмотрим граф на рисунке 45 (б).

В графе (б) вершины A, E, F имеют степень 2, а вершины B, C, D имеют степень 2. Все вершины имеют четную степень, поэтому граф уже является эйлеровым, и удалять ребра не нужно.

Минимальное число ребер, которые нужно удалить, равно 0.

Ответ: (а) 4 ребра, например AL, BM, CN, DK; (б) 0 ребер.

85 Какой максимальный по числу рёбер эйлеров подграф можно выделить в данном графе (рис. 46)?

Рассмотрим граф на рисунке 46 (a).

В графе (a) вершины A, B, C, D, E, F имеют степень 3. Чтобы выделить эйлеров подграф, нужно удалить ребра так, чтобы все вершины имели четную степень. Можно удалить ребра, соединяющие противоположные вершины, например, AD, BE, CF. Тогда останется 6 ребер, и каждая вершина будет иметь степень 2, что делает граф эйлеровым.

Рассмотрим граф на рисунке 46 (б).

В графе (б) вершины A, B, C, D имеют степень 3, а вершины E, F имеют степень 2. Чтобы выделить эйлеров подграф, нужно удалить ребра так, чтобы все вершины имели четную степень. Можно удалить ребра AE и CD. Тогда останется 5 ребер, и вершины A, C будут иметь степень 2, а вершины B, D, E, F будут иметь степень 2, что делает граф эйлеровым.

Ответ: (а) 6 ребер; (б) 5 ребер.

86 Нужно спаять из проволоки каркас куба, показанный на рисунке 47. На какое наименьшее число частей придётся разрезать проволоку?

Чтобы спаять каркас куба из проволоки, нужно иметь 12 ребер. Если не разрезать проволоку, то получится один кусок. Однако, если нужно минимизировать количество частей, то нужно разрезать наименьшее число раз. Каркас куба имеет 8 вершин, и в каждой вершине сходятся 3 ребра. Если мы хотим сделать каркас куба из одного куска проволоки, то нужно минимизировать число разрезов. Если представить, что мы спаяли куб из проволоки и не разрезали её, то мы имеем один кусок. Если разрезать проволоку в одном месте, то получим 2 куска. Таким образом, наименьшее число частей, на которое нужно разрезать проволоку, равно 1.

Ответ: 1

Ты молодец! У тебя все отлично получается! Продолжай в том же духе, и ты обязательно добьешься больших успехов в учебе!