Teorema del coloreo de carreteres

Un grafo dirigit en un coloreo que sempre que se seguixquen les instruccions "blau-roig-roig-blau-roig-roig-blau-roig-roig", respectant la direcció de les fleches, independentment del nodo inicial, conduïx al nodo groc. Análogamente, les instruccions "blau-blau-roig-blau-blau-roig-blau-blau-roig" sempre conduïxen al nodo vert.

En teoria de grafos el teorema de coloreo de carreteres, teorema del camí coloreado o, conegut antigament com la conjectura del coloreo de carreteres, és un problema de coloreo de grafos plans. El plantejament inicial, en térmens intuïtius, consistix que donada una ret (grafo que representa ya siga una ciutat o llaberint) en determinades condicions, i donada una posició en el mateix, buscar si existix, i quin és, una série d'instruccions que independentment del posicionament inicial, permeten aplegar a la posició requerida. Usualment, este problema es planteja en térmens coloquials com:

Supongam que algú visita una ciutat que no coneix, en la peculiaritat de que dit lloc no conté cap classe de senyal indicativa. Després d'haver vagat un parell d'hores, el visitant li demana ajuda a algú per a aplegar a determinat lloc, contant-li que no sap on està. ¿Existix alguna série d'instruccions que se li puguen donar al turiste per a que, independentment d'on es trobe, puga aplegar al seu destí?

Esta teorema va ser conjeturado per primera volta per Roy Adler, Wayne Goodwyn i Benjamin Weiss en 1970 i replantejat en 1977, sent provat 37 anys despuix, en 2007 per l'israelita d'orige rus Avraham Trahtman. Les seues aplicacions van des de la cartografia fins al simbolisme dinàmic i la teoria d'automatisació.

Nocions prèvies

La notació usada a continuació és la donada per Trahtman en la seua demostració original. Les definicions i teoremes han segut adaptats de ací i ací.

Grafos AGW

Artícul principal → Grafo dirigit.

En un dígraf, cridem al conjunt de totes les arestes que ixen d'un vèrtiç un manojo (bunch, en anglés) si cada una de dites arestes aplega a un sol vèrtiç.

Un dígraf $D$ es diu extern-regular o en grau extern uniforme si existix un sancer $\Delta$ tal que el grau exterior de tot vèrtiç (número d'arestes que partixen d'ell) té com a valor $\Delta$.

cal mencionar que análogamente, existix la noció de dígraf intern-regular i que, donat un grafo extern-regular, açò no implica que també siga intern-regular o viceversa.

Un dígraf $D$ és periòdic si és possible trobar una partició en el conjunt de vèrtiços, $V(D)$, de $k\ge 2$ subconjunts, $V_1,V_2,\dots ,V_k,V_{k+i}=1$ tal que si $(u,v)$ és una aresta, llavors $u\in V_i,v\in V_{i+1}$ per a algun $i$ en $1\le i\le k$. Tal partició de $V(D)$ és cridada una $k$-partició cíclica de $D$.

Per tant, $D$ és periòdic si existix una $k$-partició cíclica de $V(D)$ per a algun sancer $k\ge 2$. Si $D$ no és periòdic, es diu que $D$ és aperiódico. Ademés, un grafo fortament conexo aperiódico i extern-regular, és usualment cridat un grafo AGW.

Coloreo sincronisat

Artícul principal → Coloració de grafos.

Donat un dígraf $D$, un coloreado $c$ del grafo es diu propi si qualssevol dos arestes incidents al mateix vèrtiç de $D$ tenen assignat distint color. Per a un dígraf fortament conexo $D$ en grau exterior regular $\Delta$ un $\Delta$-coloreo propi $c$ es diu sincronisat si per a qualsevol vèrtiç $v$ de $D$, existix una seqüència $s_v$ de colors tal que para tot vèrtiç $u$ de $D$, el camí dirigit en vèrtiç inicial $u$ determinat per $s_v$ té com a vèrtiç final $v$. En este cas, la seqüències $s_v$ es diu una seqüència sincronisada del vèrtiç $v$.

Esta terminologia de coloreo sincronisat és donada per la relació entre la noció de paraula sincronisada en la teoria d'autómates finitos.

