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

UptoLike

ВУЗ: 

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

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

Рубрика: 

172
13.4.
14. Найдите матрицы фундаментальных циклов,
фундаментальных разрезов, радиус и диаметр, ми-
нимальное множество покрывающих цепей графа
G. Является ли изображенный граф эйлеровым?
Является ли изображенный граф планарным?
14.1.
14.2.
G
2
3
4
1
2
3
1
2
G
1
G
1
G
2
1
2
3 4
1
2
3
1
G
5
Введение
Родоначальником теории графов принято
считать математика Леонарда Эйлера (1707-1783).
Историю возникновения этой теории можно про-
следить по переписке великого ученого. Вот пере-
вод латинского текста, который взят из письма
Эйлера к итальянскому математику и инженеру
Маринони, отправленного из Петербурга 13 марта
1736 года: «Некогда мне была предложена задача
об острове, расположенном в
городе Кенигсберге
и окруженном рекой, через которую перекинуто
семь мостов. Спрашивается, может ли кто-нибудь
непрерывно обойти их, проходя только однажды
через каждый мост. И тут же мне было сообщено,
что никто еще до сих пор не мог это проделать, но
никто и не доказал, что это невозможно… После
долгих
размышлений я нашел легкое правило, ос-
нованное на вполне убедительном доказательстве,
с помощью которого можно во всех задачах такого
рода тотчас же определить, может ли быть совер-
шен такой обход через какое угодно число и как
угодно расположенных мостов или не может». Ке-
нигсбергские же мосты расположены так, что их
можно
представить в виде схемы (смотри рис. 1).
По поводу обнаруженного им способа ре-
шать задачи подобного рода Эйлер писал: «Это
решение по своему характеру, по-видимому, имеет
мало отношения к математике, и мне непонятно, 
                                                                                    Введение
            1               2                     1
                                                                    Родоначальником теории графов принято
            G1                      G2                        считать математика Леонарда Эйлера (1707-1783).
                                                              Историю возникновения этой теории можно про-
                                                              следить по переписке великого ученого. Вот пере-
                        4   3
                                              3       2       вод латинского текста, который взят из письма
13.4.                                                         Эйлера к итальянскому математику и инженеру
                                                              Маринони, отправленного из Петербурга 13 марта
                    1
                1           2                     1           1736 года: «Некогда мне была предложена задача
                                                              об острове, расположенном в городе Кенигсберге
            G1                      G2
                                                              и окруженном рекой, через которую перекинуто
                                                              семь мостов. Спрашивается, может ли кто-нибудь
                        4       3
                                          3               2
                                                              непрерывно обойти их, проходя только однажды
                                                              через каждый мост. И тут же мне было сообщено,
                                                              что никто еще до сих пор не мог это проделать, но
14. Найдите матрицы фундаментальных циклов,                   никто и не доказал, что это невозможно… После
фундаментальных разрезов, радиус и диаметр, ми-               долгих размышлений я нашел легкое правило, ос-
нимальное множество покрывающих цепей графа                   нованное на вполне убедительном доказательстве,
G. Является ли изображенный граф эйлеровым?                   с помощью которого можно во всех задачах такого
Является ли изображенный граф планарным?                      рода тотчас же определить, может ли быть совер-
                                                              шен такой обход через какое угодно число и как
14.1.                                                         угодно расположенных мостов или не может». Ке-
                                                              нигсбергские же мосты расположены так, что их
        G                                                     можно представить в виде схемы (смотри рис. 1).
                                                                    По поводу обнаруженного им способа ре-
                                                              шать задачи подобного рода Эйлер писал: «Это
                                                              решение по своему характеру, по-видимому, имеет
14.2.                                                         мало отношения к математике, и мне непонятно,

                                    172                                                 5

Страницы