Сириус. Комбинаторика 8 класс. Подвешивание за вершину. Блок заданий №3.
Помогите пожалуйста с 2 заданиями:
На кружок пришли несколько школьников, среди которых Вася и Петя. Оказалось, что:
каждый из пришедших знает не более пятерых других;
у Васи и Пети трое общих знакомых;
каждый школьник либо знает Васю или Петю, либо имеет с кем-то из них хотя бы одного общего знакомого.
Какое наибольшее количество школьников могло прийти на кружок?
Архипелаг состоит из N⩾7 островов. Любые два острова соединены не более чем одним мостом. Известно, что с каждого острова ведёт не более чем 5 мостов, а среди любых 7 островов обязательно есть два, соединённые мостом. Какое наибольшее значение может принимать N
?
Спасибо❤️.
1)
V, P – выбранные ученики
deg ≤ 5
|N(V)| = 5, |N(P)| = 5, |N(V)∩N(P)| = 3 ⇒
|N(V)∪N(P)| = 5 + 5 − 3 = 7
∀x∉{V,P,N(V),N(P)} ∃y∈N(V)∪N(P): xy∈E
‖свободные‖ степени соседей:
u∈N(V)\N(P): 4; v∈N(P)\N(V): 4; w∈N(V)∩N(P): 3
∑ свободные = 2·4 + 2·4 + 3·3 = 25
⇒ max |S| = 25
n_max = 2 + 7 + 25 = 34
Ответ: 34.
2)
∀ 7 вершин ∃ ребро ⇔ α(G) ≤ 6
Δ(G) ≤ 5 ⇒ ∀v: deg(v) ≤ 5
α(G) ≥ ∑_{v∈V} 1/(deg(v)+1) ≥ n/6 (Caro–Wei)
α ≤ 6 ⇒ n/6 ≤ 6 ⇒ n ≤ 36
n = 36 достижимо (5-регулярный граф, напр. 6 копий C₆ с подходящими «скрещивающими» рёбрами).
Ответ: 36.