Graph congruences: some combinatorial properties.pdf Под ориентированным графом (далее орграфом) понимается пара G = (V, а), гдеV - конечное непустое множество вершин, а а - отношение смежности на V.Пусть е - некоторое отношение эквивалентности на множестве вершин V ор-графа G. Фактор-графом орграфа G по эквивалентности е называется орграфG/е = (V/е, а.), где V/е - множество классов эквивалентности е, а а. = {(e(v1), e(v2)) :(3ui Е e ( v i ) 3 « 2 Е e(v2) ( ( u i , ^ ) Е а ) } .Пусть K - некоторый класс орграфов. Конгруэнцией K-графа G называется такоеотношение эквивалентности в на V, что фактор-граф G/0 является K-графом.Возьмём в качестве класса K класс неориентированных графов. Неориентирован-ным графом (или, для краткости, графом) называется пара G = (V, а), где а - симмет-ричное и антирефлексивное отношение на множестве вершин V. Множество вершинназывается независимым, если любые две вершины из этого множества несмежны.Очевидно, что отношение эквивалентности в на множестве вершин графа G тогдаи только тогда будет конгруэнцией этого графа, когда каждый в-класс образует в Gнезависимое подмножество.Теорема 1. Количество конгруэнций m-реберной цепи равно количеству эквива-лентностей на m-элементном множестве.В [1] обсуждалась следующая задача: для данного связного графа G найти цепьс минимальным возможным числом ребер p(G), фактор-графом которой являетсяграф G.Теорема 2. Пусть G - связный граф. Тогда p(G) = m + l - к, где m - количе-ство ребер графа G; l - количество ребер в минимальном цепном паросочетании намножестве нечётных вершин графа G; к - максимальная из длин цепей в таких паро-сочетаниях.Подробное изложение представленных результатов можно найти в [2].

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