Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
2 beğenilme 0 beğenilmeme
163 kez görüntülendi
$n$ elemanlı $X$ kümesi için bütün topolojileri üreten bir algoritma yazınız.
Veri Bilimi kategorisinde (1.1k puan) tarafından  | 163 kez görüntülendi

2 Cevaplar

0 beğenilme 0 beğenilmeme

Soyle nacizhane bir denemem oldu. Pek verimli degil ama calisiyor gibi durmakta.

from itertools import chain, combinations

def kuvvet_kumesi(kume):
    "kuvvet_kumesi([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(kume)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def kesisimler_ve_birlesimler_topolojidemi(topoloji):
    for x in topoloji:
        for y in topoloji:
            kesisim_topolojide =( x.intersection(y) in topoloji )
            birlesim_topolojide=( x.union(y) in topoloji ) 
            ikiside_topolojide = kesisim_topolojide and birlesim_topolojide
            if not(ikiside_topolojide):
                
                return False
    return True


def topolojimi(kume,topoloji):
    ret = True
    ret = ret and (frozenset() in topoloji)
    ret = ret and (kume in topoloji)
    ret = ret and kesisimler_ve_birlesimler_topolojidemi(topoloji)
    return ret

def topolojileri_bul(kume):
    topolojiler = set();
    alt_kumeler = set(map(lambda x: frozenset(x) ,kuvvet_kumesi(kume))) 
    for x in kuvvet_kumesi(alt_kumeler):
        if topolojimi(kume,x):
            topolojiler.add(x)

    return topolojiler
    
    
x = {1,2}
topolojiler = topolojileri_bul(x)

print("iki elemanli topolojiler")
for i in topolojiler:
    print(i)

#    iki elemanli topolojiler
#((1,), (1, 2), ())
#((1, 2), (), (2,))
#((1, 2), ())
#((1,), (1, 2), (), (2,))


x = {1,2,3}
topolojiler = topolojileri_bul(x)

print("uc elemanli topolojiler")
for i in topolojiler:
    print(i)

#uc elemanli topolojiler
#((1, 2), (2,), (1, 2, 3), (2, 3), ())
#((1, 2), (2,), (1, 2, 3), ())
#((1, 3), (1, 2), (2,), (1, 2, 3), (1,), ())
#((1, 3), (1, 2, 3), (1,), (), (3,))
#((1, 3), (1, 2, 3), (2, 3), (), (3,))
#((1, 2, 3), (2, 3), (), (3,))
#((1, 2), (1, 2, 3), (), (3,))
#((1, 3), (1, 2, 3), ())
#((1, 3), (2,), (1, 2, 3), ())
#((1, 3), (1, 2), (2,), (1, 2, 3), (2, 3), (1,), (), (3,))
#((1, 3), (1, 2, 3), (), (3,))
#((1, 3), (1, 2), (1, 2, 3), (1,), (), (3,))
#((1, 2, 3), (2, 3), (1,), ())
#((1, 2, 3), ())
#((1, 2), (2,), (1, 2, 3), (2, 3), (), (3,))
#((1, 2), (1, 2, 3), (1,), ())
#((2,), (1, 2, 3), (2, 3), (), (3,))
#((2,), (1, 2, 3), ())
#((1, 2, 3), (), (3,))
#((1, 3), (1, 2, 3), (1,), ())
#((1, 2), (2,), (1, 2, 3), (2, 3), (1,), ())
#((1, 2), (1, 2, 3), ())
#((1, 3), (1, 2), (1, 2, 3), (1,), ())
#((1, 2, 3), (1,), ())
#((2,), (1, 2, 3), (2, 3), ())
#((1, 2), (2,), (1, 2, 3), (1,), ())
#((1, 2, 3), (2, 3), ())
#((1, 3), (2,), (1, 2, 3), (2, 3), (), (3,))
#((1, 3), (1, 2, 3), (2, 3), (1,), (), (3,))

 

(1.1k puan) tarafından 
tarafından düzenlendi
Sonlu bir topolojik uzayda bir kümenin içini ve kapanışını bulan bir algoritma nasıl yazılır?
burada sanirim onsiralama kullanilarak daha verimli bir algoritma yazilabilir ama matematigim yetmedi
0 beğenilme 0 beğenilmeme
Sonlu kumeler uzerindeki her onsiralama (preorder?) bir topolojiye denk duser.
Bir iliski onsiralamadir ancak ve ancak gecisken (transitive?) ve refleksif ise.

$n$ elemanli bir kume uzerindeki $A$ iliskisini $n\times n$ lik bir matriks olarak ifade edebiliriz.
$A$ refleksifdir eger $A_{ii} = 1$  ise.

$A$ transitiftir eger $A^2_{ij} \neq  0 \implies A_{ij} = 1$.

Eger $A$ transitif ise, $A^T$ de transiftir.

 

Sanirim bu ozellikleri kullanarak $O(2^{n*(n-1)}/2)$ islemde butun topolojileri bulabiliriz.

Asagida verdigim algortirmadan biraz daha hizli calismali.
(1.1k puan) tarafından 
tarafından düzenlendi
Sonlu kümeler üzerinde her önsıralama bir topolojiye denktir, her topoloji ise bir önsıralamaya denktir.
Iliskinin matriks gosteriminden gecisken oldugunu nasil anlarim?
Bir ikili ilişki geçişken ise tersi de geçişkendir.
19,209 soru
21,078 cevap
70,171 yorum
23,759 kullanıcı