Paraules sincronisades

Dígraf en paraula de sincronisació BRB per al nodo 1, a on R correspon a aresta roja i B correspon a aresta blava.

Vore també: Teoria d'autómates

Si existix un camí en un autómata des de l'estat $𝒑$ a l'estat $𝒒$ i les arestes del camí són ${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_k$, en eixe orde, després per a $s={\sigma }_1,{\sigma }_2,\cdots ,{\sigma }_k\in {\Sigma }^{+}$, escrivim $𝒒=𝒑s$.

Siga llavors $Ps$ el mapage del subconjunt $P\subseteq G$ a través de $s\in {\Sigma }^{+}$ i siga $P{s}^{-1}$ el conjunt maximal d'estats $Q$ tal que $Qs\subseteq P$.

Una paraula (també coneguda com cadena) $s\in {\Sigma }^{+}$ és cridada paraula sincronisada de l'autómata en grafo de transició $D$ si $|Ds|=1$. Per un atre costat, un parell de vèrtiços $𝒑$ i $𝒒$ d'un grafo es diuen sincronisats si existix $s\in {\Sigma }^{+}$ tal que $𝒑s=𝒒s$. En el cas contrari, és dir, si para tot $s\in {\Sigma }^{+}$, $𝒑s\ne 𝒒s$, cridem al parell de vèrtiços punt mort (deadlock, en anglés).

Un parell de vèrtiços (estats) $𝒑$ i $𝒒$ sincronisats són cridats estables si per a qualsevol paraula $u$, el parell $𝒑u$ i $𝒒u$ és també sincronisat.

Conjunts F-maximales

Siga $u$ un autovector esquerre en components positives sense divisores comunes en la matriu de adyacencia d'un grafo $G$ en vèrtiços ${𝒑}_1,{𝒑}_2,\dots ,{𝒑}_{𝒏}$. La $i$-ésima component $u_i$ del vector és cridat el pes del vèrtiç ${𝒑}_{𝒊}$ i denotat per $w{𝒑}_{𝒊}$. La suma dels pesos dels vèrtiços d'un subconjunt $D\subseteq G$ es denota per $w(D)$ i es diu el pes de $D$.

Donat un grafo $G$, un subconjunt $D\subseteq G$ es diu $𝑭$-maximal si $w(D)$ és maximal i $|Ds|=1$ per a alguna paraula $s\in {\Sigma }^{+}$.

Història i antecedents

El problema va ser inicialment plantejat per Adler, Goodwyn i Weiss en un artícul de la Societat nortamericana de Matemàtica en 1970. Est va ser enunciat explícitament per a grafos AGW que el seu màxim comú divisor de la llongitut de tots els seus cicles siga 1:

Per a un grafo aperiódico en grau exterior uniforme, deurà existir un coloreo d'arestes tal que per a certa seqüència, independent del vèrtiç inicial, seguir dita seqüència de colors sempre durà al mateix vèrtiç. Adler, Goodwyn & Weiss, 1970

Per més de 30 anys, molts matemàtics varen intentar resoldre este problema, i inclús es varen fer progressos per a casos particulars. Els dos més notables són:

Si un dígraf $D$ és finito fortament conexo aperiódico sense arestes múltiples, i $D$ conté un cicle simple de llongitut primera com a subconjunt propi de $D$, llavors $D$ posseïx un coloreo sincronisat. O' Brien, 1981

Si un dígraf $D$ és finito fortament conexo aperiódico (les arestes múltiples són permeses), i tot vèrtiç té el mateix grau exterior i interior $k$, llavors $D$ posseïx un coloreo sincronisat. Kari, 2003

No obstant, la conjectura es va mantindre sense provar fins al 2007 quan un matemàtic israelí, cridat Avraham Trahtman, finalment va conseguir provar-la i convertir-la en teorema. Trahtman era un científic de l'Unió Soviètica ans que tinguera que emigrar a Israel, a on va treballar com a guàrdia de seguritat.

Vore també

• Teorema dels quatre colors
• Coloració de grafos
• Grafo dirigit
• Anex:Glossari de teoria de grafos
• Teoria d'autómates

Referències

Bibliografia

• .
• .
• .
• .
• .
• .
• .