Статья Автор: Лебедев Дмитрий

Конспект _Двудольные графы


Комби-7 Двудольные графы Часть 1 

Говорят, что граф двудольный, если его вершины можно разбить на две доли так, чтобы внутри каждой доли рёбер не было.

Нетрудно заметить, что в таком графе сумма степеней вершин одной доли должна быть равна сумме степеней другой.

Задача. В классе учится несколько мальчиков и девочек. Известно, что каждая девочка дружит ровно с 6 мальчиками из этого класса, а каждый мальчик дружит ровно с 10 девочками из этого класса. Кого в классе больше: мальчиков или девочек?

Задача. Футбольный мяч сшит из 32 частей: чёрных пятиугольников и белых шестиугольников. Каждый пятиугольник граничит с пятью шестиугольниками, а каждый шестиугольник граничит с тремя пятиугольниками и тремя шестиугольниками. Сколько всего пятиугольников, а сколько шестиугольников?

Задача. В классе учится 20 человек. В прошлом учебном году они участвовали в трёх математических олимпиадах: городской, региональной и Турнире Городов. В каждой из олимпиад участвовало нечётное число учеников класса, причём каждый ученик, участвовавший в олимпиадах, участвовал в нечётном числе олимпиад. Докажите, что кто-то из класса не был ни на одной олимпиаде.

Задача. У куба отмечены вершины и центры граней, а также проведены диагонали всех граней. Можно ли по отрезкам этих диагоналей обойти все отмеченные точки, пройдя каждую из них ровно по одному разу?

Задачи для тренировки

1) 7_11_1 Выберите графы, которые являются двудольными

  
2)  7_11_2 У девочки Ани есть несколько юбок и блузок  
3) 7_11_3 Каждый из десяти гвардейцев кардинала Ришелье  
4) 7_11_4 Нестандартный футбольный мяч сшит   
5) 7_11_5 Какое наибольшее число рёбер может быть в  
6) 7_11_6 На рисунке изображён двудольный граф.  
7) 7_11_7 В городе есть 3 секции по шахматам:  
8) 7_11_8 В компании пять эльфов, пять гномов и один хоббит  
9)  7_11_9 В стране есть города и посёлки.   

Задачи с разбором

Разбор 1 "Задача про учеников класса"

Задача 1. Про некоторый класс известно, что в нём больше 30 человек, но меньше 40. Каждый мальчик дружит с тремя девочками, а каждая девочка — с четырьмя мальчиками. Сколько человек в классе?

  
Разбор 2 "Задача про детей в лагере"
Задача 2. В лагерь приехали дети. У каждого из детей ровно 5 знакомых мальчиков и ровно 5 знакомых девочек. Докажите, что число детей делится на 4.  
Разбор 3 "Задача про игру в классики"

Задача 3. Для игры в классики на земле нарисован ряд клеток, в которые вписаны по порядку числа от 1 до 10, как на рисунке.

1 4 5 8 9
2 3 6 7 10
 

Женя прыгнула снаружи в клетку 1, затем попрыгала по остальным клеткам (каждый прыжок — на соседнюю по стороне клетку) и выпрыгнула наружу из клетки 10. Известно, что на клетке 1 Женя была один раз, на клетке 2 — два раза, ……, на клетке 9 — девять раз. Сколько раз побывала Женя на клетке 10?

  
Разбор 4 "Задача про расстановку шахматных коней"
Задача 4. Можно ли расставить 777 шахматных коней на доске 10000×10000 так, чтобы каждый из них бил ровно 4 других?  
Разбор 5 "Задача про граф без треугольников"
Задача 5. В графе со 100 вершинами без треугольников (циклов длины 3) степени всех вершин больше 40. Докажите, что в этом графе нет циклов длины 5.  

Печать