Bir ailenin topoloji olup olmadığını test eden bir bilgisayar programı - Matematik Kafası

Bir ailenin topoloji olup olmadığını test eden bir bilgisayar programı

0 beğenilme 0 beğenilmeme
116 kez görüntülendi

$X$ sonlu bir küme olmak üzere herhangi bir $\tau\subseteq \mathcal{P}(X)$ ailesinin söz konusu $X$ kümesi üzerinde topoloji olup olmadığını kontrol eden bir program (online da olabilir) bilen var mı? Varsa ve paylaşırsa sevinirim.

25, Ocak, 25 Uygulamalı Bilgisayar Bilimi kategorisinde murad.ozkoc (8,870 puan) tarafından  soruldu

Var mıdır bilmiyorum ama yazmak çok zor olmasa gerek. $n$ elemanlı bir kümenin her alt kümesini, girdileri $1$ ve $0$'lardan oluşan bir $v\in \mathbb{R}^n$ vektörü ile eşleyebiliriz. Bu vektörlerin toplamları ve farklarını bir şekilde kullanarak kesişim ve birleşimleri yine vektörler cinsinden açıklayabiliriz. Bu vektörlerin ailemizde olup olmadığını da kontrol edebiliriz.

Küme sonlu olduğu için ikili kesişim ve ikili birleşim yeterli olacaktır.

Özgür bunu matlab ile mi yaparız?

Herhangi bir dille uygulanabilir. Fakat eleman sayısı arttıkça bu basit kontrol işlemi çok uzun sürer gibi görünüyor.

Bir arkadaşım matematica'da bu işi yapacak bir program yazdı. $6$ elemanlı bir kümenin kuvvet kümesinin $30$ elemanlı bir altailesini ele aldık. Topoloji olup olmadığını kontrol etmek için matematica'da yazılan programı çalıştırdığımızda maalesef bilgisayar kilitlendi.

Ben cevap vermeyi unutmuşum, özür diliyorum. Verecek cevabım da yok maalesef.


1 cevap

0 beğenilme 0 beğenilmeme

surda var.  https://stackoverflow.com/questions/8814059/generating-topological-space-diagram-in-mathematica/8815337#8815337


suraya da bakilabilir. https://mathematica.stackexchange.com/questions/5/generating-a-topological-space-diagram-for-an-n-element-set/165#165


Ben test ettim 22 eleman icin 29 saniye, 24 eleman icin 95 saniye aliyor. 27 eleman icin denedim yaklasik 5 dakika sonra sonlandirdim programi.


In[1]:= set = Subsets[Range@6]

Out[1]= {{}, {1}, {2}, {3}, {4}, {5}, {6}, {1, 2}, {1, 3}, {1, 4}, {1,
5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3,
6}, {4, 5}, {4, 6}, {5, 6}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 2,
6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6}, {1, 5,
6}, {2, 3, 4}, {2, 3, 5}, {2, 3, 6}, {2, 4, 5}, {2, 4, 6}, {2, 5,
6}, {3, 4, 5}, {3, 4, 6}, {3, 5, 6}, {4, 5, 6}, {1, 2, 3, 4}, {1, 2,
3, 5}, {1, 2, 3, 6}, {1, 2, 4, 5}, {1, 2, 4, 6}, {1, 2, 5, 6}, {1,
3, 4, 5}, {1, 3, 4, 6}, {1, 3, 5, 6}, {1, 4, 5, 6}, {2, 3, 4,
5}, {2, 3, 4, 6}, {2, 3, 5, 6}, {2, 4, 5, 6}, {3, 4, 5, 6}, {1, 2,
3, 4, 5}, {1, 2, 3, 4, 6}, {1, 2, 3, 5, 6}, {1, 2, 4, 5, 6}, {1, 3,
4, 5, 6}, {2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 6}}

In[2]:= set2 =
Sort@Join[{First@set, Last@set}, RandomSample[Most@Rest@set, 22]]

Out[2]= {{}, {1}, {2}, {3}, {4}, {5}, {6}, {1, 2}, {1, 3}, {2, 3}, {5,
6}, {1, 2, 3}, {1, 3, 4}, {1, 3, 6}, {1, 4, 5}, {1, 5, 6}, {2, 3,
4}, {2, 3, 6}, {2, 4, 5}, {4, 5, 6}, {1, 2, 3, 5}, {2, 3, 4, 5}, {1,
2, 3, 5, 6}, {1, 2, 3, 4, 5, 6}}

In[3]:= topologyQ[x_List] :=
Intersection[x, #] === # &[
Union[{Union @@ x}, Intersection @@@ Rest@#, Union @@@ #] &@
Subsets@x]

In[4]:= topologyQ@set2 // AbsoluteTiming

Out[4]= {95.7043, False}

8, Şubat, 8 Okkes Dulgerci (1,425 puan) tarafından  cevaplandı
Teşekkür ederim.
...