Локальные свойства ориентированных графов

Abstract

Целью настоящей работы является дальнейшее развитие методов исследования зависимости между локальными и глобальными свойствами ориентированных графов, начатого в [2, 3]. В работе рассмотрены два обобщения понятия локально связного графа на случай ориентированных графов: локально сильные орграфы и (L, R)-сильные орграфы. Установлены достаточные условия того, чтобы орграф был локально сильным или (L, R)-сильным. Исследовано влияние локальной структуры орграфа на такую его глобальную характеристику, как связность. Показано, что множество сильных локально сильных асимметрических орграфов, максимальная степень вершин которых не превосходит 4, конечно, и все такие орграфы содержат гамильтонов контур. Следует отметить, что в общем случае задача о гамильтоновом контуре в сильном орграфе, степени вершин которого не превышают 4, является NP-полной [5].