0 KB290 KB34 KB200820252013Policriti, AlbertoTomescu, Alexandru I.številka:1letnik:6str. 57-68COBISSID:16468569ISSN:1855-3966URN:URN:NBN:SI:doc-639WUEPZenDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneaextensional digraphMarkov chainrandom generationset theorytransitive setMarkov chain algorithms for generating sets uniformly at random|In this paper we tackle the problem of generating uniformly at random two representative types of sets with n elements: transitive sets and weakly transitive sets, that is, transitive sets with atoms. A set is said to be transitive if any of its elements is also a subset of it; a set is weakly transitive if any of its elements, unless disjoint from it, is also a subset of it. We interpret such sets as (weakly) extensional acyclic digraphs - that is, acyclic digraphs whose (non-sink) vertices have pairwise different out-neighborhoods - and employ a Markov chain technique already given for acyclic digraphs. We thus propose Markov chain-based algorithms for generating uniformly at random (weakly) extensional acyclic digraphs with a given number of vertices. The Markov chain is then refined to generate such digraphs which are also simply connected, and digraphs in which the number of arcs is fixedTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije