Graphique 3-régulier et circuit d'Euler bidirectionnel
Un urbaniste a construit une ville isolée dont le réseau routier se compose de $2N$ronds-points, chacun reliant exactement trois routes. Une série de tunnels et de ponts garantit que toutes les routes de la ville ne se rejoignent qu'aux ronds-points. Toutes les routes sont à double sens et chaque rond-point est orienté dans le sens des aiguilles d'une montre. Vlad a récemment passé son examen de conduite et est inquiet des ronds-points. Il commence à conduire depuis sa maison et prend toujours le premier montage à chaque rond-point qu'il rencontre. Il s'avère que son voyage inclut toutes les routes de la ville dans les deux sens avant qu'il ne revienne au point de départ dans la direction de départ. Pour quelles valeurs de$N$ Est-ce possible?
J'ai essayé de transformer cela en un problème de théorie des graphes équivalent dans lequel nous pouvons appliquer certains résultats sur des circuits d'Euler ou similaires, mais sans de telles reformulations semblent utiles. Toute aide appréciée!
Réponses
$\text{Partial answer}$
Soit les sommets de notre graphe (les ronds-points) $v_1,v_2,...,v_{2N}$. Nous prouverons que chaque étrange$N$ fonctionne et discuter de même $N$.
$\text{For odd }N$
Bien sûr, des cas $N=3$ et $N=5$ travail ($N$ doit être $\geq 2$ pour que le graphique ait un sens, nous ne pouvons donc pas discuter de $N=1$). Voici$2$ configurations qui montrent que $N=3$ et $N=5$ travail:
Nous allons maintenant montrer que si $N_1$ et $N_2$ travail, alors $N_1+N_2+1$travaux. Supposons que nous ayons$2$ graphes $G_1$ et $G_2$, un avec $2N_1$ sommets et l'autre avec $2N_2$sommets, qui fonctionnent tous les deux. Sélectionner$2$ sommets connectés à partir de $G_1$, $v_1$ et $v_2$ et $2$ sommets connectés depuis $G_2$, $u_1$ et $u_2$. Ajouter$2$ plus de sommets, $w_1$ et $w_2$.
Si nous prouvons que nous pouvons connecter certains sommets de telle sorte que le nouveau graphe fonctionne (qui a $2\cdot(N_1+N_2+1)$), nous avons prouvé que si $N_1$ et $N_2$ sont des nombres valides, il en est de même $N_1+N_2+1$.
Nous ferons les opérations suivantes:
- efface le bord entre $v_1$ et $v_2$
- efface le bord entre $u_1$ et $u_2$
- relier $v_1$ et $w_1$
- relier $v_2$ et $w_2$
- relier $u_1$ et $w_1$
- relier $u_2$ et $w_2$
- relier $w_1$ et $w_2$
Donc à partir de cette configuration initiale
nous atteignons cette configuration
Je n'expliquerai pas vraiment pas à pas pourquoi cela fonctionne, mais une simple analyse du trajet que la voiture fera avec ces nouveaux petits changements confirmera, en effet, que ce nouveau graphique fonctionne.
Donc, $N_1$, $N_2$ le travail implique que $N_1+N_2+1$travaux. Nous avons montré$3$ et $5$ travail, donc chaque étrange $N$ travaux. $\text{ }\blacksquare$
$\text{For even }N$
À ma déception, je n'ai pas réussi à trouver une contradiction ou une preuve pour l'un des petits cas. Notez que c'est$2k$ est une solution, alors tout nombre pair supérieur $\geq 2k+4$ est clairement une solution (en utilisant le résultat ci-dessus, $N_1$ et $N_2$ travail $\Rightarrow$ $N_1+N_2+1$ travaux).
$N=2$ ne fonctionne clairement pas et, bien, pour $N=4$J'ai passé environ une heure à tester les configurations et je n'ai pas réussi à en trouver une qui fonctionne. Je ne pense pas qu'il existe un moyen de prouver qu'un tel graphe existe sans au moins un exemple, qui est introuvable lorsque$N$ est pair, alors j'ai essayé de prouver que même $N$ ne marche pas.
J'ai essayé plusieurs approches telles que la coloration des bords, les invariants et quelques autres astuces, mais encore une fois, je n'ai pas réussi à obtenir une contradiction. Je veux juste souligner qu'il est impossible de contrôler les configurations tout en essayant de réfuter cela même$N$. C'est difficile, simplement parce que vous devez parler purement théoriquement et que vous ne pouvez pas vous fier à n'importe quelle configuration. Regarde ça:
Supposons que vous veniez du bord bleu vers $v$. Dans le premier cas, vous partiriez sur le bord vert,$vv_1$4, mais dans le second cas, vous laisseriez sur le bord rouge $vv_2$:
C'est pourquoi le positionnement des points est crucial, tellement réfutant que même $N$ fonctionne est assez difficile, car nous ne pouvons pas faire d'observations liées à la configuration.
Pour être honnête, je ne suis même pas sûr si même $N$devrait ou ne devrait pas fonctionner. D'une part, sur les (très) nombreuses configurations possibles, on pourrait fonctionner, mais d'autre part, il pourrait y avoir une petite condition qui l'empêche de fonctionner. J'espère que cette "dissection" du problème a aidé de quelque manière que ce soit.
Réponse partielle
Laissez-moi officialiser. Si vous entrez dans un rond-point par la route$i$ tu le quittes par la route $(i \mod 3) +1$.
Soit Ri la route i du rond-point R.
$N=1$ est une solution à votre problème, connectez les deux ronds-points A et B comme suit: pour tout i: Ai est connecté à Bi
Nous montrons maintenant que pour $N_1,N_2$ solution de votre problème alors $N_1+N_2+1$ est aussi une solution.
Laisser $T_1,T_2$ être deux towA_1 avec respectivement $2N_1,2N_2$rond point. Laisser$A_1,B_1$ être deux rond-point connectés en $T_1$ et $A_2,B_2$ connecté en $T_2$. Nous construisons une ville$T_3$ comme suit: on ajoute deux rond-point $C$ et $D$ et connectez-vous ensuite comme suit:
- $A_1$ avec $C.1$
- $B_1$ avec $C_2$
- $C_3$ avec $D_3$
- $A_2$ avec $D_1$
- $B_2$ avec $D_2$
$T_3$ est une solution à votre problème avec $2N_1+2N_2+2=2(N_1+N_2+1)$ ronds-points.
Ainsi chaque étrange $N$ est une solution.
Les commentaires de @Alex Ravsky nous disent que $N=2$n'est pas une solution. Alors peut-être que les nombres pairs sont impossibles (je ne sais pas encore). J'essaierai de penser une réduction avec la même idée afin de le prouver
wece et plus tard Vlad ont fourni la preuve qu'une telle tournée peut exister pour chaque étrange $N$. Nous montrons qu'il ne peut y avoir de telle tournée même$N$.
Incorporez le graphique dans une surface bidimensionnelle. Pour que la notion de «sens horaire» soit bien définie, la surface doit être orientable. Maintenant, le nombre de sommets est$2N$ et le nombre d'arêtes est $3N$. Si une visite comme celle que vous avez décrite existe, l'incorporation peut être considérée comme une carte avec une seule face (qui a$6N$côtés). Mais la généralisation de la formule d'Euler,$$ V-E+F=2-2g, $$ doit tenir, où $g$est le genre de la surface sur laquelle le graphique est intégré. Alors on obtient$$ 2N-3N+1=2-2g. $$ C'est une contradiction si $N$ est même.
Ajouté: l' incorporation souhaitée est obtenue en dessinant le graphique sur une sphère avec des poignées, qui est une surface orientable. Pour expliquer cela un peu plus, commencez par dessiner le graphique sur la sphère. Il y aura, en général, des croisements d'arêtes. Le graphique doit être dessiné conformément à l'ordre des arêtes spécifié dans le sens des aiguilles d'une montre à chaque sommet (rond-point). Pour appliquer cet ordre, même un graphique planaire peut parfois devoir être dessiné avec des croisements d'arêtes.
Supprimez ou réacheminez les arêtes (sans violer les contraintes d'ordre des arêtes) jusqu'à ce qu'il n'y ait plus de croisements. Cela peut être fait de telle manière que le graphe reste connecté. Ajoutez maintenant les arêtes supprimées, une par une: si une arête peut être dessinée dans une seule face, faites-le. (La face sera divisée en deux faces.) Si ce n'est pas le cas, les points d'insertion de l'arête se trouvent sur deux faces différentes. Découpez des trous dans chacune de ces faces et joignez les trous avec un tube. Dans ce processus, les faces ont commencé comme deux surfaces, chacune homéomorphe à un disque et se sont terminées comme une seule surface homéomorphe à un cylindre. Maintenant, acheminez le bord à travers le cylindre, ce qui coupe le cylindre pour qu'il soit à nouveau homéomorphe à un disque.
Une fois que toutes les arêtes ont été ajoutées, nous avons l'incorporation souhaitée du graphique dans une surface orientable. Il s'agit d'une incorporation à 2 cellules, ce qui signifie que toutes les faces sont homéomorphes aux disques, une propriété nécessaire pour appliquer la formule d'Euler.
Les idées de ce croquis proviennent du court article,
JH Lindsay, Un traitement élémentaire de l'imbrication d'un graphe dans une surface . The American Mathematical Monthly 66 (2) (1959) 117-118.
et de la thèse de maîtrise de Jack Edmond
Edmonds, John Robert (1960). Une représentation combinatoire pour des surfaces polyédriques orientées . Université du Maryland.
Une citation de ce dernier:
Théorème 2. Etant donné un graphe linéaire connexe avec un ordre cyclique arbitrairement spécifié des arêtes de chaque sommet, il existe un polyèdre à deux côtés topologiquement unique dont les arêtes et les sommets sont le graphe donné et dont l'ordre des arêtes dans le sens des aiguilles d'une montre à chaque sommet (avec respect sur l'un des côtés) sont comme spécifié.
Ces idées ont une longue histoire, remontant à Lothar Heffter dans les années 1890. La notion d'associer un embeddage à une spécification de l'ordre des arêtes à chaque sommet d'un graphe passe désormais par le nom de système de rotation . Si vous souhaitez essayer les idées, vous pouvez vérifier qu'il existe essentiellement trois systèmes de rotation différents pour$K_4$, produisant trois plongements différents, un sphérique (genre $0$) encastrement avec quatre faces triangulaires et deux toroïdales (genre $1$) plongements, chacun avec deux faces - soit un triangle et un nonagone, soit un quadrilatère et un octogone.