9. Sınıf Çizge Kuramı (Königsberg Şehri) Nedir?

Soru: Çizge kuramında, Königsberg probleminin çözümsüzlüğü hangi genel teoreme yol açmıştır? Bu teoremi basit bir çizge örneği üzerinde açıklayın: Düğümler: M, N, O; Kenarlar: M-N, N-O, O-M, M-N (iki paralel kenar). Bu çizgede Euler yolu var mıdır?

Çözüm: Königsberg problemi, Euler yolu/teoremi'nin temelini oluşturmuştur. Teorem: Bir çizgede Euler yolu var olması için, çizge bağlantılı olmalı ve en fazla iki düğüm tek dereceli olmalıdır. Verilen çizge için dereceler:

• M: M-N, M-N, O-M → derece = 3 (M-N kenarı iki kez sayılır, çünkü paralel kenarlar ayrıdır)
• N: M-N, M-N, N-O → derece = 3
• O: N-O, O-M → derece = 2

Tek dereceli düğümler: M (3) ve N (3). Sadece iki düğüm tek dereceli olduğu ve çizge bağlantılı olduğu için Euler yolu vardır. Yol, M veya N'den başlayıp diğerinde biter.