Задачі на графи

Що таке графи?

Теорія графів не входить до шкільної програми з математики, тому в умовах задач оімпіадного рівня ми не побачимо слова "граф". Проте завдання з теорії графів легко впізнавані - найчастіше це завдання про людей і знайомства, або про міста і дороги. Розберемося з цим поняттям.

Графом в математиці називається креслення, що складається з точок, з'єднаних відрізками. Ці точки є вершинами графа, а відрізки (вони можуть бути і кривими; деякі графи взагалі неможливо побудувати так, щоб усі лінії були прямими) - ребрами графа. Дві вершини, з'єднані ребром, називаються сусідніми. Послідовність ребер, що з'єднують дві вершини, називається шляхом. Степенем вершини в графі називається число ребер, що виходять з неї. Ми говоримо, що вершина графа парна, якщо її степінь парний, і що вершина непарна - в іншому випадку.

Задачі з розв'язанням

1. У державі 100 міст, з кожного виходить 2 дороги, окрім столиці, звідки виходить 5 доріг і міста Гірський, звідки виходить одна єдина дорога. Скільки всього доріг в державі? [20]

РОЗВ'ЯЗАННЯ. Складемо кількість доріг, що виходять з усіх міст: 98 * 2 +5 +1 = 202. Це число - кількість кінців всіх доріг. Оскільки кожна дорога має 2 кінці, то кількість доріг буде вдвічі менше, а саме 101. Аналогічними міркуваннями доводиться, що в будь-якому графі кількість ребер вдвічі менше суми ступенів усіх вершин.

2. На острів Сігма завезли 13 телефонів. Голова хоче організувати таку схему телефонного зв'язку, щоб з'єднати кожен телефон рівно з 7-ма іншими. Чи вдасться це йому?

РОЗВ’ЯЗАННЯ. Порахуємо, скільки проводів потрібно, щоб здійснити таку схему. Кінців проводів буде 13 * 7 = 91, а самих проводів - удвічі менше, тобто 45,5 штук. Це означає, що така схема зв'язку неможлива.

Зауваження. Число непарних вершин будь-якого графа парне (саме ця властивість заважає побудувати мережу зв'язку в попередній задачі).

Мало задач?

1. В шахматном турнире по круговой системе участвуют семь школьников. Известно, что Ваня сыграл шесть партий, Толя – пять, Леша и Дима – по три, Семен и Илья – по две, Женя – одну. С кем сыграл Леша?

2. Между девятью планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер, Юпитер – Марс и Марс – Уран. Можно ли добраться с Земли до Марса?

3. Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.

4. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 – по 4 друга, а 10 – по 5 друзей?

5. В графе каждая вершина – синяя или зелёная. При этом каждая синяя вершина связана с пятью синими и десятью зелёными, а каждая зелёная – с девятью синими и шестью зелёными. Каких вершин больше – синих или зелёных?

6. На 8 марта каждый из 10 мальчиков класса подарил по цветку 8 одноклассницам. Известно, что каждая девочка получила по 5 цветков. Сколько всего девочек в классе?

7. В классе 20 человек. На празднике каждый мальчик подарил каждой девочке по цветку. Какое наибольшее число цветков могло быть подарено?