Введение в теорию графов. Индивидуальные задания (66
.pdf
31
32
Задание 18. Раскраска карт и вершин графов
I. Найдите правильную раскраску вершин графа минимальным числом красок, обозначая их цифрами 1, 2, 3, 4. Укажите число использованных красок. Запишите множества одинаково окрашенных вершин. Постройте карту, геометрически двойственную графу, и раскрасьте ее в соответствии с раскраской графа.
33
II. Найдите правильные раскраски карт, используя минимальное число красок. Для раскраски какой карты достаточно всего двух красок? Почему?
III. Постройте планарные графы каркасов правильных многогранников и раскрасьте получившиеся карты минимальным числом красок, не забывая о внешней грани. Укажите число красок, понадобившихся для каждого из многогранников.
34
Задание 19.
Матрицы смежностей и инциденций
1)Нарисуйте диаграмму графа с заданной матрицей смежностей.
2)Вычислите степени А2 , А3 , А4 матрицы смежностей А, причем последнюю – двумя способами.
3)Найдите степени di вершин графа по А и по А2 .
4)Определите по матрице А3 число треугольников с вершиной в каждой из вершин графа.
5) Обладает ли каждая из матриц А, А2 , А3 , А4 симметрией? Проверьте
иобъясните почему.
6)Выберите два максимальных элемента aij( 4) матрицы А4 и перечисли-
те пути длины 4 из i в j , пользуясь диаграммой графа. Совпадает ли их число с
aij( 4) ?
7)Изобразите диаграмму дополнения заданного Вам графа и составьте его матрицу смежностей. Сравните матрицы смежностей графа и его дополнения.
8)Как по матрице смежностей графа определить висячую вершину, изолированную вершину?
9)Составьте матрицу инциденций I графа и найдите с ее помощью степени вершин. Изменив знак одной из единиц каждого столбца матрицы I на противоположный, запишите полученную матрицу В и с ее помощью определите матрицу смежностей графа.
10)Запишите матрицы смежностей и инциденций простого цикла C5 ,
простой цепи P5 , полного графа K4 , полного двудольного графа K2,4 , графа
K2UK4 из двух компонент. Как для последних двух графов удобно пометить вершины? Какими особенностями обладает каждая из записанных матриц?
35
1. |
|
0 |
1 |
1 |
1 |
|
|
|
1 |
0 |
0 |
0 |
|
|
|
|
||||
|
|
1 |
0 |
0 |
1 |
|
|
|
|
||||
|
|
1 |
0 |
1 |
0 |
|
|
|
|
||||
4. |
|
0 |
1 |
0 |
1 |
|
|
|
1 |
0 |
1 |
1 |
|
|
|
|
||||
|
|
0 |
1 |
0 |
0 |
|
|
|
|
||||
|
|
1 |
1 |
0 |
0 |
|
|
|
|
||||
7. |
|
0 |
1 |
1 |
0 |
|
|
|
1 |
0 |
1 |
0 |
|
|
|
|
||||
|
|
1 |
1 |
0 |
1 |
|
|
|
|
||||
|
|
0 |
0 |
1 |
0 |
|
|
|
|
||||
10. |
|
0 |
0 |
0 |
1 |
|
|
|
0 |
0 |
1 |
1 |
|
|
|
|
||||
|
|
0 |
1 |
0 |
1 |
|
|
|
|
||||
|
|
1 |
1 |
1 |
0 |
|
|
|
|
Варианты задания
2. |
|
0 |
1 |
1 |
1 |
|
|
|
1 |
0 |
0 |
0 |
|
|
|
|
||||
|
|
1 |
0 |
0 |
0 |
|
|
|
|
||||
|
|
1 |
0 |
0 |
0 |
|
|
|
|
||||
5. |
|
0 |
1 |
0 |
0 |
|
|
|
1 |
0 |
1 |
1 |
|
|
|
|
||||
|
|
0 |
1 |
0 |
0 |
|
|
|
|
||||
|
|
0 |
1 |
0 |
0 |
|
|
|
|
||||
8. |
|
0 |
0 |
1 |
0 |
|
|
|
0 |
0 |
1 |
0 |
|
|
|
|
||||
|
|
1 |
1 |
0 |
1 |
|
|
|
|
||||
|
|
0 |
0 |
1 |
0 |
|
|
|
|
||||
11. |
|
0 |
0 |
0 |
1 |
|
|
|
0 |
0 |
0 |
1 |
|
|
|
|
||||
|
|
0 |
0 |
0 |
1 |
|
|
|
|
||||
|
|
1 |
1 |
1 |
0 |
|
|
|
|
3. |
|
0 |
1 |
0 |
1 |
|
|
|
1 |
0 |
1 |
0 |
|
|
|
|
||||
|
|
0 |
1 |
0 |
1 |
|
|
|
|
||||
|
|
1 |
0 |
1 |
0 |
|
|
|
|
||||
6. |
|
0 |
0 |
1 |
1 |
|
|
|
0 |
0 |
1 |
1 |
|
|
|
|
||||
|
|
1 |
1 |
0 |
0 |
|
|
|
|
||||
|
|
1 |
1 |
0 |
0 |
|
|
|
|
||||
9. |
|
0 |
1 |
0 |
1 |
|
|
|
1 |
0 |
1 |
0 |
|
|
|
|
||||
|
|
0 |
1 |
0 |
0 |
|
|
|
|
||||
|
|
1 |
0 |
0 |
0 |
|
|
|
|
||||
12. |
|
0 |
0 |
1 |
1 |
|
|
|
0 |
0 |
1 |
0 |
|
|
|
|
||||
|
|
1 |
1 |
0 |
0 |
|
|
|
|
||||
|
|
1 |
0 |
0 |
0 |
|
|
|
|
36
Задание 20.
Социометрические матрицы, турниры, ранги индивидуумов
1)Нарисуйте диаграмму графа К5 и постройте, используя ее, диаграмму
турнира, выбрав на каждом ребре произвольное направление, но так, чтобы полустепени исхода и захода для каждой вершины были отличны от нуля. Составьте для полученного орграфа матрицу смежностей D.
2)Определите для каждой вершины ее полустепени исхода и захода: а) по диаграмме орграфа; б) по матрице смежностей D.
3)Пусть все элементы какой-либо строки (какого-либо столбца) матрицы D, кроме диагонального, отличны от 0. Что это означает с точки зрения доминирования индивидуумов? Проверьте по матрице D, что в составленном вами турнире нет однозвенного победителя и однозвенного проигравшего.
4)Найдите матрицу D2 двумя способами: алгебраически ( D2 D D ) и по диаграмме графа. Какой смысл имеют элементы dij( 2) матрицы D2 ?
5)Найдите матрицу D D2 и определите с ее помощью ранг каждого индивидуума. Сколько однозвенных или двухзвенных лидеров имеет турнир? Установите ответ на этот вопрос как по диаграмме турнира, так и с помощью матрицы D D2 .
Задание 21.
Определение порядка следования элементов по заданному списку предпочтений
1)Нарисуйте диаграмму орграфа (1) и найдите с помощью его матрицы смежностей порядок следования вершин. Выделите эту цепь на диаграмме, пронумеровав ребра в порядке их следования.
2)Определите порядок, в котором следует запустить 15 компьютерных программ друг за другом, выполнив требования (2).
37
|
|
|
|
|
|
Варианты задания |
|
|
||
1 |
1) |
1 2,3,6 |
2) |
1 2,6,7 |
6 |
7,12 |
11 |
10 |
||
|
|
2 4,6 |
|
2 4,8,14 |
7 |
13 |
12 |
11 |
||
|
|
3 |
2,4,5 |
|
3 |
4 |
8 |
7,9,14 |
13 |
5,12 |
|
|
5 |
4 |
|
4 |
9,15 |
9 15 |
14 |
5,6 |
|
|
|
6 4,5 |
|
5 3,11 |
10 3,9 |
|
|
|||
2 |
1) |
5 2,3,6 |
2) |
1 2,7,13 |
6 5,12 |
11 |
10 |
|||
|
|
1 4 |
|
2 |
3,8,14 |
7 |
6 |
12 |
11 |
|
|
|
2 |
4,6 |
|
3 |
9,15 |
8 |
7,9,14 |
13 |
7,12 |
|
|
3 1,2,4 |
|
4 |
3 |
9 15 |
14 13,5 |
|||
|
|
6 |
4,1 |
|
5 |
4,11 |
10 4,9 |
|
|
|
3 |
1) |
1 3 |
2) |
1 13 |
6 |
1,12 |
11 |
10 |
||
|
|
2 |
3,6 |
|
2 |
4,8,14 |
7 |
1,2,6 |
12 |
11 |
|
|
4 1,2,3 |
|
3 |
4 |
8 1,9,14 |
13 5,12 |
|||
|
|
5 |
2,4,6 |
|
5 |
3,11 |
9 15 |
14 |
5,6 |
|
|
|
6 |
1,13 |
|
4 |
9,15 |
10 3,9 |
|
|
|
4 |
1) |
1 3 |
2) |
1 13 |
6 |
1,12 |
11 |
2 |
||
|
|
2 1,3 |
|
2 3,9 |
7 1,6,10 |
12 |
11 |
|||
|
|
4 |
1,3,6 |
|
3 |
4 |
8 |
1,9,14 |
13 |
5,12 |
|
|
5 |
2,4,6 |
|
4 |
9,15 |
9 15 |
14 |
5,6 |
|
|
|
6 2,3 |
|
5 3,11 |
10 4,8,14 |
|
|
|||
5 |
1) |
1 3,4,6 |
2) |
1 10 |
6 2,5 |
11 7,12,13 |
||||
|
|
2 |
3,4 |
|
2 |
1 |
7 |
6 |
12 |
3,8,14 |
|
|
4 |
3 |
|
3 |
9,15 |
8 |
7,9,14 |
13 |
2,7 |
|
|
5 1,2,6 |
|
4 |
3 |
9 15 |
14 5,13 |
|||
|
|
6 |
2,3 |
|
5 |
1,4 |
10 4,9 |
|
|
|
6 |
1) |
1 2,3,6 |
2) |
1 10 |
6 |
2,5 |
11 |
3,7,12 |
||
|
|
2 |
3 |
|
2 |
1 |
7 |
6 |
12 |
4,8,13 |
|
|
4 2,3 |
|
3 2,7 |
8 4,7,9 |
13 9,15 |
||||
|
|
5 |
1,4,6 |
|
4 |
3,5 |
9 15 |
14 |
3 |
|
|
|
6 |
3,4 |
|
5 |
1,14 |
10 9,14 |
|
|
|
7 |
1) |
2 |
1,3 |
2) |
1 10 |
6 |
1,14 |
11 |
3,8,12 |
|
|
|
3 |
1 |
|
2 |
1 |
7 |
4,8,9 |
12 |
4,7,13 |
|
|
4 2,3,5,6 |
|
3 2,8 |
8 |
5 |
13 9,15 |
|||
5 3,6 |
4 3,6 |
9 15 |
14 13 |
6 1,2 |
5 2,6 |
10 9,14 |
|
|
|
38 |
|
8 |
1) |
1 3,6 |
2) |
2 13 |
7 4,8,9 |
12 4,7,13 |
||||
|
|
2 3,5 |
|
3 14 |
8 |
5 |
13 |
1,9 |
||
|
|
3 |
5 |
|
4 3,6 |
9 |
1 |
14 |
15 |
|
|
|
4 1,2,3,6 |
|
5 6,14 |
10 2,9 |
15 10 |
||||
|
|
6 |
2,5 |
|
6 |
2,15 |
11 3,8,12 |
|
|
|
9 |
1) |
1 4,6 |
2) |
2 13 |
7 4,8,11 |
12 4,7,13 |
||||
|
|
2 |
4,5 |
|
3 14 |
8 |
5 |
13 |
1,11 |
|
|
|
3 |
1,2,4,6 |
|
4 3,6 |
9 |
3,8,12 |
14 |
15 |
|
|
|
4 |
5 |
|
5 6,14 |
10 2,11 |
15 10 |
|||
|
|
6 |
2,5 |
|
6 |
2,15 |
11 1 |
|
|
|
10 |
1) |
1 2,4 |
2) |
1 3,9 |
6 7,12 |
11 |
1 |
|||
|
|
2 |
5,6 |
|
2 |
4,8,14 |
7 |
13 |
12 |
11 |
|
|
3 |
1,2,4,6 |
|
3 |
4 |
8 |
7,9,14 |
13 |
5,12 |
|
|
4 |
5 |
|
4 9,15 |
9 |
15 |
14 5,6 |
||
|
|
6 |
4,5 |
|
5 |
3,11 |
10 2,6,7 |
|
|
|
11 |
1) |
1 5 |
2) |
1 10 |
6 2,11 |
11 1,4 |
||||
|
|
2 |
5,6 |
|
2 |
1 |
7 |
6 |
12 |
3,8,14 |
|
|
3 |
1,2,4,6 |
|
3 |
9,15 |
8 |
7,9,14 |
13 |
2,7 |
|
|
4 1,2 |
|
4 |
3 |
9 |
15 |
14 11,13 |
||
|
|
6 |
1,5 |
|
5 |
7,12,13 |
10 4,9 |
|
|
|
12 |
1) |
1 2 |
2) |
1 10 |
6 3,7,12 |
11 2,5 |
||||
|
|
3 |
1,4,5,6 |
|
2 |
1 |
7 |
11 |
12 |
4,8,13 |
|
|
4 |
1,5 |
|
3 |
2,7 |
8 |
4,7,9 |
13 |
9,15 |
|
|
5 2,6 |
|
4 3,5 |
9 |
15 |
14 |
13 |
||
|
|
6 |
1,2 |
|
5 |
1,14 |
10 9,14 |
|
|
|
39
Задание 22 Повторение теорем теории графов
В задании предложен список 10 теорем теории графов. Некоторые из них сопровождаются вопросами, помогающими проанализировать и усвоить доказательства, остальные только сформулированы. Задача студента в первом случае – письменно ответить на вопросы и изложить полное доказательство, во втором – доказав теорему, самостоятельно составить вопросы для анализа доказательства.
Составляя такие вопросы к теоремам 4–10, используйте приведенный анализ первых теорем и приложение к пособию «Советы и вопросы …», с. 29.
Следует отметить, что список теорем, предложенных для анализа, лишь приблизителен. Каждый преподаватель внесет изменения в этот список, расширит его или сузит в зависимости от содержания и характера курса.
1) Теорема Эйлера о числе вершин, ребер и граней выпуклого многогранника p f q 2 .
1.1Как переформулировать теорему Эйлера на языке теории графов?
1.2Каким методом доказывается теорема? По числу каких элементов?
1.3Для какого первоначального графа проверяется справедливость теоремы (первый шаг математической индукции (МИ))?
1.4Что используется для этой проверки?
1.5Для каких графов и как составляется допущение (второй шаг МИ)?
1.6К какому графу осуществляется переход в последнем шаге МИ?
1.7Как от этого графа перейти к допущению? Какое ребро надо отбросить, любое или нет?
1.8Почему при этом переходе число p f q не меняется?
1.9Почему требуется, чтобы граф был планарным?
1.10Где в дальнейшем используется эта теорема?
1.11Останется ли теорема верна, если граф не связен? Рассмотрите случай объединения двух циклов С3 и С4 без общих вершин. Нельзя ли сформулировать
40