For citation:
Mirzayanov M. R. On Minimal Strongly Connected Congruences of a Directed Path. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2006, vol. 6, iss. 1, pp. 91-95. DOI: 10.18500/1816-9791-2006-6-1-2-91-95, EDN: VCZWIL
This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online:
18.10.2006
Full text:
(downloads: 284)
Language:
Russian
Heading:
UDC:
512.5
EDN:
VCZWIL
On Minimal Strongly Connected Congruences of a Directed Path
Autors:
Mirzayanov Mikhail Rasihovich, Saratov State University
Abstract:
Let G = (V, α) be a directed graph. An equivalence relation θ ⊆ V × V is called a strongly connected congruence of G if the quotient graph G/θ is strongly connected. Minimal (under inclusion) strongly connected congruences of a directed path are described and the total amount of them is found.
Key words:
References:
- Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М., 1997
- Богомолов А.М., Салий В.Н. Несколько задач из алгебры дискретных систем // Методы и системы технической диагностики: Материалы X Междунар. конф. по проблемам теоретич. кибернетики. Саратов, 1993. Вып. 18. С. 32–34
- Киреева А.В. О конгруэнциях корневых деревьев // XI Всесоюз. конф. по проблемам теоретической кибернетики: Тез. докл. Волгоград, 1990. Ч. 1. С. 23
- Киреева А.В. Решетка конгруэнций турнира // Студенты – ускорению научного прогресса. Саратов, 1991. Вып. 3. С. 3–7
- Кабанов М.А. Функциональные конгруэнции ориентированных графов // Упорядоч. множества и решетки. Саратов, 1995. Вып. 11. С. 15–23
- Мирзаянов М.Р. Построение минимальной сильно связной конгруэнции ориентированного графа // Алгебра и теория чисел: современные проблемы и приложения. Тез. докл. VI Междунар. конф. Саратов, 2004. C. 80
Received:
17.04.2006
Accepted:
12.09.2006
Published:
18.10.2006
- 1314 reads