Yonlu bir cizgenin gecisgenligi uzerine

Question

Verilen yonlu cizgenin geciskenligini kontrol eden bir algoritma tarif edebilir misiniz?

Comments

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.