Том 1, номер 3, 1994 г., Стр. 3-19

УДК 519.17
А. В. Косточка
Одно уточнение теоремы Франка–Шебо–Тардаш и его применения

Аннотация:
Для четного подмножества $T$ множества вершин $V$ в связном графе $G=(V,E)$ $T$-джойном называется любое множество $F\subseteq E$ такое, что вершине $\upsilon\in V$ инцидентно нечетное число ребер из $F$ если и только если $\upsilon\in T$. Задача нахождения $T$-джойнов минимальной мощности включает в себя задачу китайского почтальона, задачу о кратчайшем пути, задачу о наибольшем паросочетании. При всей общности постановки эта задача полиномиально разрешима. Разрез $D$ (понимаемый как множество ребер) называется $T$-разрезом, если каждая из двух компонент графа $G\setminus D$ содержит нечетное число вершин из $T$. Каждый $T$-разрез имеет непустое пересечение с каждым $T$-джойном. Следовательно, для любой пары $(G,T)$ величина $\tau(G,T)$ – минимально возможная мощность $T$-джойнов в графе $G$ – не меньше максимального числа попарно непересекающихся $T$-разрезов в графе $G$. Теорема Франка–Шебо–Тардош утверждает, что можно выбрать $\tau(G,T)$ попарно непересекающихся $T$-разрезов и при этом выбранный набор будет обладать некоторыми дополнительными свойствами.
В статье показано, что при выборе непересекающихся $T$-разрезов можно требовать выполнения еще ряда свойств. Этот факт используется для нахождения верхних оценок $\tau(G,T)$.
Библиогр. 17.

Косточка А. В. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 12 мая 1994 г.