две задачи на графы, нид хелп

asora

Доказать, что
1) Любую компанию людей можно развести по двум комнатам так, что для каждого человека как минимум половина его друзей окажутся в другой комнате.
2) Если в компании из n человек у каждого не менее n/2 друзей, то эту компанию можно рассадить за круглым столом так, чтобы каждый сидел между двумя своими друзьями.
у меня не получилось :confused: , помогите!

Vadim46

) Разведем как угодно. Если для кого-то условие не выполняется, переселим его - общее кол-во хороших (разнокомнатных) знакомств увеличится. Бесконечно оно увеличиваться не может => когда-то наступит нирвана.

asora

не факт. переселив чувака от его друзей, мы можем обломать некоторых его друзей :)

Vadim46

не факт. переселив чувака от его друзей, мы можем обломать некоторых его друзей
При чем здесь это? Общее количество хороших знакомств увеличится!
Не только у этого чувака, а общее :)

asora

отлично, спасибо!

shpanenoc

Уфф. Рассадим за круглый стол как угодно: v1,v2,...,vn,v1.
Пусть v1 и v2 не друзья. Существует такой vi, 2<i<n-1 что
1) v1 дружит с vi
2) v2 дружит с v(i+1).
(это потому что vi (а значит и v(i+1) можно выбрать минимум n/2 способами, а у v2 минимум n/2 друзей ==> из n/2 разных v(i+1) найдется друг v2)
Пересадим народ в таком порядке:
v1, vi, v(i-1 v(i-2 ..., v3, v2, v(i+1 v(i+2 ... vn, v1. Очевидно, количество пар недрузей, сидящих рядом, уменьшилось.

seregaohota

2) Если в компании из n человек у каждого не менее n/2 друзей, то эту компанию можно рассадить за круглым столом так, чтобы каждый сидел между двумя своими друзьями.
у меня не получилось , помогите!
Значит ты не Дирак :cool:
Словарь терминов теории графов
Glossary of graph theory


Dirac (1952)
A simple graph with n vertices (n > 2) is Hamiltonian if each vertex has degree n/2 or greater.

asora

на счёт "не Дирак" - сам расстроился что так отупел
Оставить комментарий
Имя или ник:
Комментарий: