Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
340 kez görüntülendi
Verilen yonlu cizgenin geciskenligini kontrol eden bir algoritma tarif edebilir misiniz?
Lisans Matematik kategorisinde (1.6k puan) tarafından  | 340 kez görüntülendi
Geçişkenlik ne?

transitivity. yani $x$ den $y$ ye ok ve $y$ den $z$ ye ok varsa $x$ den z ye ok olmali. Akrabalik iliskilerinde mesela ebeveyinlik kardeslik geciskendir. Toplumumuzda mesela ask iliskileri pek gecisken olmuyor. Hatta bu konu bir suru turk filmine/sarkisina (sarki sozleri saraptan cok bozuk sut gibi yaslanmis ama olsun)konu oluyor.

 

ebeveyinlik gecisken degil ya, dede anneanne olmayi falan da ebeveyinlik sayarsak oluyor. birisinden uzun/kisa/sisman olmak transitiv ama mesela.

Valla aklıma ilk gelen matris gösterimi oldu. Köşeleri numaralandır: $ e_1, \ldots, e_n $. Şu kuralla bir $n \times n$ matrisi oluştur: eğer $e_i$'den $e_j$'ye bir ok varsa, $ij$ girdisi $1$ olsun, yoksa $0$ olsun.

Bu durumda geçişkenlik kuralı $A_{ij}=A_{jk}=1$ ise $A_{ik}=1$ olur kuralına denk. Belki sadece üç köşe varken ne olur onu inceleyip, sonra bazı $3\timesn3$ minörlere de bakabilirsin.
evet evet yani adjacency matrisi $A$yi olusturup, $A^2 \geq A$ sartina bakmam gerekiyor (burada buyukluk girdi basina). Ama cok eglenceli baska bir cozumunu buldum diger sorumla alakali. bi uygun zaman buldugumsa yazacagim
toplama islemi minimum islemi olsun, carpma islemi de toplama islemi olsun.

cizgenin matris gosterimi soyle olsun. Eger $e_i$ den $e_j$ ye ok varsa $1$, yok ise $\infty$ yazalim.

matrisin kosegenlerini $0$ yapalim (ya buradan emin degilim kendine ok varsa $1$ de birakabiliriz galiba dusunucem). Idiam su ki bu matrisi, yukarida tanimladigim islemlerle $n$ inci kuvvetini alip hepsini "toplarsak" elimize gecen matris, $e_i$ den $e_j$ ye  $n$ adimda giden en kisa yolun uzunlugunu verecek.
20,248 soru
21,774 cevap
73,421 yorum
2,150,245 kullanıcı