Математическое моделирование на графах. Часть 1. Берцун В.Н. - 56 стр.

UptoLike

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

Рубрика:

56 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

вым, если в нем есть контур, проходящий по каждой дуге этого гра-

фа в точности один раз. Известно [1 – 3], что:

1) связный орграф – эйлеров, если в каждой его вершине полу-

степень захода равна полустепени исхода;

2) если граф G – связный, то можно построить цикличный мар-

шрут, содержащий все его ребра в точности два раза, по одному разу

в каждом из двух направлений.

Рассмотрим граф на рис. 2.12, a, в котором требуется найти замк-

нутый путь из вершины А, содержащий все ребра графа G, дважды

по одному разу в каждом направлении.

аб

Рис. 2.12

Для этой цели используем правило Тарри для связного графа [1].

Из произвольной вершины А начинаем движение вдоль любого реб-

ра. Ребро, по которому впервые приходим в вершину, отмечаем, на-

пример, стрелкой с точкой. Ребро, по которому впервые попали в

вершину, используем для выхода, если нет других возможностей.

Один из вариантов пути в этом случае представлен на рис. 2.12, б.

Утверждение 2.7. Почти нет эйлеровых графов [11].

Доказательство. Пусть G(n) – множество графов с n вершинами,

Э(n) множество эйлеровых графов с n вершинами и мощностью

│Э(n)│. Если Э′(n) – множество графов с n вершинами и четными

степенями, тогда

Э′(n) ⊃ Э (n) и | Э′(n)| ≥ |Э(n)| .

В любом графе число вершин нечетной степени четно. Тогда лю-

бой граф из множества Э′(n) можно получить из некоторого графа