|
Гость |
|
|
|
Помогите, пожалуйста, решить задачу по теории графов.
Имеется несколько юношей, каждый из которых знаком с некоторыми девушками. Две свахи знают, кто с кем знаком. Одна сваха заявляет: "Я могу одновременно женить всех брюнетов так, чтобы каждый из них женился на знакомой ему девушке!". Вторая сваха говорит: "А я могу устроить судьбу всех блондинок: каждая выйдет замуж за знакомого юношу!". Этот диалог услышал любитель математики, который сказал: "В таком случае можно сделать и то, и другое!". Прав ли он?
|
|
|
|
 |
|
Гость |
|
|
|
Вроде бы задача простая. Но решить не так-то просто. Она, кажется, из какой-то олимпиады. При том за ее решение давали 5 или 6 очков, так что там она считалась трудной.
|
|
|
|
|
|
Evgeni_1003 |
|
|
|
Задача-то совсем простая.
Рассмотрим граф с вершинами людьми и направленными ребрами ( из брюнетов к их невестам и из блондинок к их женихам).
Так как в каждую вершину входит не более одного ребра и выходит не более одного, то все ребра можно разбить на направленные циклы и пути не пересекающиеся по вершинам. Так как они не пересекаются по вершинам, то для каждого из них можно решать задачу отдельно.
Например, выбрав ребер через одно ( циклы имеют четную длину, а в пути надо выбирать 1-е, 3-е, ... ребра, считая от начала) получаем пример свадеб.
|
|
|
|
|
