Двудольные графы.

119. Является ли двудольным графом

• простая цепь?

• дерево?

• полный граф?

120. Докажите, что дерево является двудольным графом. Какие деревья являются полными двудольными графами.

121. В теннисном турнире каждый игрок команды «синих» встречается с каждым игроком команды «красных». Число игроков в командах одинаково и не более восьми. «Синие» выиграли в четыре раза больше встреч, чем «красные». Сколько человек в каждой из команд?

122. Школьники на кружке решали 16 задачи. Каждый из 16 школьников решил по четыре задачи, и каждая задача была решена четырьмя школьниками. Доказать, что можно организовать разбор задач так, чтобы каждый рассказал одну решенную им задачу и чтобы все задачи были разобраны.

123. Каждый из учеников 9 «А» класса дружит с тремя учениками 9 «Б» класса, а каждый из учеников 9 «Б» класса дружит с тремя учениками 9 «А» класса. Докажите, что число учеников в обоих классах одинаково.

124. Строительному управлению для выполнения работы требуются каменщик плотник, водопроводчик и слесарь. На эти должности имеются пять претендентов: один может работать каменщиком, другой – плотником, третий – каменщиком и водопроводчиком и еще двое имеют по две специальности – водопроводчика и слесаря. Можно ли охватить весь фронт работ (используя четверых рабочих)? Если да, то подробно проверьте выполнение условия теоремы Холла.

125. В школе 4 кружка: домоводство, математический кружек, компьютеный клуб и кружек английского языка. Пять человек из класса посещают эти кружки, причем один и тот же ученик может являться членом нескольких кружков. Можно ли выбрать старосту в каждом кружке так, чтобы ни один человек не был старостой сразу в двух кружках, в следующих случаях:

1. Кружок домоводства посещают 1, 3 и 4 ученики, математический кружок – 1, 4 и 5, компьютерный клуб – 2, 3 и 5, кружок английского языка – 2, 4 и 5.

2. Кружок домоводства посещают 1 и 3 ученики, математический кружок – 2 и 3, компьютерный клуб – 2 и 1, кружок английского языка – 3.

3. Кружок домоводства посещают 1, 3 и 4 ученики, математический кружок – 2 и 5, компьютерный клуб – 2 и 5, кружок английского языка – 2.

126. Десять кандидатов готовятся к двум космическим экспедициям на Марс. Поскольку экспедиции будут продолжаться несколько лет, а их участники окажутся в замкнутом пространстве небольшого объема, то большое значение приобретает психологическая совместимость членов экипажа. Путем тестирования установлены пары кандидатов, присутствие которых в одной и той же экспедиции было бы нежелательным. Результаты тестирования отражены в таблице. (Если на пересечении I строки j столбца находится знак «+», то участие I и j кандидатов в одной экспедиции нежелательно.) Разделите кандидатов на две группы для участия в экспедициях.

	1	2	3	4	5	6	7	8	9	10
1		+	+	+
2	+				+
3	+						+
4	+					+
5		+						+
6				+						+
7			+					+		+
8					+		+		+
9								+		+
10						+	+		+