Дискретная математика

155 Теперь попытаемся определить для произвольного графа наименьшее число цепей, таких, что никакие две из них не имеют общих ребер, а все они вместе покрывают весь граф. Ясно, что если в графе имеется такое семейство цепей, то каждая нечетная вершина должна быть либо начальной, либо конечной точкой, по крайней мере, одной из них, иначе вершина была бы четной. Как известно, число нечетных вершин графа четно, скажем равно 2к. Значит, каждое семейство цепей, покрываюш,их граф, должно состоять, по крайней мере, из к цепей. Покажем теперь, что существование 2к нечетных вершин является и достаточным условием существования к таких цепей. Теорема 5.19. На любом связном графе с 2к нечетными вершинами имеется семейство из к цепей, которые в совокупности содержат все ребра графа в точности по одному разу. Доказательство. Обозначим нечетные вершины графа, взятые в некотором порядке, через Если добавим к нашему графу к ребер (A,,B,),(A2,B^,...,(AhBiJ, то все вершины станут четными и на нем существует эйлеровый цикл С. При удалении добавленных ребер цикл С распадется на к отдельных цепей, содержащих все ребра графа. Буме своем я создач мир иной И образов гшых сугцесгпвованье; Я цепью их связш между собой, ... М. JTep.voHmoe § 15. Гамильтоновы графы Эйлеровы графы характеризуются тем свойством, что существуют UHiuibi, содержащие каждое ребро один раз. Гамильтоновы циклы определяются для связных графов аналогичным образом, но только по отношению к вершинам; цикл называется гамтътоновъш, если он проходит через каждую вершину графа один и только один раз. Гамшътоновым графом называется граф, содержащий гамильтонов цикл. На рис. 5.27 приведен граф, вершинами которого являются вершины параллелепипеда, а ребрами - все рёбра этого параллелепипеда, Этот граф является гамильтоновым графом; ребра, порождающие гамильтонов цикл, на этом рисунке изображены сплошной линией. Гамшьтоновой цепью в графе называется простая цепь, проходящая через каждую вершину графа один и только один раз. Несмотря на сходство в определениях для эйлеровых и гамильтоновь! циклов (графов), соответствуюшде теории для этих понятий имеют ма общего. Критерий существования эйлеровых циклов был установлен прос Для гамильтоновых циклов не получены необходимые и достаточн