2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Теория графов, задача на клики
Сообщение22.05.2009, 09:21 
Привет, всем)))
Помогите, пожалуйста, решить задачу по теории графов, нужно срочно:

Некоторые участники олимпиады дружат, и дружба взаимна. Назовем группу участников кликой, если все они дружат между собой. Их число называется размером клики. Известно, что максимальный размер клики четен. Докажите, что участников можно рассадить по двум аудиториям так, что максимальные размеры клик в обеих аудиториях совпадают.


Буду очень благодарна)

 !  AKM:
Ознакомьтесь с Правилами форума. Заголовок отредактирован

Цитата:
I-1-и. Заголовки тем должны быть информативными. Не допускается использование "кричащих" выражений типа "Help!!!", "Помогите", "Горю", "Очень срочно надо" и т.п. Сообщения подобного типа могут быть удалены администрацией.
I-1-к. Запрещается злоупотребление средствами форматирования с целью привлечь внимание к своему сообщению (в частности, КАПСЛОКИНГ), а также чрезмерное использование знаков препинания и смайлов.

 
 
 
 Re: ТЕОРИЯ ГРАФОВ!!!!!СРОЧНО!!!!ПЛИЗ!!))
Сообщение22.05.2009, 09:47 
Аватара пользователя
Возьмите эту максимальную клику и разделите на две равные части. Заведите в аудитории. А остальных начните разводить по аудиториям так, чтобы размер первоначальных клик не увеличивался. Только вот не может ли образоваться новая клика...

 
 
 
 Re: ТЕОРИЯ ГРАФОВ!!!!!СРОЧНО!!!!ПЛИЗ!!))
Сообщение22.05.2009, 09:56 
Аватара пользователя
Сначала посадите максимальную клику в первую аудиторию, а всех остальных участников - во вторую. Затем пересадите несколько пар участников из первой аудитории во вторую так, чтобы либо размеры максимальных клик сравнялись, либо число людей в первой аудитории превосходит размер максимальной клики во второй аудитории на 1, после чего пересадите во вторую аудиторию еще 1 чел. Детали доказательства того, что описанный мной процесс решает задачу - додумайте сами.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group