ISSN: 1984 – 8625 – n´mero 6 – IFSP - Sert˜ozinho u a EITHER DIGRAPHS OR PRE-TOPOLOGICAL SPACES?
J. CARLOS S. KIIHL1 , IRWEN VALLE GUADALUPE2
RESUMO: Neste artigo mostramos que os digrafos podem ser identiﬁcados, de um modo natural, com espa¸os pre-topol´gicos ﬁnitos. Mostramos c o tamb´m que com esta identiﬁca¸˜o a Teoria de Homotopia Regular ´ a mais e ca e apropriada a ser usada quando setrabalha com digrafos. Em particular obtemos caracteriza¸˜es gr´ﬁcas e estruturais para algumas classes de torneios, co a mostrando a importˆncia desta nova abordagem. a Palavras-chave: Digrafos, Espa¸os Pr´-topol´gicos, Homotopia Regular c e o para Digrafos, Torneios. ABSTRACT: In this paper we show that digraphs can be identiﬁed, in a natural way, to ﬁnite pre-topological spaces. We also showthat with this identiﬁcation the Regular Homotopy Theory is the most appropriate one to be used when dealing with digraphs. We give some combinatorial applications of the homotopy theory of pre-topological spaces to digraphs. In particular we get structural and graphical characterizations for some classes of tournaments, showing the importance of this new approach. Keywords: Digraphs,Pre-topological spaces, Regular Homotopy for Digraphs, Tournaments.
´ JOSE CARLOS S. KIIHL ´ Doutor em Matem´tica pela Universidade de e a Chicago, EUA. Atualmente ´ docente no IFSP, no Campus de Sert˜ozinho. Ene a dere¸o eletrˆnico: firstname.lastname@example.org. c o 2 IRWEN VALLE GUADALUPE ´ Doutor em Matem´tica pela UNICAMP. Ate a ualmente est´ como docente aposentado da UNICAMP. a
ISSN: 1984 –8625 – n´mero 6 – IFSP - Sert˜ozinho u a 1. Introduction In Graph Theory sometimes one has to introduce certain structures in order to study or to obtain successful applications. In , for instance, tournaments are studied using an algebraic approach so that they are considered as algebras of a special kind. Sometimes a topological approach is used. Since graphs can always be realized in theeuclidean space, if one is interested in studying them from a homotopical viewpoint, the usual procedure is to consider them just as 1-complexes. Demaria and his collaborators used a diﬀerent approach, taking in account just the combinatorial data furnished by the graphs, obtaining what they have called the Regular Homotopy Theory for Digraphs. It is known that one can introduce structures in a setwhich are weaker than a topology. For example, we can consider certain sets as pre-topological spaces. Considering the pre-continuous maps we can construct the corresponding homotopy theory. In this paper we show that, in a natural way, to any digraph (directed graph) D we can associate two pre-topological spaces P (D) and P ∗ (D). In fact we will show that the class of the digraphs can actually beidentiﬁed with the class of the ﬁnite pre-topological spaces. As a matter of fact, the main purpose of this paper is to stablish the point that a ﬁnite pre-topological space is just a digraph, and vice versa. Since we have this identiﬁcation, it seems proper to use the corresponding homotopy theory when a digraph is considered as a pretopological space in order to study them from a homotopicalpoint of view. In this paper we will show that this homotopy theory is exactly that introduced by Demaria. Moreover we shall present several applications, showing this new approach is relevant and eﬀective leading to some important new results. In section 2, we give the basic deﬁnitions, the notation and we prove the equivalence between the class of the digraphs and the class of the ﬁnitepre-topological spaces. In section 3, we present a summary of the Regular Homotopy for Digraphs, which was introduced by D. C. Demaria and his collaborators, showing that it coincides with the homotopy theory for pre-topological spaces, since the o-regular maps are just the pre-continuous maps. In the last four sections we present several recent results, showing how this identiﬁcation of digraphs with...
Ler documento completo
Por favor, assinar para o acesso.