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

Конспект _Введение в графы


Комби-7 Введение в графы. Часть 1 Определения 

Пусть дано некоторое множество точек, некоторые пары из которых соединены. Такая конструкция называется графом. Точки называются вершинами, а соединения между ними называются рёбрами.

Количество рёбер, которые выходят из данной вершины, называется степенью этой вершины.

В задачах графы могут описываться разными способами. Например, следующие три задачи описывают одну и ту же математическую конструкцию.

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

Задача. Докажите, что в любой компании из 7 человек есть двое с одинаковым числом знакомых среди этой компании.

Задача. Некоторые из 7 городов соединены железными дорогами. Докажите, что существуют 2 города, из которых выходит одинаковое количество дорог.

Комби-7 Введение в графы. Часть 2 Подсчёт числа рёбер

Лемма. Сумма степеней всех вершин графа равна удвоенному количеству рёбер.

Задача. В государстве 111 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?

Задача. В государстве 111 городов. Могут ли из каждого города выходить ровно 3 дороги?

Задача. У марсиан бывает только нечётное число рук. Однажды все марсиане взялись за руки так, что свободных рук не осталось. Докажите, что число марсиан чётно.

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

Задача. На занятие кружка пришли 24 школьника, среди них отличник Лёша. Руководитель спросил у каждого из них, кроме Лёши, сколько у них знакомых среди остальных пришедших. В ответ прозвучали только числа 3 и 5. Докажите, что Лёша с кем-нибудь знаком.

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

1) 7_10_1 В Липецкой области существуют дороги

  
2) 7_10_2 Построим по предыдущей задаче   
3) 7_10_3 В стране Цифра есть 9 городов   
4) 7_10_4 В стране Циферка есть 9 городов  
5) 7_10_5 У графа пять вершин имеют степень  
6) 7_10_6 В некотором государстве 10 городов   
7) 7_10_7 В графе n вершин,  
8) 7_10_8 На кружок по математике пришло 7 человек  
9) 7_10_9 Вася выписал в ряд степени всех вершин графа  
10) 7_10_10  графе 100 вершин,   
11) 7_10_11 В графе 18 вершин, причём  

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

Разбор 1 "Задача про дороги"
Задача 1. В стране из каждого города выходит три дороги. Может ли общее количество дорог равняться 1000?  
Разбор 2 "Задача про отрезки"
Задача 2. Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?  
Разбор 3 "Задача про дорожную сеть"
Задача 3. В неизвестной стране из города Столичный выходит 21 дорога, а из города Дальний — ровно одна. Из остальных городов выходит по 20 дорог. Докажите, что из города Дальний можно попасть в Столичный.  
Разбор 4 "Задача о дорожной сети"
Задача 4. В стране некоторые пары городов соединены дорогами. Между двумя городами A и B этой страны существует ровно один путь по дорогам, который проходит через каждый город не более одного раза. Может ли из каждого города выходить чётное число дорог?  

Печать