Geodesic
On minimal strongly connected congruences of a directed path
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 6 (2006) no. 1-2, pp. 91-95 
M. R. Mirzayanov. On minimal strongly connected congruences of a directed path. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 6 (2006) no. 1-2, pp. 91-95. http://geodesic.mathdoc.fr/item/ISU_2006_6_1-2_a10/
@article{ISU_2006_6_1-2_a10,
     author = {M. R. Mirzayanov},
     title = {On minimal strongly connected congruences of a directed path},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {91--95},
     year = {2006},
     volume = {6},
     number = {1-2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2006_6_1-2_a10/}
}
TY  - JOUR
AU  - M. R. Mirzayanov
TI  - On minimal strongly connected congruences of a directed path
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2006
SP  - 91
EP  - 95
VL  - 6
IS  - 1-2
UR  - http://geodesic.mathdoc.fr/item/ISU_2006_6_1-2_a10/
LA  - ru
ID  - ISU_2006_6_1-2_a10
ER  - 
%0 Journal Article
%A M. R. Mirzayanov
%T On minimal strongly connected congruences of a directed path
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2006
%P 91-95
%V 6
%N 1-2
%U http://geodesic.mathdoc.fr/item/ISU_2006_6_1-2_a10/
%G ru
%F ISU_2006_6_1-2_a10

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $G = (V, \alpha)$ be a directed graph. An equivalence relation $\theta\subseteq V\times V$ is called a strongly connected congruence of $G$ if the quotient graph $G/\theta$ is strongly connected. Minimal (under inclusion) strongly connected congruences of a directed path are described and the total amount of them is found ($2^{n-3}$ if the path has $n$ vertices).

[1] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, M., 1997

[2] Bogomolov A. M., Salii V. N., “Neskolko zadach iz algebry diskretnykh sistem”, Materialy X Mezhdunar. konf. po problemam teoretich. kibernetiki, Metody i sistemy tekhnicheskoi diagnostiki, 18, Saratov, 1993, 32–34

[3] Kireeva A. V., “O kongruentsiyakh kornevykh derevev”, XI Vsesoyuz. konf. po problemam teoreticheskoi kibernetiki, Tez. dokl. (Volgograd, 1990), v. 1, 23

[4] Kireeva A. V., “Reshetka kongruentsii turnira”, Studenty — uskoreniyu nauchnogo progressa, 3, Saratov, 1991, 3–7 | MR

[5] Kabanov M. A., “Funktsionalnye kongruentsii orientirovannykh grafov”, Uporyadoch. mnozhestva i reshetki, 11, Saratov, 1995, 15–23

[6] Mirzayanov M. R., “Postroenie minimalnoi silno svyaznoi kongruentsii orientirovannogo grafa”, Algebra i teoriya chisel: sovremennye problemy i prilozheniya, Tez. dokl. VI Mezhdunar. konf. (Saratov, 2004), 80