La demi-isomorphie et les tournois fortement connexes finis

Moncef Bouaziz; Youssef Boudabbous

doi:10.1016/S1631-073X(02)02439-1

La demi-isomorphie et les tournois fortement connexes finis

Moncef Bouaziz ¹ ; Youssef Boudabbous ²

¹ Faculté des sciences de Tunis, Département de mathématiques, Elmanar II 2092, Tunisie
² Al-Jouf Technical College, Department of General Studies, PO Box 1642, Sakaka, Al-Jouf, Saudi Arabia

Comptes Rendus. Mathématique, Volume 335 (2002) no. 2, pp. 105-110.

Résumé
Abstract

Soient T=(S,A) un tournoi fini à n sommets et F un ensemble d'entiers positifs ⩽n. Le dual de T est le tournoi $T^{*} = (S, A^{*})$ défini par : pour tous x,y∈S, $(y, x) \in A^{*}$ si et seulement si (x,y)∈A. A chaque partie X de S est associé le sous-tournoi T(X)=(X,A∩(X×X)) de T induit par X. Le tournoi T est fortement connexe si pour tous x,y∈S, avec x≠y, il existe une suite x₀=x,…,x_p=y telle que pour tout i∈{0,…,p−1}, (x_i,x_i+1)∈A. Un demi-isomorphisme de T sur un tournoi T′ est soit un isomorphisme de T sur T′ soit un isomorphisme de $T^{*}$ sur T′. Un tournoi T′, ayant le même ensemble de sommets S que T, est F-demi-isomorphe à T lorsque pour toute partie X de S telle que |X|∈F, les sous-tournois T(X) et T′(X) sont demi-isomorphes. Nous étudions la {3,n−2}-demi-isomorphie et la {n−3}-demi-isomorphie entre deux tournois à n sommets dont l'un est fortement connexe.

Let T=(V,A) be a finite tournament with n vertices and let F be a set of non-negative integers ⩽n. The dual of T is the tournament $T^{*} = (V, A^{*})$ defined by: for all x,y∈V, $(y, x) \in A^{*}$ if and only if (x,y)∈A. With every subset X of V is associated the subtournament T(X)=(X,A∩(X×X)) of T induced by X. The tournament T is strongly connected if for all x,y∈V, with x≠y, there is a sequence x₀=x,…,x_p=y such that for all i∈{0,…,p−1}, (x_i,x_i+1)∈A. An half-isomorphism from T onto a tournament T′ is either an isomorphism from T onto T′ or an isomorphism from $T^{*}$ onto T′. A tournament T′, with the same set of vertices V than T, is F-half-isomorphic to T if for every subset X of V such that |X|∈F, the subtournaments T(X) and T′(X) are half-isomorphic. We study the {3,n−2}-half-isomorphy and the ${n - 3}$ -half-isomorphy between two tournaments with n vertices, one of them is strongly connected.

Reçu le : 2002-05-02
Accepté le : 2002-05-03
Publié le : 2002-01-01

DOI : 10.1016/S1631-073X(02)02439-1

Affiliations des auteurs :

Moncef Bouaziz ¹ ; Youssef Boudabbous ²

¹ Faculté des sciences de Tunis, Département de mathématiques, Elmanar II 2092, Tunisie
² Al-Jouf Technical College, Department of General Studies, PO Box 1642, Sakaka, Al-Jouf, Saudi Arabia

@article{CRMATH_2002__335_2_105_0,
     author = {Moncef Bouaziz and Youssef Boudabbous},
     title = {La demi-isomorphie et les tournois fortement connexes finis},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {105--110},
     publisher = {Elsevier},
     volume = {335},
     number = {2},
     year = {2002},
     doi = {10.1016/S1631-073X(02)02439-1},
     language = {fr},
}

TY  - JOUR
AU  - Moncef Bouaziz
AU  - Youssef Boudabbous
TI  - La demi-isomorphie et les tournois fortement connexes finis
JO  - Comptes Rendus. Mathématique
PY  - 2002
SP  - 105
EP  - 110
VL  - 335
IS  - 2
PB  - Elsevier
DO  - 10.1016/S1631-073X(02)02439-1
LA  - fr
ID  - CRMATH_2002__335_2_105_0
ER  -

%0 Journal Article
%A Moncef Bouaziz
%A Youssef Boudabbous
%T La demi-isomorphie et les tournois fortement connexes finis
%J Comptes Rendus. Mathématique
%D 2002
%P 105-110
%V 335
%N 2
%I Elsevier
%R 10.1016/S1631-073X(02)02439-1
%G fr
%F CRMATH_2002__335_2_105_0

Moncef Bouaziz; Youssef Boudabbous. La demi-isomorphie et les tournois fortement connexes finis. Comptes Rendus. Mathématique, Volume 335 (2002) no. 2, pp. 105-110. doi : 10.1016/S1631-073X(02)02439-1. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(02)02439-1/

Bibliographie
Cité par

[1] Y. Boudabbous; J. Dammak Sur la (-k)-demi-reconstructibilité des tournois finis, C. R. Acad. Sci. Paris, Série I, Volume 326 (1998), pp. 1037-1040

[2] Y. Boudabbous; G. Lopez La relation différence et l'anti-isomorphie, Math. Log. Quart., Volume 41 (1995), pp. 268-280

[3] A. Boussairi; P. Ille; G. Lopez; S. Thomassé Hypomorphie et inversion locale entre graphes, C. R. Acad. Sci. Paris, Série I, Volume 317 (1993), pp. 125-128

[4] A. Ehrenfeucht; G. Rozenberg Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., Volume 3 (1990) no. 70, pp. 343-358

[5] R. Fraïssé Abritement entre relations et spécialement entre chaînes, Sympos. Math., Volume 5 (1970), pp. 203-251

[6] T. Gallai Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., Volume 18 (1967), pp. 25-66

[7] J.G. Hagendorf; G. Lopez La demi-reconstructibilité des relations binaires d'au moins 13 éléments, C. R. Acad. Sci. Paris, Série I, Volume 317 (1993), pp. 7-12

[8] F. Harary; E. Palmer On the problem of reconstructing a tournament from subtournaments, Monatsch. Math., Volume 71 (1967), pp. 14-23

[9] M. Pouzet Application d'une propriété combinatoire des parties d'un ensemble aux groupes et aux relations, Math. Z., Volume 150 (1976), pp. 117-134

[10] J.H. Schmerl; W.T. Trotter Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., Volume 113 (1994), pp. 191-205

[11] S.M. Ulam A Collection of Mathematical Problems, Interscience, New York, 1960

Cité par Sources :

Commentaires - Politique