Имя материала: Справочник по математике для экономистов

Автор: В.И. Ермаков

11.7. эйлеровы и гамильтоновы графы

Эйлеровым путем (циклом) графа называется путь (цикл), содержащий все ребра графа ровно один раз.

10-421

289

 

Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

На рис. 11.9 граф G не является эйлеровым, так как вершина ръ инцидентна только одному ребру. Если путь приведет в вершину ръ, то не будет ребра, по которому можно было бы выйти изр,.

Теорема 11.8. Граф G является эйлеровым тогда и только тогда, когда G-связный и все его вершины имеют четную степень.

Граф G, изображенный на рис. 11.10, является эйлеровым. Последовательность ребер (alt аг, а3, а4, as, а6, а7, а8, а9, а10) образует эйлеров цикл.

Теорема 11.9. Граф G обладает эйлеровым путем с концами pit рг тогда и только тогда, когда G-связный и pL, рг — единственные его вершины нечетной степени.

На рис. 11.9 изображен граф G, обладающий эйлеровым путем (<*!, а2, а3, <х4, а5, а6) с концевыми вершинами ръ и ръ.

Гамильтоновым путем (циклом) графа С? называется путь (цикл), проходящий через каждую вершину G в точности по одному разу.

Граф, обладающий гамильтоновым циклом, наазывается гамильтоновым.

Критерий существования гамильтонова цикла в произвольном графе G еще не найден. Достаточным условием существования гамильтонова цикла является полнота графа G.

Граф, изображенный на рис. 11.9, не является гамильтоновым, а граф, представленный на рис. 11.11, содержит гамиль-тонов цикл (at, a2, a4, as, a6).

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 |