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

UptoLike

ВУЗ: 

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

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

Рубрика: 

6
почему следует скорее от математика ожидать это-
го решения, нежели от какого-нибудь другого че-
ловека, ибо это решение подкрепляется одним
только рассуждением, и нет необходимости при-
влекать для нахождения этого решения какие-либо
законы, свойственные математике. Итак, я не
знаю, каким образом получается, что вопросы,
имеющие совсем мало отношения
к математике,
скорее разрешается математиками, чем другими».
Так можно ли обойти Кенигсбергские мос-
ты, проходя только один раз через каждый из этих
мостов? Чтобы найти ответ, продолжим письмо
Эйлера к Маринони: «Вопрос состоит в том, чтобы
определить, можно ли обойти все эти семь мостов,
проходя через каждый только однажды, или нель
-
зя. Мое правило приводит к следующему решению
этого вопроса. Прежде всего, нужно смотреть,
сколько есть участков, разделенных водой, – та-
ких, у которых нет другого перехода с одного на
другой, кроме как через мост. В данном примере
таких участков четыре – A, B, C, D. Далее нужно
различать, является ли число мостов, ведущих к
этим отдельным
участкам, четным или нечетным.
Так, в нашем случае к участку A ведут пять мос-
тов, а к остальным – по три моста, т. е. Число мос-
тов, ведущих к отдельным участкам, нечетно, а
этого одного уже достаточно для решения задачи.
Когда это определено, применяем следующее пра-
171
12.3.
13. Даны графы G
1
и G
2
. Найдите G
1
® G
2
, G
1
G
2
, G
1
« G
2
, G
1
×
G
2
,. Для графа G
1
® G
2
найдите
матрицы смежности, инцидентности, сильных
компонент, маршрутов длины 2 и все маршруты
длины 2, исходящие из вершины 1.
13.1.
13.2.
13.3.
G
1
G
2
1
2
3 4
1
2
3
G
1
G
2
1
2
3 4
б
2
3 
почему следует скорее от математика ожидать это-      12.3.
го решения, нежели от какого-нибудь другого че-
ловека, ибо это решение подкрепляется одним
только рассуждением, и нет необходимости при-
влекать для нахождения этого решения какие-либо
законы, свойственные математике. Итак, я не
знаю, каким образом получается, что вопросы,
имеющие совсем мало отношения к математике,           13. Даны графы G1 и G2. Найдите G1 ® G2, G1 ­
скорее разрешается математиками, чем другими».        G2, G1 « G2, G1 × G2,. Для графа G1 ® G2 найдите
       Так можно ли обойти Кенигсбергские мос-        матрицы смежности, инцидентности, сильных
ты, проходя только один раз через каждый из этих      компонент, маршрутов длины 2 и все маршруты
мостов? Чтобы найти ответ, продолжим письмо           длины 2, исходящие из вершины 1.
Эйлера к Маринони: «Вопрос состоит в том, чтобы
определить, можно ли обойти все эти семь мостов,      13.1.        1       2
                                                                                         1
проходя через каждый только однажды, или нель-
зя. Мое правило приводит к следующему решению                 G1               G2
этого вопроса. Прежде всего, нужно смотреть,
сколько есть участков, разделенных водой, – та-                        4   3
ких, у которых нет другого перехода с одного на                                      3       2
другой, кроме как через мост. В данном примере        13.2.
таких участков четыре – A, B, C, D. Далее нужно
                                                                   1       2
различать, является ли число мостов, ведущих к                                               б
этим отдельным участкам, четным или нечетным.
                                                              G1               G2
Так, в нашем случае к участку A ведут пять мос-
тов, а к остальным – по три моста, т. е. Число мос-
тов, ведущих к отдельным участкам, нечетно, а                          4   3
этого одного уже достаточно для решения задачи.                                      3       2
Когда это определено, применяем следующее пра-        13.3.

                           6                                                   171

Страницы