$\text{Partial answer}$

Grafiğimizin (döner kavşaklar) köşelerinin $v_1,v_2,...,v_{2N}$. Her tuhaflığı kanıtlayacağız$N$ çalışır ve hatta hakkında tartışır $N$.

---

$\text{For odd }N$

Tabii ki davalar $N=3$ ve $N=5$ iş ($N$ olmalıdır $\geq 2$ grafiğin anlamlı olması için, bu nedenle hakkında tartışamayız $N=1$). Burada$2$ bunu gösteren konfigürasyonlar $N=3$ ve $N=5$ iş:

Şimdi göstereceğiz eğer $N_1$ ve $N_2$ iş o zaman $N_1+N_2+1$İşler. Varsayalım ki bizde$2$ grafikler $G_1$ ve $G_2$, biri ile $2N_1$ köşeler ve diğeri $2N_2$her ikisi de çalışan köşeler. Seçiniz$2$ bağlı olan köşeler $G_1$, $v_1$ ve $v_2$ ve $2$ bağlı olan köşeler $G_2$, $u_1$ ve $u_2$. Ekle$2$ daha fazla köşe, $w_1$ ve $w_2$.

Yeni grafiğin çalışacağı şekilde bazı köşeleri bağlayabileceğimizi kanıtlarsak ( $2\cdot(N_1+N_2+1)$), eğer $N_1$ ve $N_2$ geçerli sayılardır, öyleyse öyledir $N_1+N_2+1$.

Aşağıdaki işlemleri yapacağız:

• aradaki kenarı sil $v_1$ ve $v_2$
• aradaki kenarı sil $u_1$ ve $u_2$
• bağlanmak $v_1$ ve $w_1$
• bağlanmak $v_2$ ve $w_2$
• bağlanmak $u_1$ ve $w_1$
• bağlanmak $u_2$ ve $w_2$
• bağlanmak $w_1$ ve $w_2$

Yani bu ilk yapılandırmadan

bu konfigürasyona ulaşıyoruz

Aslında neden işe yaradığını adım adım açıklamayacağım, ancak arabanın bu yeni küçük değişikliklerle yapacağı yolculuğun basit bir analizi, gerçekten de bu yeni grafiğin çalıştığını doğrulayacaktır.

Böylece, $N_1$, $N_2$ iş şunu ima eder $N_1+N_2+1$İşler. Gösterdik$3$ ve $5$ iş, bu yüzden her garip $N$ İşler. $\text{ }\blacksquare$

---

$\text{For even }N$

Hayal kırıklığıma göre, küçük davalardan biri için bir çelişki ya da kanıt bulamadım. Unutmayın ki$2k$ bir çözüm, o zaman herhangi bir çift sayı daha büyük $\geq 2k+4$ açıkça bir çözümdür (yukarıdaki sonucu kullanarak, $N_1$ ve $N_2$ iş $\Rightarrow$ $N_1+N_2+1$ İşler).

$N=2$ açıkça çalışmıyor ve $N=4$Yapılandırmaları test etmek için yaklaşık bir saat harcadım ve işe yarayan bir tane bulmayı başaramadım. En az bir örnek olmadan böyle bir grafiğin var olduğunu kanıtlamanın bir yolu olduğunu sanmıyorum,$N$ eşit, bu yüzden bunu bile kanıtlamaya çalıştım $N$ çalışmıyor.

Kenar renklendirmeleri, değişmezler ve diğer bazı hileler gibi birkaç yaklaşım denedim, ancak yine bir çelişki yakalamayı başaramadım. Bunu bile çürütmeye çalışırken konfigürasyonları kontrol etmenin imkansız olduğunu belirtmek istiyorum.$N$. Zor, çünkü tamamen teorik olarak konuşmanız gerekiyor ve herhangi bir konfigürasyona güvenemiyorsunuz. Şuna bir bak:

Mavi kenardan geldiğinizi varsayalım. $v$. İlk durumda, yeşil kenarda bırakırdın,$vv_1$4, ama ikinci durumda kırmızı kenarda bırakırdın $vv_2$:

Bu yüzden noktaların konumu çok önemlidir, bu yüzden $N$ yapılandırma ile ilgili gözlemler yapamadığımız için işler oldukça zordur.

Dürüst olmak gerekirse, emin değilim bile $N$çalışmalı veya çalışmamalı. Bir yandan, pek çok olası konfigürasyondan biri işe yarayabilir, ancak diğer yandan, çalışmasını engelleyen küçük bir koşul olabilir. Umarım sorunun bu "diseksiyonu" herhangi bir şekilde yardımcı olmuştur.

Kısmi cevap

Resmileştirmeme izin verin. Karayolu ile bir döner kavşağa girerseniz$i$ onu karayoluyla terk et $(i \mod 3) +1$.

Ri döner kavşak R'nin i yolu olsun.

$N=1$ sorununuzun çözümüdür. iki döner kavşak A ve B'yi aşağıdaki gibi bağlayın: tüm i: Ai, Bi'ye bağlıdır

Şimdi bunu gösteriyoruz $N_1,N_2$ o zaman sorunun çözümü $N_1+N_2+1$ aynı zamanda bir çözümdür.

