 |
|
Практическая работа по теме 5.
Задание 1.В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Решение: Предположим, что это возможно. Рассмотрим тогда граф, вершины которого соответствуют телефонам, а ребра - соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна пяти. Подсчитаем количество ребер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено дважды (оно ведь соединяет две вершины!). Поэтому число ребер графа должно быть равно 15×5/2. Но это число нецелое. Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.
Задание 2.В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
Заметим теперь, что из вышесказанного можно получить следствие: сумма степеней всех вершин графа должна быть четной (иначе ее нельзя было бы разделить на два нацело).
Задание 3. В классе 30 человек. Может ли быть так, что 9 из них имеют по три друга (в этом классе), 11-по четыре друга, а 10-по 5 друзей?
Решение: Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11-степень 4, 10-степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме.
Задание 4. Изоморфны ли графы в парах, изображенных на рис. 31
 а)
| 
|
 б)
| 
|
Рисунок 31.
Решение. В пунктах а) и б) приведены изоморфные графы, что доказывается рисунками 32 а) и 32 б) соответственно.
| а) | |
 б)
| 
|
Рисунок 32.
Задание 4. Задан граф списком ребер
| N ребра | ||||||||||
| Вершины | A | B | C | C | D | E | E | G | B | G |
| Ребра | B | C | D | F | E | F | G | F | F | A |
Начертите его графическое изображение на плоскости, постройте его матрицы инциденций и смежности.
Решение.
Графическая реализация заданного графа:
Матрица инциденций:
| A | -1 | |||||||||
| B | -1 | |||||||||
| C | -1 | |||||||||
| D | -1 | |||||||||
| E | -1 | |||||||||
| F | -1 | -1 | -1 | -1 | ||||||
| G | -1 |
Матрица смежности:
| A | B | C | D | E | F | G | |
| A | |||||||
| B | |||||||
| C | |||||||
| D | |||||||
| E | |||||||
| F | |||||||
| G |
Задание 5. Постройте граф отношения «x+y<=7» на множестве М={1,2,3,4,5,6}. Постройте его матрицы инциденций и смежности.
Решение. Построим граф G(X) c множеством вершин X={Xi=i, i=1,..,6}, причем две вершины Xi и Xj соединяются ребром тогда и только тогда, когда Xi+Xj<=7. Поскольку отношение «x+y<=7» симметрично, граф G(X) неориентированный.
Построим матрицу смежности (вершин).
 |
Здесь элемент Aij обозначает число ребер, идущих из вершины Xi в вершину Xj. Поскольку граф неориентированный, матрица смежности симметрична.
Построим матрицу инциденций.
Здесь элемент Rij равен 1, если вершина Xi инцидентна ребру gj и 0 иначе.
Задание 5.Построить матрицы инцидентности и смежности для графа, изображённого на рисунке 34.
Рис. 34
Решение.
Строим матрицу инцидентности в виде таблицы:
| a | -1 | ||||||
| b | -1 | ||||||
| c | -1 | ||||||
| d | -1 | ||||||
| e | -1 | ||||||
| f | -1 | ||||||
| g |
Матрица смежности выглядит следующим образом:
Задание 5. Имеется 7 (A, B, C, D, E, F, G) городов и таблица минимальных расстояний.
Таблица 6
Построить граф типа «дерево» минимальной суммарной длины.
Решение.
Из табл. 5.13 минимальное расстояние равно 15 (A–E). Соединим эти вершины. Следующее минимальное расстояние 17 (B–G). Соединим эти вершины. Следующее минимальное расстояние 18 (A–B и E–G). Мы можем выбрать только одно (любое) соединение, иначе образуется цикл. Возьмем, например, A–B, а E–G исключим из рассмотрения. Следующим минимальным расстоянием будет 19 (E–F и C–B). В данном случае мы можем соединить обе пары вершин. Очередное минимальное расстояние 21 (B–E) проводить нельзя, так как образуется цикл. Следующее минимальное расстояние 22 (A–F F–G) также следует пропустить (любая из этих пар образует цикл. Расстояние 24 (A–C) также неприемлемо, расстояние 25 (B–D) завершает построение минимальной сети дорог. Суммарная длина всех построенных дорог равна L = 15+17+18+19+19+25 = 113. Решения меньшей длины не существует.
Задание 6.Построить турнирную таблицу для 7 игроков.
Решение. Добавим фиктивного игрока для того, чтобы число участников стало четным. Таблица для 8 участников будет выглядеть так (табл. 7)
Таблица 7
В первой строке построенной таблицы перечислены номера всех участников. В первом туре играют пары из 1‑й и 2‑й строк. Во втором туре играют пары из 1‑й и 3‑й строк и т. д. Один из игроков, например с номером 8, является фиктивным.