Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu

$n$ elemanlı $X$ kümesi için bütün topolojileri üreten bir algoritma yazınız.

2 beğenilme 0 beğenilmeme
946 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.6k puan) tarafından  | 946 kez görüntülendi

3 Cevaplar

0 beğenilme 0 beğenilmeme
En İyi Cevap
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.6k puan) tarafından 
tarafından seçilmiş
Sonlu kümeler üzerinde her önsıralama bir topolojiye denktir, her topoloji ise bir önsıralamaya denktir.
31 Ekim 2020 Lisans Matematik kategorisinde (1.6k puan) tarafından  soruldu | 540 kez görüntülendi
Bir ikili ilişki geçişken ise tersi de geçişkendir.
31 Ekim 2020 Lisans Matematik kategorisinde (1.6k puan) tarafından  soruldu
1 Kasım 2020 tarafından düzenlendi | 604 kez görüntülendi
1 beğenilme 0 beğenilmeme

Bu program tüm topolojileri listeleyecek. 

$n\in \{1,2,3,4\}$ için maksimum 1 saniye içinde tüm topolojileri verir.

$n =5$ hepsini yazmasını $1$ saatten fazla sürer fakat çok normal. Çünkü çok hesap var.

Hızlandıramaya çalışıyorum.

import itertools as it

def isTopology(t,E):
    '''Retourne True eğer t, E üzerine bir topoloji ise aksı halde False '''
    t_inter,t_union=[set()]+t,t+[E]
    for e1,e2 in it.combinations(t,2):
        if e1.intersection(e2) not in t_inter: return False 
        if e1.union(e2) not in t_union: return False 
    return True

def topologies(n):
    ''' boş ve X olmayan tüm X in altkumelerin kümesi '''
    E=set(range(1,n+1)) # n elemanli bir küme oluşturma
    pE=[] 
    for i in range(1,len(E)):
        pE+=[set(c) for c in it.combinations(E,i)]
   

    T=[] # Topolojilerın listesi
    for i in range(len(pE)+1):
        for c in it.combinations(pE,i):
            if isTopology(list(c),E):
                c1=[set()]+list(c)+[E]
                T.append(c1)
                print(len(T),' : ',c1)
    return T
    
# n elemanlı kümesi E=[1,n]
n=input("kumenin elemani sayısı : ")
try:# Hattaları!
    n=int(n)
    print("|n|={}".format(n))
except:
    print("lütfen bir rakam gırın !")
# n elemanlı küme üzerınde topolojileri bul.
T=topologies(n)
print("\n %d elemanli küme topoloji sayisi = %d "%(n,len(T)))