İzin Vermek $T_1,T_2$ sırasıyla iki A_1 çekilecek $2N_1,2N_2$dönel kavşak. İzin Vermek$A_1,B_1$ birbirine bağlı iki kavşak olmak $T_1$ ve $A_2,B_2$ bağlı $T_2$. Bir kasaba inşa ediyoruz$T_3$ aşağıdaki gibi: iki döner kavşak ekliyoruz $C$ ve $D$ ve ardından aşağıdaki gibi bağlanın:

• $A_1$ ile $C.1$
• $B_1$ ile $C_2$
• $C_3$ ile $D_3$
• $A_2$ ile $D_1$
• $B_2$ ile $D_2$

$T_3$ ile ilgili sorunun çözümü $2N_1+2N_2+2=2(N_1+N_2+1)$ kavşaklar.

Böylece her tuhaf $N$ bir çözümdür.

@Alex Ravsky yorumları bize şunu söylüyor: $N=2$bir çözüm değil. Öyleyse olabilir Çift sayılar imkansızdır (henüz bilmiyorum). Bunu kanıtlamak için aynı fikirle bir indirgeme düşünmeye çalışacağım

wece ve daha sonra Vlad, böyle bir turun her tuhaf kişi için olabileceğine dair bir kanıt sağladı. $N$. Böyle bir turun bile olamayacağını gösteriyoruz$N$.

Grafiği iki boyutlu bir yüzeye gömün. "Saat yönünde" kavramının iyi tanımlanabilmesi için, yüzeyin yönlendirilebilir olması gerekir. Şimdi köşe sayısı$2N$ ve kenarların sayısı $3N$. Tanımladığınız gibi bir tur varsa, bu durumda yerleştirme, tek yüzlü bir harita olarak kabul edilebilir ($6N$taraf). Ancak Euler formülünün genelleştirilmesi,$$ V-E+F=2-2g, $$ tutmalı, nerede $g$grafiğin gömülü olduğu yüzeyin cinsidir. Böylece anlıyoruz$$ 2N-3N+1=2-2g. $$ Bu bir çelişki ise $N$ eşittir.

Eklendi: Yönlendirilebilir bir yüzey olan kulplu bir küre üzerine grafiğin çizilmesiyle istenen gömme elde edilir. Bunu biraz daha açıklamak için küre üzerine grafiği çizerek başlayın. Genel olarak, bazı kenar kesişimleri olacaktır. Grafik, her bir tepe noktasında (döner kavşak) belirtilen saat yönünde kenar sırasına göre çizilmelidir. Bu sıralamayı uygulamak için, bazen bir düzlemsel grafiğin bile kenar geçişleri ile çizilmesi gerekebilir.

Kesişme kalmayıncaya kadar kenarları kaldırın veya yeniden yönlendirin (kenar sıralaması kısıtlamalarını ihlal etmeden). Bu, grafik bağlı kalacak şekilde yapılabilir. Şimdi, kaldırılan kenarları birer birer geri ekleyin: tek bir yüz içinde bir kenar çizilebiliyorsa, bunu yapın. (Yüz iki yüze bölünecektir.) Aksi takdirde, kenarın yerleştirme noktaları iki farklı yüzdedir. Bu yüzlerin her birinde delikler açın ve delikleri bir tüp ile birleştirin. Bu süreçte yüzler, her biri bir diske homeomorfik iki yüzey olarak başladı ve bir silindire tek bir yüzey homeomorfik olarak sona erdi. Şimdi kenarı, silindiri kesen silindir boyunca yönlendirin, böylece tekrar bir diske homomorfik olsun.

Tüm kenarlar geri eklendiğinde, grafiğin yönlendirilebilir bir yüzeye istenen şekilde yerleştirilmesini elde ederiz. Bu, 2 hücreli bir katıştırmadır, yani tüm yüzler disklere homeomorfiktir; bu, Euler'in formülünü uygulamak için gerekli bir özelliktir.

Bu taslaktaki fikirler kısa makaleden alınmıştır,

JH Lindsay, Grafiğin Bir Yüzeye Gömülmesinin Temel Bir İncelemesi . The American Mathematical Monthly 66 (2) (1959) 117-118.

ve Jack Edmond'un yüksek lisans tezinden

Edmonds, John Robert (1960). Yönlendirilmiş çok yüzlü yüzeyler için bir kombinatoryal temsil . Maryland Üniversitesi.

İkincisinden bir alıntı:

Teorem 2. Her bir tepe noktasına kenarların keyfi olarak belirlenmiş döngüsel sıralaması ile bağlantılı bir doğrusal grafik verildiğinde, topolojik olarak benzersiz, iki taraflı bir çokyüzlü vardır. taraflardan birine) belirtildiği gibidir.

Bu fikirlerin, 1890'larda Lothar Heffter'a kadar uzanan uzun bir tarihi vardır. Gömülü bir grafiğin her tepe noktasındaki kenar sıralamalarının bir özelliği ile ilişkilendirme kavramı artık ad döndürme sistemi tarafından kullanılmaktadır . Fikirleri denemek istiyorsanız, temelde üç farklı rotasyon sistemi olduğunu doğrulayabilirsiniz.$K_4$, üç farklı düğün, bir küresel (cins $0$) dört üçgen yüz ve iki toroidal (cins $1$) her biri iki yüze sahip - bir üçgen ve bir üçgen veya bir dörtgen ve bir sekizgen.