Çevrimiçi ve yaklaşık kaplama zamanı problemleri üzerine

Olasılık teorisindeki klasikleşmiş kupon toplama probleminin bir genellemesi olarak, Markov zincirleri üzerindeki rastgele dolaşmanın kaplama zamanı literatürdeki birçok çalışmada incelenmiştir. Özellikle, bağlantılı ve yönsüz çizgeler üzerindeki basit rastgele dolaşmanın kaplama zamanı üzerine birçok sonuç bulunmaktadır. Bu tezde, çizgelerin kaplama zamanı üzerine iki yeni problem üzerine çalışılmıştır. İlk olarak, zamanla büyüyen bir çizge üzerinde hareketlerinin zaman aralıkları rassal olan bir gezicinin olduğu bir çevrimiçi model inşa edilmiştir. Belirli bir zamana kadar kaplanan köşelerin sayısı basit bir model üzerinde incelenerek bu çalışma başlatılmış ve çeşitli araştırma alanları tartışılmıştır. İkincisi, klasik kaplama zamanı tanımı genelleştirilerek, kısmi kaplama ve tam kaplama arasındaki farklar anlaşılmaya çalışılmıştır. Yolak çizgesi ve tam çizge gibi özel çizge ailelerinde yaklaşık kaplama zamanı incelenerek bu çalışma başlatılmış, büyüklük derecesi olarak daha kolay yaklaşık zamanına izin veren çizge yapıları keşfedilmesi temel motivasyon olmuştur. Bütünlük açısından, klasik kaplama zamanı üzerine temel sonuçlar ile kenar kaplama ve dinamik versiyonlar gibi problemin literatürde yer alan çeşitli varyasyonları da tezde verilmiştir.