On congruences of paths.pdf Под ориентированным графом (далее орграфом) понимается пара G = (V, а), гдеV - конечное непустое множество вершин; а - отношение на V, задающее множестводуг. Основные понятия приводятся в соответствии с [1].Существуют различные методы преобразования графовых систем для приложе-ний к проблемам оптимизации в различных ситуациях. В качестве допустимых рекон-струкций данного графа обычно рассматриваются следующие [2]:1) отождествление некоторых вершин графа;2) ориентация ребер данного неориентированного графа;3) переориентация некоторых дуг;4) добавление новых дуг (ребер);5) удаление некоторых дуг (ребер).Будем рассматривать реконструкцию типа 1.Пусть е - некоторое отношение эквивалентности на множестве вершин V оргра-фа G. Фактор-графом орграфа G по эквивалентности е называется орграф G/е == (V/e,a.), где V/е - множество классов эквивалентности е; ae = {(e(vc),e(v2)) :3uc Е e(vc),u2 Е e(v2) ((uc,u2) E а)}. Пусть K - некоторый класс орграфов. Конгру-энцией K-графа G называется такое отношение эквивалентности 0 на V, что фактор-граф G/0 является K-графом. Возьмём в качестве класса K класс неориентированныхграфов.Множество вершин называется независимым, если любые две вершины из этогомножества несмежны. Очевидно, что отношение эквивалентности 0 на множестве вер-шин графа G тогда и только тогда будет конгруэнцией этого графа, когда каждый0-класс образует в G независимое подмножество.Цепь (простой путь, не являющийся циклом) с m ребрами будем обозначать Pm,звезду с m ребрами - Sm. В [3] представлена программа, генерирующая все конгруэн-ции заданной цепи и выделяющая среди них цепные конгруэнции, т. е. такие, фактор-графы по которым являются цепями. При этом выдается общее число конгруэнцийданной цепи и количество её цепных конгруэнций. Например, у трехреберной цепи P3имеются четыре различных конгруэнции, которые дают три неизоморфных фактор-графа. У четырехреберной цепи P4 всего имеется 14 фактор-графов, из них 7 попарнонеизоморфных.Известна следующая задача о факторизации: можно ли для заданного графа ска-зать, является ли он фактор-графом другого заданного графа? Эта задача являетсяNP-полной. Например, возьмем пятиреберную цепь P5. Пятивершинный цикл C5 будетеё фактор-графом, а четырехреберная звезда S4 - нет.Маршрут в связном графе называется обходом, если он содержит все ребра графа.Теорема 1. Связный граф G тогда и только тогда является фактор-графомm-реберной цепи, когда в нем есть обход длины m.Следствие 1. Любой связный граф с m ребрами является фактор-графом це-п и P 2 m - c.Одной из открытых проблем является следующая: для данного связного графа Gнайти цепь с минимальным возможным числом ребер p(G), фактор-графом которойявляется данный граф.Теорема 2. Если T - дерево с m ребрами, имеющее диаметр d, то p(T) = 2m - d.Следствие 2. Для звезды Sm имеем p(Sm) = 2m - 2.Теорема 3. Для связного графа G с m ребрами m ^ p(G) ^ 2m - 2.Подробное изложение представленных результатов можно найти в [4].

Скачать электронную версию публикации