2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Задача по теории графов
Сообщение19.11.2005, 15:17 
Помогите, пожалуйста, решить задачу по теории графов.

Имеется несколько юношей, каждый из которых знаком с некоторыми девушками. Две свахи знают, кто с кем знаком. Одна сваха заявляет: "Я могу одновременно женить всех брюнетов так, чтобы каждый из них женился на знакомой ему девушке!". Вторая сваха говорит: "А я могу устроить судьбу всех блондинок: каждая выйдет замуж за знакомого юношу!". Этот диалог услышал любитель математики, который сказал: "В таком случае можно сделать и то, и другое!". Прав ли он?

  
                  
 
 О задаче
Сообщение23.11.2005, 16:10 
Вроде бы задача простая. Но решить не так-то просто. Она, кажется, из какой-то олимпиады. При том за ее решение давали 5 или 6 очков, так что там она считалась трудной.

  
                  
 
 
Сообщение24.11.2005, 04:43 
Задача-то совсем простая.
Рассмотрим граф с вершинами людьми и направленными ребрами ( из брюнетов к их невестам и из блондинок к их женихам).
Так как в каждую вершину входит не более одного ребра и выходит не более одного, то все ребра можно разбить на направленные циклы и пути не пересекающиеся по вершинам. Так как они не пересекаются по вершинам, то для каждого из них можно решать задачу отдельно.

Например, выбрав ребер через одно ( циклы имеют четную длину, а в пути надо выбирать 1-е, 3-е, ... ребра, считая от начала) получаем пример свадеб.

  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group