#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
"""
n= 2 için ;
Out :
kumenin elemani sayısı : 2
|n|=2
1  :  [set(), {1, 2}]
2  :  [set(), {1}, {1, 2}]
3  :  [set(), {2}, {1, 2}]
4  :  [set(), {1}, {2}, {1, 2}]

 2 elemanli küme topoloji sayisi = 4 

///////////////////////////////////////////////////////////////////
n = 3 için
Out :
kumenin elemani sayısı : 3
|n|=3
1  :  [set(), {1, 2, 3}]
2  :  [set(), {1}, {1, 2, 3}]
3  :  [set(), {2}, {1, 2, 3}]
4  :  [set(), {3}, {1, 2, 3}]
5  :  [set(), {1, 2}, {1, 2, 3}]
6  :  [set(), {1, 3}, {1, 2, 3}]
7  :  [set(), {2, 3}, {1, 2, 3}]
8  :  [set(), {1}, {1, 2}, {1, 2, 3}]
9  :  [set(), {1}, {1, 3}, {1, 2, 3}]
10  :  [set(), {1}, {2, 3}, {1, 2, 3}]
11  :  [set(), {2}, {1, 2}, {1, 2, 3}]
12  :  [set(), {2}, {1, 3}, {1, 2, 3}]
13  :  [set(), {2}, {2, 3}, {1, 2, 3}]
14  :  [set(), {3}, {1, 2}, {1, 2, 3}]
15  :  [set(), {3}, {1, 3}, {1, 2, 3}]
16  :  [set(), {3}, {2, 3}, {1, 2, 3}]
17  :  [set(), {1}, {2}, {1, 2}, {1, 2, 3}]
18  :  [set(), {1}, {3}, {1, 3}, {1, 2, 3}]
19  :  [set(), {1}, {1, 2}, {1, 3}, {1, 2, 3}]
20  :  [set(), {2}, {3}, {2, 3}, {1, 2, 3}]
21  :  [set(), {2}, {1, 2}, {2, 3}, {1, 2, 3}]
22  :  [set(), {3}, {1, 3}, {2, 3}, {1, 2, 3}]
23  :  [set(), {1}, {2}, {1, 2}, {1, 3}, {1, 2, 3}]
24  :  [set(), {1}, {2}, {1, 2}, {2, 3}, {1, 2, 3}]
25  :  [set(), {1}, {3}, {1, 2}, {1, 3}, {1, 2, 3}]
26  :  [set(), {1}, {3}, {1, 3}, {2, 3}, {1, 2, 3}]
27  :  [set(), {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}]
28  :  [set(), {2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}]
29  :  [set(), {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]

 3 elemanli küme topoloji sayisi = 29 

//////////////////////////////////////////////////////////////////////

n=4 için :
Out:
kumenin elemani sayısı : 4
|n|=4
1  :  [set(), {1, 2, 3, 4}]
2  :  [set(), {1}, {1, 2, 3, 4}]
3  :  [set(), {2}, {1, 2, 3, 4}]
4  :  [set(), {3}, {1, 2, 3, 4}]
5  :  [set(), {4}, {1, 2, 3, 4}]
6  :  [set(), {1, 2}, {1, 2, 3, 4}]
7  :  [set(), {1, 3}, {1, 2, 3, 4}]
8  :  [set(), {1, 4}, {1, 2, 3, 4}]
9  :  [set(), {2, 3}, {1, 2, 3, 4}]
10  :  [set(), {2, 4}, {1, 2, 3, 4}]
11  :  [set(), {3, 4}, {1, 2, 3, 4}]
12  :  [set(), {1, 2, 3}, {1, 2, 3, 4}]
13  :  [set(), {1, 2, 4}, {1, 2, 3, 4}]
14  :  [set(), {1, 3, 4}, {1, 2, 3, 4}]
15  :  [set(), {2, 3, 4}, {1, 2, 3, 4}]
16  :  [set(), {1}, {1, 2}, {1, 2, 3, 4}]
17  :  [set(), {1}, {1, 3}, {1, 2, 3, 4}]
18  :  [set(), {1}, {1, 4}, {1, 2, 3, 4}]
19  :  [set(), {1}, {1, 2, 3}, {1, 2, 3, 4}]
20  :  [set(), {1}, {1, 2, 4}, {1, 2, 3, 4}]
21  :  [set(), {1}, {1, 3, 4}, {1, 2, 3, 4}]
22  :  [set(), {1}, {2, 3, 4}, {1, 2, 3, 4}]
23  :  [set(), {2}, {1, 2}, {1, 2, 3, 4}]
24  :  [set(), {2}, {2, 3}, {1, 2, 3, 4}]
25  :  [set(), {2}, {2, 4}, {1, 2, 3, 4}]
26  :  [set(), {2}, {1, 2, 3}, {1, 2, 3, 4}]
27  :  [set(), {2}, {1, 2, 4}, {1, 2, 3, 4}]
28  :  [set(), {2}, {1, 3, 4}, {1, 2, 3, 4}]
29  :  [set(), {2}, {2, 3, 4}, {1, 2, 3, 4}]
30  :  [set(), {3}, {1, 3}, {1, 2, 3, 4}]
31  :  [set(), {3}, {2, 3}, {1, 2, 3, 4}]
32  :  [set(), {3}, {3, 4}, {1, 2, 3, 4}]
33  :  [set(), {3}, {1, 2, 3}, {1, 2, 3, 4}]
34  :  [set(), {3}, {1, 2, 4}, {1, 2, 3, 4}]
35  :  [set(), {3}, {1, 3, 4}, {1, 2, 3, 4}]
36  :  [set(), {3}, {2, 3, 4}, {1, 2, 3, 4}]
37  :  [set(), {4}, {1, 4}, {1, 2, 3, 4}]
38  :  [set(), {4}, {2, 4}, {1, 2, 3, 4}]
39  :  [set(), {4}, {3, 4}, {1, 2, 3, 4}]
40  :  [set(), {4}, {1, 2, 3}, {1, 2, 3, 4}]
41  :  [set(), {4}, {1, 2, 4}, {1, 2, 3, 4}]
42  :  [set(), {4}, {1, 3, 4}, {1, 2, 3, 4}]
43  :  [set(), {4}, {2, 3, 4}, {1, 2, 3, 4}]
44  :  [set(), {1, 2}, {3, 4}, {1, 2, 3, 4}]
45  :  [set(), {1, 2}, {1, 2, 3}, {1, 2, 3, 4}]
46  :  [set(), {1, 2}, {1, 2, 4}, {1, 2, 3, 4}]
47  :  [set(), {1, 3}, {2, 4}, {1, 2, 3, 4}]
48  :  [set(), {1, 3}, {1, 2, 3}, {1, 2, 3, 4}]
49  :  [set(), {1, 3}, {1, 3, 4}, {1, 2, 3, 4}]
50  :  [set(), {1, 4}, {2, 3}, {1, 2, 3, 4}]
51  :  [set(), {1, 4}, {1, 2, 4}, {1, 2, 3, 4}]
52  :  [set(), {1, 4}, {1, 3, 4}, {1, 2, 3, 4}]
53  :  [set(), {2, 3}, {1, 2, 3}, {1, 2, 3, 4}]
54  :  [set(), {2, 3}, {2, 3, 4}, {1, 2, 3, 4}]
55  :  [set(), {2, 4}, {1, 2, 4}, {1, 2, 3, 4}]
56  :  [set(), {2, 4}, {2, 3, 4}, {1, 2, 3, 4}]
57  :  [set(), {3, 4}, {1, 3, 4}, {1, 2, 3, 4}]
58  :  [set(), {3, 4}, {2, 3, 4}, {1, 2, 3, 4}]
59  :  [set(), {1}, {2}, {1, 2}, {1, 2, 3, 4}]
60  :  [set(), {1}, {3}, {1, 3}, {1, 2, 3, 4}]
61  :  [set(), {1}, {4}, {1, 4}, {1, 2, 3, 4}]
62  :  [set(), {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}]
63  :  [set(), {1}, {1, 2}, {1, 2, 4}, {1, 2, 3, 4}]
64  :  [set(), {1}, {1, 2}, {1, 3, 4}, {1, 2, 3, 4}]
65  :  [set(), {1}, {1, 3}, {1, 2, 3}, {1, 2, 3, 4}]
66  :  [set(), {1}, {1, 3}, {1, 2, 4}, {1, 2, 3, 4}]
67  :  [set(), {1}, {1, 3}, {1, 3, 4}, {1, 2, 3, 4}]
68  :  [set(), {1}, {1, 4}, {1, 2, 3}, {1, 2, 3, 4}]
69  :  [set(), {1}, {1, 4}, {1, 2, 4}, {1, 2, 3, 4}]
70  :  [set(), {1}, {1, 4}, {1, 3, 4}, {1, 2, 3, 4}]
71  :  [set(), {1}, {2, 3}, {1, 2, 3}, {1, 2, 3, 4}]
72  :  [set(), {1}, {2, 4}, {1, 2, 4}, {1, 2, 3, 4}]
73  :  [set(), {1}, {3, 4}, {1, 3, 4}, {1, 2, 3, 4}]
74  :  [set(), {2}, {3}, {2, 3}, {1, 2, 3, 4}]
75  :  [set(), {2}, {4}, {2, 4}, {1, 2, 3, 4}]
76  :  [set(), {2}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}]
77  :  [set(), {2}, {1, 2}, {1, 2, 4}, {1, 2, 3, 4}]
78  :  [set(), {2}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}]
79  :  [set(), {2}, {1, 3}, {1, 2, 3}, {1, 2, 3, 4}]
80  :  [set(), {2}, {1, 4}, {1, 2, 4}, {1, 2, 3, 4}]
...........................................
.............................................
.................................................
4 elemanli küme topoloji sayisi = 355 
"""

 

(159 puan) tarafından 
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.6k 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?
1 Haziran 2020 Veri Bilimi kategorisinde (11.5k puan) tarafından  soruldu | 1.5k kez görüntülendi
burada sanirim onsiralama kullanilarak daha verimli bir algoritma yazilabilir ama matematigim yetmedi
(1.6k puan) tarafından 

İlgili sorular

20,284 soru
21,823 cevap
73,508 yorum
2,568,211 kullanıcı