Графы Определения. Будем называть графом множество точек (вершин), некоторые из которых соединены между собой линиями (рёбрами). Граф называется связным, если от любой его вершины можно по рёбрам добраться до любой другой. Степенью вершины называется количество выходящих из этой вершины рёбер. Упражнения 1) В графе три вершины степени 3, четыре вершины степени 4, пять вершин степени 5 и шесть вершин степени 6. Сколько в графе рёбер? 3) Докажите, что количество людей, сделавших в течение своей жизни нечётное число рукопожатий, чётно. Лемма о рукопожатиях. Количество вершин нечетной степени в графе четно. 1. 2. Существует ли 8-вершинный граф, степени вершин которого равны a) 8, 6, 6, 5, 3, 2, 1, 1? б) 7, 7, 5, 4, 4, 2, 2, 1? в) 7, 3, 3, 3, 3, 2, 2, 1? г) 7,5,5,5,4,3, 2, 2? Для каждого случая нарисуйте хотя бы один подходящий граф, либо докажите, что такой граф нарисовать нельзя. В некоторой стране 17 городов и 50 дорог. Некоторые города соединены дорогами. Известно, что из некоторых шести городов выходит по 6 дорог, из шести других городов по 3 дороги, еще из 3 городов по 9 дорог, и еще из одного 7 дорог. Сколько дорог выходит из оставшегося города? 3. Докажите, что в любом графе с п вершинами найдутся две вершины одинаковой степени. 4. Может ли в государстве, в котором из каждого города выходят 3 дороги, быть ровно 100 дорог? Каждая дорога соединяет ровно два города. 5. В шахматном турнире один шахматист заболел и не доиграл свои партии. Всего в турнире было проведено 24 встречи. Сколько шахматистов участвовало в турнире, и сколько партий сыграл выбывший участник? одной шахматной доске стоят 64 пронумерованных коня, на друй – 64 пронумерованных короля. Может ли быть, что для каждой меров если короли с этими номерами бьют друг друга, то и пары кони - 1e?

1) В графе три вершины степени 3, четыре вершины степени 4, пять вершин степени 5 и шесть вершин степени 6. Сколько в графе рёбер?

Разбираемся:

• Сумма степеней всех вершин равна удвоенному числу рёбер.
• Вычислим сумму степеней вершин:

\[3 \cdot 3 + 4 \cdot 4 + 5 \cdot 5 + 6 \cdot 6 = 9 + 16 + 25 + 36 = 86\]

• Теперь найдём число рёбер, разделив полученную сумму на 2:

\[\frac{86}{2} = 43\]

Ответ: 43 ребра

1. Существует ли 8-вершинный граф, степени вершин которого равны

• a) 8, 6, 6, 5, 3, 2, 1, 1?

Сумма степеней: 8 + 6 + 6 + 5 + 3 + 2 + 1 + 1 = 32. Так как сумма четная, то теоретически такой граф может существовать. Однако, вершина степени 8 должна быть соединена со всеми остальными вершинами, включая вершину степени 1, что невозможно, так как у вершины степени 1 может быть только одно ребро. Следовательно, такой граф не существует.

• б) 7, 7, 5, 4, 4, 2, 2, 1?

Сумма степеней: 7 + 7 + 5 + 4 + 4 + 2 + 2 + 1 = 32. Сумма четная, такой граф теоретически может существовать. Однако, вершина степени 7 должна быть соединена со всеми остальными вершинами, что возможно.

• в) 7, 3, 3, 3, 3, 2, 2, 1?

Сумма степеней: 7 + 3 + 3 + 3 + 3 + 2 + 2 + 1 = 24. Сумма четная, такой граф теоретически может существовать. Однако, вершина степени 7 должна быть соединена со всеми остальными вершинами, что возможно.

• г) 7, 5, 5, 5, 4, 3, 2, 2?

Сумма степеней: 7 + 5 + 5 + 5 + 4 + 3 + 2 + 2 = 33. Сумма нечетная, следовательно, такой граф не существует.

2. В некоторой стране 17 городов и 50 дорог. Некоторые города соединены дорогами. Известно, что из некоторых шести городов выходит по 6 дорог, из шести других городов по 3 дороги, еще из 3 городов по 9 дорог, и еще из одного 7 дорог. Сколько дорог выходит из оставшегося города?

Разбираемся:

• Сумма дорог, выходящих из известных городов:

\[6 \cdot 6 + 6 \cdot 3 + 3 \cdot 9 + 1 \cdot 7 = 36 + 18 + 27 + 7 = 88\]

• Всего городов 17, значит, осталось 17 - 6 - 6 - 3 - 1 = 1 город.
• Пусть из оставшегося города выходит x дорог. Тогда:

\[88 + x = 2 \cdot 50\]

\[88 + x = 100\]

\[x = 100 - 88\]

\[x = 12\]

Ответ: 12 дорог

3. Докажите, что в любом графе с n вершинами найдутся две вершины одинаковой степени.

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

4. Может ли в государстве, в котором из каждого города выходят 3 дороги, быть ровно 100 дорог? Каждая дорога соединяет ровно два города.

Предположим, что в государстве n городов, и из каждого выходит 3 дороги. Тогда общее количество дорог равно сумме степеней всех вершин, деленной на 2, так как каждая дорога соединяет 2 города.

Тогда, \[\frac{3n}{2} = 100\]

\[3n = 200\]

\[n = \frac{200}{3}\]

Так как n должно быть целым числом, а 200/3 не является целым числом, то такая ситуация невозможна.

Ответ: Нет, не может.

5. В шахматном турнире один шахматист заболел и не доиграл свои партии. Всего в турнире было проведено 24 встречи. Сколько шахматистов участвовало в турнире, и сколько партий сыграл выбывший участник?

Разбираемся:

• Пусть участвовало n шахматистов. Каждый шахматист должен сыграть с каждым, кроме себя.
• Общее число партий, которые должны были быть сыграны: \[\frac{n(n-1)}{2}\]
• Пусть выбывший участник сыграл x партий. Тогда общее число сыгранных партий:

\[\frac{n(n-1)}{2} - x = 24\]

Тут нужно подобрать n и x так, чтобы уравнение было верным. Попробуем разные значения n:

• Если n = 7, то \[\frac{7 \cdot 6}{2} = 21\] что меньше 24.
• Если n = 8, то \[\frac{8 \cdot 7}{2} = 28\] Тогда x = 28 - 24 = 4. Это возможно.

Значит, участвовало 8 шахматистов, и выбывший сыграл 4 партии.

Ответ: 8 шахматистов, выбывший сыграл 4 партии.

На одной шахматной доске стоят 64 пронумерованных коня, на другой – 64 пронумерованных короля. Может ли быть, что для каждой пары номеров если короли с этими номерами бьют друг друга, то и кони - тоже?

Этот вопрос сформулирован нечетко и не имеет однозначного ответа, потому что не указано, как именно должны быть пронумерованы кони и короли, и что значит «кони тоже». Предположим, что кони и короли стоят на досках в одинаковом порядке, и если король с номером i бьет короля с номером j, то конь с номером i бьет коня с номером j. В таком случае это возможно.