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

11.7. эйлеровы и гамильтоновы графы: Справочник по математике для экономистов, В.И. Ермаков, 2007 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Предназначен для студентов экономических вузов. Может быть использован аспирантами и преподавателями вузов и колледжей, а также экономистами различных специальностей в практической работе.

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).

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

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

Обсуждение Справочник по математике для экономистов

Комментарии, рецензии и отзывы

11.7. эйлеровы и гамильтоновы графы: Справочник по математике для экономистов, В.И. Ермаков, 2007 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Предназначен для студентов экономических вузов. Может быть использован аспирантами и преподавателями вузов и колледжей, а также экономистами различных специальностей в практической работе.