IX Международная студенческая научная конференция Студенческий научный форум - 2017

Теорема Холла утверждает, что если в двудольном графе для любого положительного целого k любые k элементов одной из долей связаны, по крайней мере, с k элементами другой, то граф разбивается на пары.

Мы провели опрос молодых людей в нашем институте, и среди желающих составить себе пару выбрали трое юношей и четыре девушки. Но выбирали мы с одним условием, а именно каждый юноша знаком с несколькими девушками; задаемся вопросом, при каких условиях можно женить юношей так, чтобы каждый из них женился на знакомой именно ему девушке? Отношения знакомства мы можем увидеть в таблице 1.

Таблица 1Отношения знакомства между юношами и девушками

Для более наглядного решения данной задачи используем двудольный граф. Граф представляет собой некоторое множество вершин, которые, в свою очередь, подразделены на две группы: юноши и девушки. Мы соединили ребрами девушек и юношей в зависимости от того кто с кем знаком (см. рис. 1).

Рисунок 1 Граф отношения знакомств между юношами и девушками

Итак, чтобы решить данную задачу необходимо соблюсти одно условие. А именно, любые n количество парней, должны быть знакомы не меньше чем с n девушками. Но при этом число n не должно превышать общее количество парней и должно быть меньше единицы. Важность данного условия можно объяснить, тем что даже если для n количества парней мы не найдем необходимого количества девушек, то мы не сможем поженить даже это количество парней, не говоря уже обо всех остальных.

Так же не сложно представить количество данных браков с помощью двудольного графа (см. рис.2).

Рисунок 2Изображение линий связи

Литература:

1. Агишева Д.К., Зотова С.А., Матвеева Т.А., Светличная В.Б. Линейное программирование: учебное пособие // Успехи современного естествознания. – 2010. – № 9. – С. 61-62.

2.Сетевое планирование и управление (СПУ) в экономике. Вавилина А. А., Агишева Д. К. http://rae.ru/forum2011/21/1501