Основные понятия теории графов. Гладких О.Б - 59 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

Составители: 

Рубрика: 

118
сматриваемой компании нельзя выделить ни четы-
рехугольник, ни треугольник, поскольку тогда из
оставшихся нельзя будет составить компанию,
удовлетворяющую условию, т.е. схема знакомства
единственная. Всякую схему, напоминающую
многоугольник, принято называть циклом. (Древ-
ние греки «цикл» называли «колесом»; и действи-
тельно на рис. 5.5 изображено нечто, напоминаю-
щее колесо и с успехом
заменяющее в рассматри-
ваемой ситуации многоугольник.)
Рис. 5.5.
Задача 5.4.
Может ли так случиться, что в одной компа-
нии из шести человек каждый знаком с двумя и
только двумя другими?
Решение.
Участника этой компании изобразим верши-
ной графа, а отношение знакомства между двумя
участниками – ребром. Изобразим графы, которые
59
Пример 1.28.
Найдем диаметр графа G, изображенного на
рис. 1.22.
Рис. 1.22.
Матрица расстояний имеет вид
Р =
01312
10211
32021
11201
21110
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
отсюда
е (1) = 3, е (2) = 2, е (3) = 3, е (4) = 2, е (5) = 2
и, следовательно, d (G) = 3. Вершины 1 и 3 явля-
ются периферийными.
4
5
3
2
1
сматриваемой компании нельзя выделить ни четы-
рехугольник, ни треугольник, поскольку тогда из                         Пример 1.28.
оставшихся нельзя будет составить компанию,             Найдем диаметр графа G, изображенного на
удовлетворяющую условию, т.е. схема знакомства    рис. 1.22.
единственная. Всякую схему, напоминающую                            4                   5
многоугольник, принято называть циклом. (Древ-
ние греки «цикл» называли «колесом»; и действи-
тельно на рис. 5.5 изображено нечто, напоминаю-                               2
щее колесо и с успехом заменяющее в рассматри-
ваемой ситуации многоугольник.)

                                                                    1                     3
                                                                          Рис. 1.22.

                                                        Матрица расстояний имеет вид
                                                                       ⎛0    1 3 1 2⎞
                                                                       ⎜1    0 2 1 1 ⎟⎟
                    Рис. 5.5.                                       Р= ⎜
                                                                       ⎜3    2 0 2 1⎟
                                                                       ⎜              ⎟
                     Задача 5.4.                                       ⎜1    1 2 0 1⎟
                                                                       ⎜2    1 1 1 0 ⎟⎠
     Может ли так случиться, что в одной компа-                        ⎝
нии из шести человек каждый знаком с двумя и      отсюда
только двумя другими?                                 е (1) = 3, е (2) = 2, е (3) = 3, е (4) = 2, е (5) = 2
                   Решение.                       и, следовательно, d (G) = 3. Вершины 1 и 3 явля-
     Участника этой компании изобразим верши-     ются периферийными.
ной графа, а отношение знакомства между двумя
участниками – ребром. Изобразим графы, которые


                          118                                                     59

Страницы