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

11. Найти цикломатические и хроматические чис-    вило: если бы число мостов, ведущих к каждому
ла, числа внутренней и внешней устойчивости для   отдельному участку, было четным, то тогда обход,
графов. Изоморфны ли графы?                       о котором идет речь, был бы возможен, и в то же
                                                  время можно было бы начать этот обход с любого
                                                  участка. Если же из этих чисел два были бы нечет-
                                                  ные, ибо только одно быть нечетным не может, то
                                                  и тогда мог бы совершиться переход, как это
                                                  предписано, но только начало обхода непременно
                                                  должно быть взято от одного из тех двух участков,
                                                  к которым ведет нечетное число мостов. Если бы,
12. Найти декартово произведение графов.          наконец, было больше двух участков, к которым
                                                  ведет нечетное число мостов, то тогда такое дви-
12.1.                                             жение вообще невозможно… если можно было
                                                  привести здесь другие, более серьезные задачи,
                                                  этот метод мог бы принести еще большую пользу
                                                  и им не следовало бы пренебрегать».
                                                        Обоснование вышеприведенного правила
                                                  можно найти в письме Л. Эйлера к своему другу
                                                  Элеру. Математик писал, что переход возможен,
                                                  если на участке разветвления реки имеется не бо-
12.2.                                             лее двух областей, в которые ведет нечетное число
                                                  мостов. Для того, чтобы проще представить себе
                                                  это, будем стирать на рисунке уже пройденные
                                                  мосты. Легко проверить, что если мы начнем дви-
                                                  гаться в соответствии с правилами Эйлера, пересе-
                                                  чем один мост и сотрем его, то на рисунке будет
                                                  изображен участок, где опять имеется не более
                                                  двух областей, в которые ведет нечетное число

                         170                                                7