Tek hamlede
Tek dereceli düğümler
Çizilen kenarlar
Çizme yolu sayısı

    • 0 tek dereceli düğüm: bir devre, herhangi bir düğümden yine ona
    • 2 tek dereceli düğüm: birinden ötekine bir yol
    • 4 ya da daha fazla: tek hamlede imkânsız

    Yöntem

    Euler yolları ve devreleri hakkında daha fazlası

    Euler Yolu Bulucu

    Noel Baba'nın evini kalemi kaldırmadan ve hiçbir çizgiden iki kez geçmeden çizebilir misiniz? Çizebilirsiniz, ama yalnızca alttaki iki köşeden birinden başlarsanız; her birinden 44 ayrı yol vardır. Nedeni bir düğümün derecesi, yani orada buluşan çizgilerin sayısıdır: kalem bir düğümden her geçişinde onun iki çizgisini kullanır. Leonhard Euler bu kuralı 1736'da Königsberg'in yedi köprüsüyle buldu. Bir şeklin üzerinden kendiniz geçin, nerede ve neden tıkandığınızı görün, ipucu isteyin ya da bir algoritmanın çizişini izleyin. Bir şekil seçin ve üzerinden geçin: başlamak için bir düğüme dokunun, sonra sırayla kenarlara ya da sonraki düğümlere dokunun veya düğümden düğüme sürükleyin. Her kenar yalnızca bir kez kullanılabilir. Geri bir adımı geri alır, İpucu bir sonraki güvenli kenarı gösterir, Çöz ise Fleury ya da Hierholzer algoritmasını adım adım oynatır. Tek dereceli düğümler dolu çizilir ve her düğümün üzerindeki rozet onun derecesidir. Çiz kipinde boş bir yere dokunmak düğüm ekler, iki düğüme dokunmak onları birleştirir, bir kez daha dokunmak ikinci bir kenar ekler; düğümü taşımak için sürükleyin. Sil düğümleri ve kenarları kaldırır. Tek dereceli düğüm sayısı ikiden fazlaysa Ekle, şeklin çizilebilmesini sağlayan kenarları yerleştirir.

    Nasıl çalışır

    1. Bir şekil seçin; örneğin Königsberg'in yedi köprüsü, Noel Baba'nın evi ya da bir yıldız. Ya da Çiz kipinde kendi şeklinizi çizin; iki düğüm arasına istediğiniz kadar kenar koyabilirsiniz.
    2. Başlamak için bir düğüme dokunun, sonra sırayla kenarlara ya da düğümlere dokunun veya düğümden düğüme sürükleyin. Tıkanırsanız durum satırı nedenini söyler; Geri bir adımı geri alır, İpucu güvenli bir kenar gösterir.
    3. Şeklin altındaki derece kuralını okuyun, imkânsız bir şekle önerilen kenarları ekleyin ya da Çöz düğmesine basıp Fleury veya Hierholzer algoritmasının şekli adım adım çizişini izleyin.

    Neden tek dereceli düğümler belirleyicidir

    Bir düğümden geçen hamle bir çizgiyle gelir, başka bir çizgiyle gider; yani o düğümün çizgilerini ikişer ikişer kullanır. Yalnızca hamlenin başladığı ya da bittiği yerde bir çizgi eşsiz kalabilir. Bu yüzden tek sayıda çizgisi olan bir düğüm ya başlangıç ya da bitiş olmalıdır. Tek dereceli düğüm yoksa hamle başladığı yerde biter: bir Euler devresi. İki tane varsa birinden ötekine gider: bir Euler yolu. Dört ya da daha fazlası varsa tek hamle için fazla uç vardır ve k tek dereceli düğüm k/2 hamle gerektirir. Königsberg'de dört kara parçası vardı; köprü sayıları beş, üç, üç ve üçtü: dördü de tek, bu yüzden hiçbir yürüyüş her köprüden bir kez geçemezdi. Bunlardan ikisi arasına bir köprü daha eklenseydi yürüyüş mümkün olurdu.

    Fleury ve Hierholzer algoritmaları

    Bir şeklin çizilebildiğini bilmek onu çizmekle aynı şey değildir: dikkatsiz bir hamle, hâlâ ihtiyaç duyduğu çizgilerden kendini koparabilir. Fleury'nin 1883 tarihli algoritması bunu tek bir kuralla önler: bir köprüden, yani kaldırıldığında kalan çizgileri iki parçaya ayıracak bir çizgiden, başka çizgi yoksa dışında asla geçmeyin. Hierholzer'in 1873'te yayımlanan bir çalışmadan gelen algoritması daha hızlıdır: tıkanana kadar istediğiniz yere yürüyün, ki bu yalnızca başlangıç noktasında olabilir; sonra turda hâlâ boş çizgisi olan bir düğümden kapalı bir ilmek daha yürüyüp onu tura ekleyin. Süresi kenar sayısıyla orantılı büyür ve bilgisayarlar Euler yollarını böyle bulur.

    Sık sorulan sorular

    Euler yolu ile Euler devresi arasındaki fark nedir?

    İkisi de bir grafın her kenarını tam bir kez kullanır. Euler devresi başladığı yerde biter; Euler yolu başka bir yerde biter. Bağlantılı bir grafın her düğümü çift dereceliyse devresi, tam iki düğümü tek dereceliyse yolu vardır; yol o zaman birinden ötekine gider.

    Königsberg'in yedi köprüsünden neden birer kez geçilemez?

    Her kara parçasını bir düğüm, her köprüyü bir kenar olarak çizin. Kneiphof adasının beş köprüsü, öteki üç kara parçasının üçer köprüsü vardı; yani dört düğümün dördü de tek derecelidir. Bir yürüyüş ancak tek dereceli bir düğümde başlayabilir ya da bitebilir ve dört tane fazladır. Bunlardan ikisi arasına bir köprü eklemek geriye iki tek dereceli düğüm bırakır ve yürüyüş mümkün olur.

    Noel Baba'nın evi kaç farklı şekilde çizilebilir?

    Alttaki iki köşenin her birinden 44, toplamda 88; farklı bir sıra ya da yön farklı bir yol sayılırsa. Başka hiçbir düğümden çizilemez, çünkü tek sayıda çizgisi olan yalnızca o iki alt köşedir. Uygulama küçük şekillerin yollarını bu biçimde sayar.

    Grafta köprü nedir?

    Kaldırıldığında bağlantılı bir grafı iki parçaya ayıran kenardır. Fleury algoritması, başka seçeneği olduğu sürece kalan kenarlar arasındaki bir köprüden asla geçmez, çünkü şeklin bir parçası geride kalırdı. Bu uygulamada, bir köprüden çok erken geçtiği için tıkanan bir hamleye bunun hangi adım olduğu söylenir.

    İki düğüm arasında birden fazla kenar olabilir mi?

    Olabilir. Paralel kenarları olan grafa çoklu graf denir ve Königsberg için gereklidir: Kneiphof'u her iki kıyıya ikişer köprü bağlıyordu. Çiz kipinde iki düğüme yeniden dokunarak aralarına dörde kadar kenar ekleyebilirsiniz. Derece kuralı aynı biçimde işler ve her kenarı sayar.

    Denemeye hazır mısınız?

    PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

    Editöre Git