SPOJ PPATH, 4 basamaklı bir basamağı başka bir 4 basamaklı basamağa dönüştürme

Question

SPOJ PPATH numaralı soruna iki dört basamaklı asal sayı verilir ve en küçük adımlarla ilk basamağı ikincisine dönüştürmeliyiz. Tek bir rakamı her seferinde ve her adımda değiştirerek sayı asal olmalıdır. Eğer primler söz konusu moda dönüştürülemezse 'IMPOSSIBLE' vermeliyiz. Bununla birlikte, imkansız olayın bile dikkate alınmadığı bir probleme ilişkin çözümler kabul edilmiştir; bu da, her dört basamaklı asalin, belirtilen şekilde herhangi bir başka dört-haneli prime dönüştürülebileceği varsayımına yol açmaktadır. Bunu kanıtlayamadım. Bu doğru mu? Resmi olarak nasıl kanıtlayabiliriz? Ayrıca n-basamaklı primler için genel bir sonuç var mı?

Answer 1

dört basamaklı sayı için bu bir program sayesinde etraflıca doğrulanabilir ancak n basamağı için teorik olarak bunu kanıtlamak zorunda kalacak.

Answer 2

bir asal 4 haneli sayılar olarak köşe ve 1 basamak farklılık gösteren iki numara bağlayan kenarları olan bir yönsüz grafik bilgisi iyi böylece. Bir köşe noktasından diğerine en yakın yolu bulmanız istenir. Böyle bir yol bulamazsanız, IMPOSSIBLE sonuç üretilecektir. Bu, grafiğin birden fazla bağlı bileşene sahip olduğu anlamına gelir. Bu grafiğin bağlı bir bileşeni olduğunu ispatlarsanız, yolun varlığını garanti eder.

Ben resmi bir şekilde bunu kanıtlamak için nasıl bilmiyorum ama yukarıda açıklanan grafik yalnızca tek bağlı bileşen olup olmadığını kontrol etmek çok kolaydır. Bir algoritma yazabilir ve sonucu 4 haneli grafikler için bir kanıt olarak yorumlanabilir.