Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
1 beğenilme 0 beğenilmeme
560 kez görüntülendi

image

Resimde gördüğünüz gibi, İngiltere Premier Liginde 2016-2017 sezonunda birbirini yenen takımlardan bir döngü oluşturulmuş ve Arsenal ile başlayıp Arsenal ile bitirilerek bu sezonda herhangi bir takımın bir diğerini yenebileceği "ispatlanmış".

Espri bir yana, ben bu işi bir insanın yapabileceğinden şüpheliyim. Bu sezon Arsenal'in $9$ galibiyeti, Chelsea'nin $11$ galibiyeti... diye giderek bir döngü kurmaya çalıştığımızda $11.9^3.7.5^6.4^3.3^5.2=27280638000000$ farklı sonuca gidebileceğimiz bir labirent var.

Bu döngüyü oluşturabilecek bir algoritma yazılabilir mi, yine Arsenal'den başlayıp Arsenal ile bitirebileceğimiz kaç döngü olduğunu da bulabilir miyiz?

Hatta işi biraz daha ileri götürüp. Fikstürdeki sonuçlara değil de sadece puan tablosuna bakarak oluşabilecek döngülerin sayısının bulunduğu aralığı hesaplatabilir miyiz?

Serbest kategorisinde (2.9k puan) tarafından  | 560 kez görüntülendi

Tam olarak ne sordugunuzu gercekten anlamadim. X takimi ile baslayip x takimi ile biten herhangi bir dongu yazabiliriz. Cunku, neden yazamayalim? Olusabilecek tum donguleri de listeleriz. Cunku, neden listeleyemeyelim? Gerek ve yeter zaman verildigi taktirde tum soyledikleriniz gayet yapilabilir seyler. Anlayamadim asil soruyu

Yukarıdaki skorlar gerçek skorlar, yani amaç döngü kurmak değil. Eldeki fikstürle bu döngüyü kurabilmek amaç.

Güzel bir soru

Bu sorunun cevabi cizgede (graph) dongu (cycle) aramaya denk. Bu algoritma bu isi yapiyor. Elinizdeki cizgede ayni verteksleri birden fazla kenar bagliyor. Yani alinda cizge degil bir multicizge var ama bunu bir cizgeye donusturup algoritmayi calistirabilirsiniz.

20,207 soru
21,731 cevap
73,297 yorum
1,896,269 kullanıcı