Ver el código de «W. T. Tutte»

{{Ficha de persona
}} '''William Thomas Tutte''' (14 de mayo de 1917 - 2 de mayo de 2002) fue un descifrador de [[Criptoanálisis|códigos]] y matemático inglés y canadiense. Durante la [[Segunda Guerra Mundial]], hizo un avance brillante y fundamental en el [[criptoanálisis del cifrado de Lorenz]], un importante sistema de encriptación de la [[Alemania nazi]] que se utilizó para comunicaciones de alto secreto dentro del Alto Mando de la [[Wehrmacht]]. La naturaleza estratégica de la información de alto nivel obtenida a partir del avance crucial de Tutte, específicamente en el descifrado masivo de los mensajes codificados con el sistema de Lorenz, contribuyó en gran medida, y quizás incluso de manera decisiva, a la derrota de la Alemania nazi.<ref name="Hinsley 1993 8">{{Harvsp|Hinsley|Stripp|1993|p=8}}</ref><ref name="Brzezinski 2005 18">{{Harvsp|Brzezinski|2005|p=18}}</ref> También obtuvo resultados matemáticos significativos, incluido el trabajo de base en los campos de la [[teoría de grafos]] y la de [[matroide]]s.<ref name="frs">{{Harvsp|Younger|2012}}</ref><ref name="MacTutorBiog">{{Harvsp|O'Connor|Robertson|2003}}</ref>

La investigación de Tutte en el campo de la teoría de grafos demostró ser de notable importancia. En un momento en que esta disciplina era todavía un tema incipiente, comenzó el estudio de los [[matroide]]s y los convirtió en una teoría ampliando el trabajo que [[Hassler Whitney]] había desarrollado por primera vez a mediados de la década de 1930.<ref>{{Cita web|url=http://www.math.washington.edu/~morrow/336_09/papers/Will.pdf|título=Matroids|fechaacceso=2014-10-16|autor=Johnson|nombre=Will}}</ref> Aunque las contribuciones de Tutte han influido en la teoría de grafos moderna y muchos de sus teoremas se han utilizado para seguir avanzando en el campo, la mayor parte de su terminología no estaba de acuerdo con su uso convencional y, por lo tanto, no es utilizada por los teóricos de grafos en la actualidad.<ref name="Hobbs 2004 322">{{Cita publicación|url=http://www.ams.org/notices/200403/mem-tutte.pdf|título=William T. Tutte (1917–2002)|apellidos=Hobbs|nombre=Arthur M.|enlaceautor=Arthur Hobbs (mathematician)|apellidos2=James G. Oxley|enlaceautor2=James Oxley|fecha=March 2004|publicación=[[Notices of the American Mathematical Society]]|volumen=51|número=3|página=322}}</ref> "Tutte hizo avanzar la teoría de grafos a partir de un tema contenido en un único texto (el de [[Dénes Kőnig|D. Kőnig]]) hacia su estado actual trabajando de forma extremadamente activa".<ref name="Hobbs 2004 322" />

== Primeros años ==
Tutte nació en [[Newmarket]], en Suffolk. Era el último hijo de William John Tutte (1873-1944), jardinero, y de la [[ama de llaves]] Annie Newell (1881-1956). Ambos padres trabajaban en la propiedad de los establos de Fitzroy House, donde Tutte nació.<ref name="MacTutorBiog" /> La familia pasó algún tiempo en [[Buckinghamshire]], el Condado de Durham y Yorkshire antes de regresar a Newmarket, donde asistió en la localidad de [[Cheveley]] a una escuela primaria regida por la [[Iglesia de Inglaterra]].<ref name="frs">{{Harvsp|Younger|2012}}</ref> En 1927, con diez años de edad, obtuvo una [[beca]] para asistir a la Escuela secundaria para niños de Cambridge y su Condado, donde ingresó en 1928.

En 1935 ganó una beca para estudiar ciencias naturales en el [[Trinity College (Cambridge)|Trinity College de Cambridge]], donde se especializó en [[química]] y se graduó con honores de primera clase en 1938.<ref name="frs">{{Harvsp|Younger|2012}}</ref> Continuó con la [[Fisicoquímica|química física]] como estudiante graduado, pero se decidió por el estudio de las matemáticas a finales de 1940.<ref name="frs" /> Como estudiante, junto con tres de sus amigos, se convirtió en uno de los primeros en resolver el problema de la [[cuadratura del cuadrado]] y el primero en resolver el problema sin un subrectángulo cuadrado. Juntos, los cuatro crearon el [[Alias|seudónimo]] de ''[[Blanche Descartes]]'', bajo el que Tutte publicó ocasionalmente algunos de sus trabajos durante años.<ref>{{Obra citada|título=The Story of Blanche Descartes|apellidos=Smith|nombre=Cedric A. B.|fecha=March 2003|pub-periódica=The Mathematical Gazette|número=508|volumen=87|páginas=23–33|apellidos2=Abbott|nombre2=Steve|ISSN=0025-5572|DOI=10.1017/S0025557200172067}}</ref>

== Segunda Guerra Mundial ==
[[File:SZ42-6-wheels-lightened.jpg|right|380px|thumbnail|Las máquinas Lorenz SZ tenían 12 ruedas, cada una con un número diferente de levas (o "pasadores").
{|class="wikitable" | border=1 | style="margin: 10px auto 1px auto; font-size:90%;"
|-
! Número de rueda
|1||2||3||4||5||6||7||8||9||10||11||12
|-
! Nombre de la rueda<br />en Bletchley Park<ref name = "GRoT11B6">{{Harvnb|Good|Michie|Timms|1945|p=6}} in ''1. Introduction: German Tunny''</ref>
| style="text-align:center;"| <math>\psi_1</math>
| style="text-align:center;"| <math>\psi_2</math>
| style="text-align:center;"| <math>\psi_3</math>
| style="text-align:center;"| <math>\psi_4</math>
| style="text-align:center;"| <math>\psi_5</math>
| style="text-align:center;"| <math>\mu</math>37
| style="text-align:center;"| <math>\mu</math>61
| style="text-align:center;"| <math>\chi_1</math>
| style="text-align:center;"| <math>\chi_2</math>
| style="text-align:center;"| <math>\chi_3</math>
| style="text-align:center;"| <math>\chi_4</math>
| style="text-align:center;"| <math>\chi_5</math>
|-
! Número de levas (pasadores)
|43||47||51||53||59||37||61||41||31||29||26||23
|}
]]

Poco después del estallido de la [[Segunda Guerra Mundial]], el tutor de Tutte, Patrick Duff, lo recomendó para trabajar durante la guerra en [[Government Communications Headquarters|Escuela de Códigos y Cifrados del Gobierno]] en [[Bletchley Park]] (BP). Fue entrevistado y enviado a un curso de capacitación en Londres antes de ir a Bletchley Park, donde se unió a la Sección de Investigación. Al principio, trabajó en el cifrado [[Boris Hagelin|Hagelin]], que estaba siendo utilizado por la Marina italiana. Esta era una máquina de [[Máquina de rotores|cifrado de rotores]] que estaba disponible comercialmente, por lo que se conocía la mecánica del cifrado, y para descifrar los mensajes solo requería averiguar cómo estaba configurada la máquina.<ref>{{Harvsp|Tutte|2006|pp=352–353}}</ref>

En el verano de 1941 fue transferido para trabajar en un proyecto llamado ''Fish''. La información de inteligencia había revelado que los alemanes llamaron a los sistemas de transmisión mediante teleimpresoras inalámbricas ''"Sägefisch"'' ([[pez]] sierra). Esto llevó a los británicos a denominar [[Fish (criptología)|''Fish'']] al sistema de cifrado alemán. El apodo ''Tunny'' (atún) se usó para el primer sistema de enlace que no empleaba el código Morse, y posteriormente se usó para las máquinas Lorenz SZ y para las comunicaciones que cifraban.<ref>{{Cita libro|título=Codebreakers: the inside story of Bletchley Park|editor=F.H. Hinsley|editor2=Alan Stripp|año=2001|apellidos=Hinsley|nombre=F.H.|chapter-url=https://books.google.com/books?id=j1MC2d2LPAcC&pg=PA141|capítulo=An Introduction to Fish|páginas=141–148|isbn=0-19-280132-5}}</ref>

Las comunicaciones telegráficas utilizaban el [[Código Baudot|Alfabeto Telegráfico Internacional n.º 2]] (ITA2) de 5 [[bit]]s. No se sabía nada sobre el mecanismo de cifrado, aparte de que los mensajes estaban precedidos por un [[Criptoanálisis|indicador]] de 12 letras, lo que implicaba una máquina de cifrado de rotor de 12 ruedas. El primer paso, por lo tanto, tenía que ser diagnosticar la máquina estableciendo la estructura lógica y por lo tanto su funcionamiento. Tutte desempeñó un papel fundamental en este logro, y no fue hasta poco antes de la victoria aliada en Europa en 1945 cuando Bletchley Park pudo disponer de una máquina de [[Código Lorenz|cifrado ''Tunny'' Lorenz]].<ref name="Sale">{{Obra citada|título=The Lorenz Cipher and how Bletchley Park broke it|apellidos=Sale|nombre=Tony|enlaceautor=Anthony Sale|url=http://www.codesandciphers.org.uk/lorenz/fish.htm|fechaacceso=2010-10-21}}</ref> Los avances de Tutte llevaron finalmente al descifrado masivo de mensajes cifrados con el sistema ''Tunny'' entre el Alto Mando Alemán [[Oberkommando der Wehrmacht|(OKW)]] en Berlín y sus mandos militares en toda la Europa ocupada y contribuyeron, quizás de manera decisiva, a la derrota de Alemania.<ref name="Hinsley 1993 8">{{Harvsp|Hinsley|Stripp|1993|p=8}}</ref><ref name="Brzezinski 2005 18">{{Harvsp|Brzezinski|2005|p=18}}</ref>

=== Diagnóstico de la máquina de cifrado ===
El 31 de agosto de 1941 se enviaron [[Código Lorenz|dos versiones del mismo mensaje]] utilizando claves idénticas, lo que constituía una situación de vulnerabilidad denominada en criptografía "[[Criptoanálisis|profundidad]]". Esto permitió a [[John Tiltman]], el veterano y notablemente talentoso criptoanalista de Bletchley Park, deducir que se trataba de un cifrado de [[Gilbert Vernam|Vernam]], que usa la función [[Disyunción exclusiva|disyunción exclusiva (XOR)]] (simbolizada por "⊕"), y extraer los dos mensajes y, por lo tanto, obtener la clave de oscurecimiento. Después de un período infructuoso durante el cual los criptoanalistas de la Sección de Investigación intentaron averiguar cómo funcionaba la máquina ''Tunny'', esta y algunas otras claves fueron entregadas a Tutte, a quien se le pidió que "viera qué podía hacer con ellas".<ref>{{Harvsp|Tutte|2006|p=354}}</ref>

[[Archivo:Lorenz-SZ42-2.jpg|derecha|miniaturadeimagen|280px|La máquina de Lorenz SZ42 sin sus cubiertas (Museo de [[Bletchley Park]])]]

En su curso de capacitación, a Tutte se le había enseñado la técnica del [[Método Kasiski|examen de Kasiski]], consistente en escribir una clave en papel cuadriculado, comenzando una nueva fila después de un número definido de caracteres que se sospechaba que era la frecuencia de repetición de la clave.<ref>{{Harvsp|Bauer|2006|p=375}}</ref> Si este número era correcto, las columnas de la matriz mostrarían más repeticiones de secuencias de caracteres que el azar por sí solo. Tutte sabía que los indicadores de la máquina ''Tunny'' usaban 25 letras (excluyendo la J) para 11 de las posiciones, pero solo 23 letras para la otra. Por lo tanto, probó la técnica de Kasiski en el primer impulso de los caracteres clave, utilizando una repetición de 25 × 23 = 575. No observó un gran número de repeticiones de columna con este período, pero sí observó el fenómeno en diagonal. Por lo tanto, volvió a intentarlo con 574, que mostró repeticiones en las columnas. Reconociendo que los [[Número primo|factores primos]] de este número son 2, 7 y 41, lo intentó de nuevo con un período de 41 y "obtuvo un [[rectángulo]] de puntos y cruces que estaba repleto de repeticiones".<ref>{{Harvsp|Tutte|2006|pp=356–357}}</ref>

Estaba claro, sin embargo, que el primer impulso de la tecla era más complicado que el producido por una sola rueda de 41 impulsos de tecla. Tutte llamó a este componente de la clave <math>\chi_1</math> (''chi''<sub>1</sub>). Supuso que había otro componente, que aplicaba una disyunción exclusiva, que no siempre cambiaba con cada nuevo carácter, y que este era el producto de una rueda que llamó <math>\psi_1</math> (''psi1'')<sub>.</sub> Lo mismo se aplicó para cada uno de los cinco impulsos {{Nowrap|(<math>\chi_1 \chi_2 \chi_3 \chi_4 \chi_5</math> and <math>\psi_1 \psi_2 \psi_3 \psi_4 \psi_5</math>).}} Entonces, para un solo carácter, la clave '''K''' completa constaba de dos componentes:<math display="block">K = \chi \oplus \psi</math>En Bletchley Park, los impulsos de marca se representaban con '''x''' y los impulsos de espacio con '''•''' .{{Refn|En una terminología más reciente, cada impulso se denominaría "[[bit]]" con una marca como 1 binario y un espacio como 0 binario. La cinta de papel perforada tenía un agujero como marca y ningún agujero como espacio.|group=nota}} Por ejemplo, la letra "H" se codificaría como '''••x•x'''.<ref>{{Harvsp|Copeland|2006|pp=348, 349}}</ref> La deducción de Tutte de los componentes ''chi'' y ''psi'' fue posible por el hecho de que era más probable que los puntos fueran seguidos por puntos, y que las cruces tenían más probabilidades de ser seguidas por cruces. Esto fue producto de una debilidad en la configuración de clave alemana, que luego eliminaron. Una vez que Tutte hizo este avance, el resto de la Sección de Investigación se unió para estudiar los otros impulsos, y se estableció que las cinco ruedas ''chi'' avanzaban con cada nuevo carácter y que las cinco ruedas ''psi'' se movían juntas bajo el control de dos ruedas ''mu'' o "motor". Durante los siguientes dos meses, Tutte y otros miembros de la Sección de Investigación trabajaron en la estructura lógica completa de la máquina, con su conjunto de ruedas con levas que podrían estar en una posición (elevada) que agregaba una '''x''' al flujo de caracteres del teclado, o en la posición alternativa que se agregaba en '''•'''.<ref>{{Harvsp|Tutte|2006|p=357}}</ref>

Deducir el funcionamiento de la máquina ''Tunny'' de esta manera fue un logro criptoanalítico verdaderamente notable que, en la mención del nombramiento de Tutte como Oficial de la [[Orden de Canadá]], se describió como "una de las mayores hazañas intelectuales de la Segunda Guerra Mundial".<ref name="MacTutorBiog" />

=== Método estadístico de Tutte ===
Para descifrar un mensaje de ''Tunny'' se requería conocimiento no solo del funcionamiento lógico de la máquina, sino también de las posiciones de inicio de cada rotor para el mensaje en particular. Se estaba buscando un proceso que manipulara el texto cifrado o la clave para producir una distribución de frecuencia de caracteres que se apartara de la uniformidad que el proceso de cifrado pretendía lograr. Mientras estaba adscrito a la Sección de Investigación en julio de 1942, [[Alan Turing]] descubrió que la combinación XOR de los valores de caracteres sucesivos en un flujo de texto cifrado y clave enfatizaba cualquier desviación de una distribución uniforme. La corriente resultante (simbolizada por la letra griega "delta" '''Δ''') se denominó diferencia porque XOR es lo mismo que la resta de módulo 2.

La razón por la que esto proporcionó una forma de acceder a ''Tunny'' fue que, aunque la distribución de frecuencia de los caracteres en el texto cifrado no podía distinguirse de un flujo aleatorio, no ocurría lo mismo con una versión del texto cifrado a partir de la cual se había extraído el elemento ''chi'' de la clave. Este fue el caso porque donde el texto sin formato contenía un carácter repetido y las ruedas ''psi'' no se habían movido, el carácter ''psi'' diferenciado (<math>\Delta\psi</math>) sería el carácter nulo (' <span style="font-size:140%;">'''/'''</span> ' en Bletchley Park). Cuando se usa XOR con cualquier carácter, este carácter no tiene efecto. Los caracteres repetidos en el texto sin formato eran más frecuentes debido a las características del alemán (los pares de letras repetidas EE, TT, LL y SS son relativamente comunes),<ref>{{Obra citada|título=The Black Chamber|apellidos=Singh|nombre=Simon|enlaceautor=Simon Singh|url=http://www.simonsingh.net/The_Black_Chamber/hintsandtips.html|fechaacceso=2012-04-28}}</ref> y porque los telegrafistas repetían con frecuencia los caracteres de cambio de cifras y letras,<ref>[[Max Newman|Newman]] c. 1944 p. 387</ref> dado que su pérdida en un mensaje telegráfico ordinario podría dar lugar a un galimatías.<ref>{{Harvsp|Carter|2004|p=3}}</ref>

Citando el Informe General sobre ''Tunny'':

{{cita|Turing introdujo el principio de que la clave diferenciada en uno, ahora llamada '''ΔΚ''', podría generar información que no se puede obtener de la clave ordinaria. Este principio '''Δ''' iba a ser la base fundamental de casi todos los métodos estadísticos de desvelado y ajuste de ruedas.<ref name="GRoT11B6" />}}

Tutte aprovechó esta amplificación de la falta de uniformidad en los valores diferenciados {{Refn|Por esta razón, el método 1 + 2 de Tutte a veces se denomina método de la "doble delta".|group=nota}} y en noviembre de 1942 había hallado una forma de descubrir los puntos de partida de las ruedas de la máquina ''Tunny'' que se conoció como el "Método estadístico".<ref>{{Harvsp|Tutte|1998|pp=7–8}}</ref> La esencia de este método era encontrar la configuración inicial del componente ''chi'' de la clave probando exhaustivamente todas las posiciones de su combinación con el texto cifrado y buscando evidencia de la falta de uniformidad que reflejaba las características del texto original sin formato.<ref>{{Harvsp|Good|Michie|Timms|1945|pp=321–322}} in ''44. Hand Statistical Methods: Setting – Statistical Methods''</ref><ref>{{Harvsp|Budiansky|2006|pp=58–59}}</ref> Debido a que cualquier carácter repetido en el texto sin formato siempre generaría '''•''', y de manera similar <math>\Delta\psi_1 \oplus \Delta\psi_2</math> generaría '''•''' cada vez que las ruedas ''psi'' no se movieran, y aproximadamente la mitad de las veces cuando lo hicieran, lo que suponía alrededor del 70% en general.

Además de aplicar la diferenciación a los caracteres completos de 5 bits del código ITA2, Tutte la aplicó a los impulsos individuales (bits).{{Refn|Los cinco impulsos o bits de los caracteres codificados a veces se denominan cinco niveles.|group=nota}} Es necesario establecer la configuración actual de la leva de la rueda ''chi'' para permitir que se genere la secuencia relevante de caracteres de las ruedas ''chi''. Era totalmente impracticable generar los 22 millones de caracteres de las cinco ruedas ''chi'', por lo que inicialmente se limitó a 41 × 31 = 1271 de las dos primeras. Después de explicar sus hallazgos a [[Max Newman]], este último recibió el trabajo de desarrollar un enfoque automatizado para comparar el texto cifrado y la clave con el fin de buscar desviaciones de la aleatoriedad. La primera máquina se denominó [[Heath Robinson (máquina de descifrar códigos)|Heath Robinson]], pero la [[Colossus|computadora Colossus]], mucho más rápida, desarrollada por [[Tommy Flowers]] y usando algoritmos escritos por Tutte y sus colegas, pronto se hizo cargo de descifrar los códigos.<ref>{{Harvsp|Copeland|2011}}</ref><ref>{{Cita web|url=https://uwaterloo.ca/combinatorics-and-optimization/about/professor-william-t-tutte/biography-professor-tutte#bletchley|título=Biography of Professor Tutte|fechaacceso=2018-06-24|autor=Younger|nombre=Dan|fecha=August 2002|sitioweb=CMS Notes|fechaarchivo=19 de agosto de 2019|urlarchivo=https://web.archive.org/web/20190819115149/https://uwaterloo.ca/combinatorics-and-optimization/about/professor-william-t-tutte/biography-professor-tutte#bletchley|deadurl=yes}}</ref><ref>{{Obra citada|título=Lorenz: Breaking Hitler's top secret code at Bletchley Park|apellidos=Roberts|nombre=Jerry|enlaceautor=Jerry Roberts|editorial=The History Press|lugar=Stroud, Gloucestershire|ISBN=978-0-7509-7885-9|year=2017}}</ref>

== Doctorado y carrera ==
A finales de 1945, Tutte reanudó sus estudios en [[Universidad de Cambridge|Cambridge]], ahora como estudiante graduado en matemáticas. Publicó algunos trabajos que había comenzado mucho antes, uno ahora famoso que caracteriza qué grafos tienen una coincidencia perfecta y otro que construye un grafo no hamiltoniano.

Completó su doctorado en matemáticas por la Universidad de Cambridge en 1948 bajo la supervisión de [[Shaun Wylie]], quien también había trabajado en Bletchley Park en la máquina ''Tunny''. Su tesis ''An Algebraic Theory of Graphs'' se consideró innovadora y trataba sobre el tema conocido más tarde como teoría de matroides.<ref name="uwaterloo.ca"/>

El mismo año, invitado por [[Harold Scott MacDonald Coxeter]], aceptó un puesto en la [[Universidad de Toronto]]. En 1962, se trasladó a la [[Universidad de Waterloo]] en [[Waterloo (Ontario)|Waterloo]], Ontario, donde permaneció el resto de su carrera académica. Se retiró oficialmente en 1985, pero permaneció activo como profesor emérito. Tutte fue fundamental para ayudar a fundar el Departamento de Combinatoria y Optimización en la Universidad de Waterloo.

Su carrera matemática se concentró en [[Combinatoria|la combinatoria]], especialmente la [[teoría de grafos]], campo en el que se le atribuye haber ayudado a crear su forma moderna, y la [[Matroide|teoría de matroides]], a la que hizo profundas contribuciones. Un colega lo describió como "el matemático líder en combinatoria durante tres décadas". Fue editor en jefe del ''Journal of Combinatorial Theory'' hasta que se retiró de Waterloo en 1985.<ref name="uwaterloo.ca"/> También formó parte de los consejos editoriales de varias otras revistas de investigación matemática.

== Contribuciones en investigación ==
El trabajo de Tutte en teoría de [[Teoría de grafos|grafos]] incluye la estructura de espacios de [[espacio ciclo|ciclos]] y de [[espacio de corte|corte]], el tamaño de las [[Coincidencia máxima|coincidencias máximas]] y la existencia de [[Factor K (teoría de grafos)|k-factores]] en grafos, y grafos [[Camino hamiltoniano|hamiltonianos]] y no hamiltonianos.<ref name="uwaterloo.ca">{{Cita web|url=https://uwaterloo.ca/combinatorics-and-optimization/about/professor-william-t-tutte/biography-professor-tutte|título=Biography of Professor Tutte &#124; Combinatorics and Optimization &#124; University of Waterloo|fechaacceso=11 May 2017|urlarchivo=https://web.archive.org/web/20190819115149/https://uwaterloo.ca/combinatorics-and-optimization/about/professor-william-t-tutte/biography-professor-tutte|fechaarchivo=2019-08-19}}</ref> Refutó la [[conjetura de Tait]], sobre la hamiltonicidad de los [[Grafo poliédrico|grafos poliédricos]], utilizando la construcción conocida como [[fragmento de Tutte]]. La prueba final del teorema de los [[Teorema de los cuatro colores|cuatro colores]] hizo uso de su trabajo anterior. El polinomio gráfico que llamó "dicromato" se ha vuelto famoso e influyente con el nombre de [[polinomio de Tutte]] y sirve como prototipo de invariantes combinatorios que son universales para todos los invariantes que satisfacen una ley de reducción específica.

Realizó los primeros avances importantes en la [[Matroide|teoría de matroides]] en su tesis doctoral de Cambridge de 1948, que formó la base de una importante secuencia de artículos publicados durante las siguientes dos décadas. El trabajo de Tutte en teoría de grafos y teoría de matroides ha tenido una profunda influencia en el desarrollo tanto del contenido como de la dirección de estos dos campos.<ref name="Hobbs 2004 322"/> En la teoría de matroides, descubrió el altamente sofisticado [[Teorema de homotopía de Tutte|teorema de la homotopía]] y fundó los estudios de [[Matroide|grupos de cadenas]] y [[Matroide regular|matroides regulares]], sobre los que demostró profundos resultados.

Además, desarrolló un algoritmo para determinar si un [[matroide binario]] determinado es un [[matroide gráfico]]. El algoritmo hace uso del hecho de que un grafo plano es simplemente un grafo cuyo circuito-matroide, el dual de su [[matroide dual|enlace-matroide]], es gráfico.<ref>W.T Tutte. An algorithm for determining whether a given binary matroid is graphic, ''Proceedings of the London Mathematical Society'', '''11'''(1960)905–917</ref>

Tutte escribió un artículo titulado ''Cómo dibujar un grafo'' en el que demostró que cualquier cara en un grafo de 3 conexiones está encerrada por un [[ciclo periférico]]. Usando este hecho, desarrolló una prueba alternativa para mostrar que cada gráfico de Kuratowski no es plano al demostrar que ''K''<sub>5</sub> y ''K''<sub>3,3</sub> tienen cada uno tres ciclos periféricos distintos con una arista común. Además de usar ciclos periféricos para demostrar que los gráficos de Kuratowski no son planos, también demostró que cada grafo simple de 3 conexiones se puede dibujar con todas sus caras convexas e ideó un algoritmo que construye el dibujo del plano resolviendo un sistema lineal. El dibujo resultante se conoce como [[embebido de Tutte]]. El algoritmo de Tutte hace uso de las asignaciones [[Coordenadas baricéntricas (n-simplex)|baricéntricas]] de los circuitos periféricos de un grafo simple de 3 conexiones.<ref>W.T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, 13(3):743–768, 1963.</ref>

Los hallazgos publicados en este documento han demostrado ser de gran importancia porque los algoritmos que desarrolló Tutte se han convertido en métodos populares de dibujo de gráficos planos. Una de las razones por las que el embebido de Tutte es popular es que los cálculos necesarios que realizan sus algoritmos son simples y garantizan una correspondencia uno a uno de un grafo y su embebido en el [[Bidimensional|plano euclídeo]], lo que es importante al parametrizar una malla tridimensional al plano en el modelado geométrico. "El teorema de Tutte es la base para las soluciones de otros problemas de grafos por computadora, como las [[Morphing|secuencias de imágenes]]".<ref>Steven J. Gortle; Craig Gotsman; Dylan Thurston. "Discrete One-Forms on Meshes and Applications to 3D Mesh Parameterization", ''Computer Aided Geometric Design'', 23(2006)83–112</ref>

Fue el principal responsable de desarrollar la teoría de la [[enumeración de grafos]] planos, que tiene estrechos vínculos con los polinomios cromáticos y dicromáticos. Este trabajo involucró algunas técnicas altamente innovadoras de su propia invención, que requerían una destreza de manipulación considerable en el manejo de series de potencias (cuyos coeficientes cuentan tipos de grafos apropiados) y las funciones que surgen como sus sumas, así como destreza geométrica para extraer estas series de potencias de la situación teórica de los grafos.<ref>[[Crispin Nash-Williams|C. St. J. A. Nash-Williams]], A Note on Some of Professor Tutte's Mathematical Work, Graph Theory and Related Topics (eds. J.A Bondy and U. S. R Murty), Academic Press, New York, 1979, p. xxvii.</ref>

Tutte resumió su trabajo en ''Selected Papers of WT Tutte'', 1979, y en ''Graph Theory as I have know it'', 1998.<ref name="uwaterloo.ca"/>

== Reconocimientos ==
El trabajo de Tutte en la Segunda Guerra Mundial y posteriormente en combinatoria le valió varios puestos, honores y premios:

* 1958, miembro de la Royal Society of Canada (FRSC);
* 1971, Premio Jeffery-Williams de la Sociedad Matemática Canadiense ;
* 1975, Medalla Henry Marshall Tory de la Royal Society of Canada;
* 1977, se llevó a cabo una conferencia sobre teoría de grafos y temas relacionados en la [[Universidad de Waterloo]] en su honor con motivo de su sexagésimo cumpleaños;
* 1982, Premio Isaak-Walton-Killam del Consejo de Canadá ;
* 1987, [[miembro de la Royal Society]] (FRS);
* 1990-1996, primer presidente del Instituto de Combinatoria y sus Aplicaciones;<ref>{{Cita web|url=http://www.theica.org/|título=The Institute of Combinatorics & Its Applications|fechaacceso=2013-09-28|editorial=ICA|urlarchivo=https://web.archive.org/web/20131002064646/http://www.theica.org/|fechaarchivo=2013-10-02}}</ref>
* 1998, nombrado director honorario del Centro de Investigación Criptográfica Aplicada de la Universidad de Waterloo;<ref>{{Cita web|url=http://www.adm.uwaterloo.ca/infonews/release/1998/107%20Tutte%20honored%20by%20new%20Centre%20for%20Applied%20Cryptographic%20Research,%20June%2017,%201998.html|título=Tutte honoured by cryptographic centre|fechaacceso=2013-09-28|editorial=University of Waterloo|fechaarchivo=4 de marzo de 2016|urlarchivo=https://web.archive.org/web/20160304084343/http://www.adm.uwaterloo.ca/infonews/release/1998/107%20Tutte%20honored%20by%20new%20Centre%20for%20Applied%20Cryptographic%20Research,%20June%2017,%201998.html|deadurl=yes}}</ref>
* 2001, Oficial de la [[Orden de Canadá]] (OC);
* 2001, premio CRM-Fields-PIMS.
* 2016, Salón de la Fama de la Región de Waterloo<ref>{{Cita noticia|url=https://uwaterloo.ca/combinatorics-and-optimization/news/bill-tutte-inducted-waterloo-region-hall-fame|título=Bill Tutte inducted into the Waterloo Region Hall of Fame &#124; Combinatorics and Optimization|periódico=Combinatorics and Optimization|fecha=2016-04-25}}</ref>
* 2017, nombre de la carretera "William Tutte Way" de Waterloo<ref>{{Cita web|url=https://uwaterloo.ca/stories/mathematics-professor-and-wartime-code-breaker-honoured|título=Mathematics professor and wartime code-breaker honoured|fecha=12 May 2017}}</ref>

También desempeñó el cargo de bibliotecario de la [[Real Sociedad Astronómica]] de Canadá en 1959-1960. El asteroide [[Anexo:Asteroides (14001)–(15000)|14989 Tutte]] (1997 UB7) recibió su nombre.<ref>{{Cita web|url=http://www.rasc.ca/content/asteroid-14989|título=Asteroid (14989) Tutte|fechaacceso=2014-09-25|fecha=2011-06-14|editorial=Royal Astronomical Society of Canada|urlarchivo=https://web.archive.org/web/20150104181311/http://www.rasc.ca/content/asteroid-14989|fechaarchivo=2015-01-04}}</ref>

Debido al trabajo de Tutte en Bletchley Park, el Establecimiento de Seguridad de las Comunicaciones de Canadá nombró una organización interna destinada a promover la investigación en criptología, el Instituto Tutte de Matemáticas y Computación (TIMC), en su honor en 2011.<ref>{{Cita noticia|apellidos=Freeze|nombre=Colin|título=Top secret institute comes out of the shadows to recruit top talent|url=https://www.theglobeandmail.com/news/national/top-secret-institute-comes-out-of-the-shadows-to-recruit-top-talent/article2154310/|fechaacceso=2014-09-25|periódico=The Globe and Mail|fecha=2011-09-07|ubicación=Toronto}}</ref>

En septiembre de 2014 recibió un homenaje en su ciudad natal de Newmarket, Inglaterra, con la inauguración de una escultura, después de que un periódico local iniciara una campaña para honrar su memoria.<ref>{{Cita web|url=http://billtuttememorial.org.uk/the-memorial/|título=The Bill Tutte Memorial|fechaacceso=2014-12-13|editorial=Bill Tutte Memorial Fund}}</ref>

Bletchley Park en Milton Keynes celebró el trabajo de Tutte con una exposición ''Bill Tutte: Mathematician + Codebreaker'' de mayo de 2017 a 2019, precedida el 14 de mayo de 2017 por conferencias sobre su vida y obra durante el Simposio del Centenario de Bill Tutte.<ref>{{Cita web|url=https://uwaterloo.ca/combinatorics-and-optimization/news/bill-tutte-centenary-symposium-bletchley-park-0|título=The Bill Tutte Centenary Symposium (Bletchley Park)|fecha=2017-04-11}}</ref><ref>{{Cita web|url=https://www.bletchleypark.org.uk/news/codebreaker-bill-tutte-to-be-celebrated-in-centenary-exhibition|título=Bletchley Park &#124; News — New exhibition to tell story of Bill Tutte|fechaacceso=11 May 2017|urlarchivo=https://web.archive.org/web/20170606221506/https://bletchleypark.org.uk/news/codebreaker-bill-tutte-to-be-celebrated-in-centenary-exhibition|fechaarchivo=2017-06-06}}</ref>

== Vida personal y muerte ==
Además de los beneficios profesionales de trabajar en la nueva [[Universidad de Waterloo]], el entorno más rural del condado de Waterloo atrajo a Bill y su esposa Dorothea. Compraron una casa en el pueblo cercano de West Montrose, Ontario, donde disfrutaron de caminatas, pasaron tiempo en su jardín en el Grand River y permitieron que otros disfrutaran del hermoso paisaje de su propiedad.

También tenían un amplio conocimiento de todas las aves de su jardín. Dorothea, una activa alfarera, también era una gran excursionista y Bill organizaba excursiones de senderismo. Incluso cerca del final de su vida, todavía era un asiduo caminante.<ref name="Hobbs 2004 322"/><ref>{{Cita web|url=http://www-gap.dcs.st-and.ac.uk/~history/Obits2/Tutte_Telegraph.html|título=Bill Tutte|fechaacceso=21 May 2013|editorial=Telegraph Group Limited|urlarchivo=https://web.archive.org/web/20130927151741/http://www-gap.dcs.st-and.ac.uk/~history/Obits2/Tutte_Telegraph.html|fechaarchivo=2013-09-27}}</ref> Después de la muerte de su esposa en 1994, se mudó de nuevo a Newmarket (Suffolk), pero luego regresó a Waterloo en 2000, donde murió dos años después.<ref>{{Obra citada|título=Obituary: William Tutte|apellidos=van der Vat|nombre=Dan|enlaceautor=Dan van der Vat|url=https://www.theguardian.com/news/2002/may/10/guardianobituaries.obituaries|fechaacceso=2013-04-28|fecha=10 May 2002|lugar=London|pub-periódica=The Guardian}}</ref> Está enterrado en el cementerio West Montrose United.<ref name="uwaterloo.ca"/>

== Publicaciones seleccionadas ==

=== Libros ===

* {{Obra citada|título=Connectivity in graphs|apellidos=Tutte|nombre=W. T.|editorial=University of Toronto Press|lugar=Toronto, Ontario|serie=Mathematical expositions|volumen=15|ref=none|year=1966}}
* {{Obra citada|título=Introduction to the theory of matroids|apellidos=Tutte|nombre=W. T.|editorial=RAND Corporation report R-446-PR|lugar=Santa Monica, Calif.|ref=none|year=1966}}. Also {{Obra citada|título=Introduction to the theory of matroids|apellidos=Tutte|nombre=W. T.|editorial=American Elsevier Publishing Company|lugar=New York|serie=Modern analytic and computational methods in science and mathematics|volumen=37|ISBN=978-0-444-00096-5|ref=none|year=1971}}
* {{Obra citada|título=Recent progress in combinatorics. Proceedings of the third Waterloo conference on combinatorics, May 1968|editorial=Academic Press|lugar=New York-London|páginas=xiv+347|editor=Tutte|nombre-editor=W. T.|ISBN=978-0-12-705150-5|ref=none|year=1969}}
* {{Obra citada|título=Selected papers of W.T. Tutte, Vols. I, II.|apellidos=Tutte|nombre=W. T.|editorial=[[Charles Babbage Research Centre]], St. Pierre, Manitoba, Canada|lugar=Winnipeg, Manitoba|páginas=xxi+879|editor=McCarthy|nombre-editor=D.|editor2=Stanton|ref=none|year=1979|editor2-first=R. G.}}
** Volume I: {{ISBN|978-0-969-07781-7}}
** Volume II: {{ISBN|978-0-969-07782-4}}
* {{Obra citada|título=Graph theory|apellidos=Tutte|nombre=W. T.|url=https://archive.org/details/graphtheory0000tutt|editorial=Addison-Wesley Publishing Company|lugar=Menlo Park, California|serie=Encyclopedia of mathematics and its applications|volumen=21|ISBN=978-0-201-13520-6|ref=none|year=1984}} Reprinted by Cambridge University Press 2001, {{ISBN|978-0-521-79489-3}}
* {{Obra citada|título=Graph theory as I have known it|apellidos=Tutte|nombre=W. T.|editorial=Clarendon Press|lugar=Oxford|serie=Oxford lecture series in mathematics and its applications|volumen=11|ISBN=978-0-19-850251-7|ref=none|year=1998}} Reprinted 2012, {{ISBN|978-0-19-966055-1}}

=== Artículos ===

* {{Cita publicación|título=The Dissection of Rectangles into Squares|url=https://archive.org/details/sim_duke-mathematical-journal_1940_7/page/312|apellidos=Brooks|nombre=R. L.|enlaceautor=Rowland L. Brooks|apellidos2=Smith|nombre2=C. A. B.|enlaceautor2=Cedric Smith (statistician)|publicación=Duke Math. J.|volumen=7|páginas=312–340|doi=10.1215/s0012-7094-40-00718-9|ref=none|apellidos3=Stone|nombre3=A. H.|enlaceautor3=Arthur Harold Stone|apellidos4=Tutte|nombre4=W. T.|año=1940}}

== Véase también ==
* [[Geometría sistólica]]

== Notas ==
<references group="nota"/>

== Referencias ==
{{listaref|2}}

== Bibliografía ==
* {{Obra citada|título=The Tiltman Break|apellidos=Bauer|nombre=Friedrich L.|enlaceautor=Friedrich L. Bauer|year=2006}} Appendix 5 in {{Harvsp|Copeland|2006|pp=370–377}}
* {{Obra citada|título=Marian Rejewski, 1905-1980: living with the Enigma secret|apellidos=Brzezinski|nombre=Zbigniew|enlaceautor=Zbigniew Brzezinski|editorial=Bydgoszcz City Council|lugar=Bydgoszcz, Poland|capítulo=The Unknown Victors|páginas=15–18|editor=Ciechanowski|nombre-editor=Stanisław|ISBN=83-7208-117-4|year=2005}}
* {{Obra citada|título=Colossus: The Secrets of Bletchley Park's Codebreaking Computers|editorial=Oxford University Press|lugar=Oxford|editor=Copeland|nombre-editor=B. Jack|enlace-editor=Jack Copeland|ISBN=978-0-19-284055-4|year=2006}}
* {{Obra citada|título=Colossus and the Dawning of the Computer Age|apellidos=Copeland|nombre=B. Jack|enlaceautor=Jack Copeland|year=2011}} in {{Harvsp|Erskine|Smith|2011|pp=305–327}}
* {{Obra citada|título=The Bletchley Park Codebreakers|año-original=2001|editorial=Biteback Publishing Ltd|editor=Erskine|nombre-editor=Ralph|editor2=Smith|enlace-editor2=Michael Smith (newspaper reporter)|ISBN=978-1-84954-078-0|year=2011|editor2-first=Michael}} Updated and extended version of ''Action This Day: From Breaking of the Enigma Code to the Birth of the Modern Computer'' Bantam Press 2001
* {{Obra citada|título=General Report on Tunny: With Emphasis on Statistical Methods|apellidos=Good|nombre=Jack|enlaceautor=I. J. Good|url=http://www.alanturing.net/turing_archive/archive/index/tunnyreportindex.html|fechaacceso=2010-09-15|apellidos2=Michie|nombre2=Donald|apellidos3=Timms|nombre3=Geoffrey|enlaceautor2=Donald Michie|id=UK Public Record Office HW 25/4 and HW 25/5|year=1945}} That version is a facsimile copy, but there is a transcript of much of this document in '.pdf' format at: {{Obra citada|título=Part of the 'General Report on Tunny', the Newmanry History, formatted by Tony Sale|apellidos=Sale|nombre=Tony|enlaceautor=Anthony Sale|url=http://www.codesandciphers.org.uk/documents/newman/newman.pdf|fechaacceso=2010-09-20|year=2001}}, and a web transcript of Part 1 at: {{Obra citada|título=General Report on Tunny With Emphasis on Statistical Methods|apellidos=Ellsbury|nombre=Graham|url=http://www.ellsbury.com/tunny/tunny-001.htm|fechaacceso=2010-11-03}}
* {{Obra citada|título=Enigma and Fish|apellidos=Good|nombre=Jack|enlaceautor=I. J. Good|year=1993}} in {{Harvsp|Hinsley|Stripp|1993|pp=149–166}}
* {{Obra citada|título=Codebreakers: The inside story of Bletchley Park|año-original=1992|editorial=Oxford University Press|lugar=Oxford|editor=Hinsley|nombre-editor=F. H.|enlace-editor=Harry Hinsley|editor2=Stripp|ISBN=978-0-19-280132-6|year=1993|editor2-first=Alan}}
* {{Obra citada|título=MacTutor Biography: William Thomas Tutte|apellidos=O'Connor|nombre=J. J.|url=http://www-history.mcs.st-and.ac.uk/Biographies/Tutte.html|fechaacceso=2013-04-28|editorial=University of St Andrews|apellidos2=Robertson|nombre2=E. F.|enlaceautor2=Edmund F. Robertson|year=2003}}
* {{Obra citada|título=Fish and I|apellidos=Tutte|nombre=W. T.|enlaceautor=W. T. Tutte|url=http://www.usna.edu/Users/math/wdj/_files/documents/papers/cryptoday/tutte_fish.pdf|fechaacceso=2012-04-07|fecha=1998-06-19}} Transcript of a lecture given by Prof. Tutte at the [[Universidad de Waterloo|University of Waterloo]]
* {{Obra citada|título=My Work at Bletchley Park|apellidos=Tutte|nombre=William T.|enlaceautor=W. T. Tutte|year=2006}} Appendix 4 in {{Harvsp|Copeland|2006|pp=352–369}}
* {{Obra citada|título=Code-cracking machine returned to life|apellidos=Ward|nombre=Mark|url=https://www.bbc.co.uk/news/technology-13566878|fechaacceso=2013-04-28|fecha=27 May 2011|pub-periódica=BBC News}}
* {{Obra citada|título=Biographical Memoirs of Fellows of the Royal Society: William Thomas Tutte. 14 May 1917 – 2 May 2002|apellidos=Younger|nombre=D. H.|url=http://rsbm.royalsocietypublishing.org/content/58/283|fechaacceso=2013-04-28|editorial=The Royal Society|pub-periódica=Biographical Memoirs of Fellows of the Royal Society|volumen=58|páginas=283–297|DOI=10.1098/rsbm.2012.0036|year=2012}}

== Enlaces externos ==
* [http://math.uwaterloo.ca/combinatorics-and-optimization/about/professor-william-t-tutte Profesor William T. Tutte]
* {{MathGenealogy|id=15096}}  
* [http://www.math.binghamton.edu/zaslav/Oldcourses/580.S04/tutte.html William Tutte, 84, matemático y descifrador, muere] – Obituario de ''[[The New York Times]]''
* [https://www.theguardian.com/obituaries/story/0,3604,712971,00.html William Tutte: el autor intelectual anónimo de las matemáticas] – Obituario de ''[[The Guardian]]''
* [http://www.crm.umontreal.ca/prix/recipients.html#2001 Premio CRM-Fields-PIMS – 2001 – William T. Tutte]
* [http://www.fields.utoronto.ca/audio/01-02/CRM-Fields/tutte/ "60 años en las redes": una conferencia (grabación de audio) impartida en el Fields Institute el 25 de octubre de 2001 para marcar la recepción del premio CRM-Fields 2001]
* [https://web.archive.org/web/20020415122807/http://www.math.niu.edu/~rusin/known-math/97/tutte La refutación de Tutte de la conjetura de Tait]
* [https://web.archive.org/web/20121226233428/http://www.telegraph.co.uk/history/world-war-two/9765962/Bletchleys-forgotten-heroes.html "Héroes olvidados de Bletchley"], Ian Douglas, ''[[The Daily Telegraph]]'', 25 de diciembre de 2012
*{{citation | last1 = Murty | first1 = U. S. R. | author-link1 = U. S. R. Murty | title = Dedication: Professor W.T. Tutte | journal = [[Journal of Combinatorial Theory]] | series = Series B | volume = 92 | issue = 2 | pages = 191–192 | year = 2004 | doi = 10.1016/j.jctb.2004.08.002}}.
*{{citation | last1 = Younger | first1 = D. H. | title = Dedication: Professor W.T. Tutte | journal = [[Journal of Combinatorial Theory]] | series = Series B | volume = 92 | issue = 2 | pages = 193–198 | year = 2004 | doi = 10.1016/j.jctb.2004.09.002}}.
* [https://www.cse-cst.gc.ca/en/culture-and-community/research El Instituto Tutte de Investigación en Matemáticas y Ciencias de la Computación]

{{NF|1917|2002|Tutte, William}}
[[Categoría:Miembros de la Royal Society of Canada]]
[[Categoría:Miembros de la Royal Society]]
[[Categoría:Oficiales de la Orden de Canadá]]
[[Categoría:Profesores de la Universidad de Waterloo]]
[[Categoría:Profesores de la Universidad de Toronto]]
[[Categoría:Teóricos de grafos]]
[[Categoría:Matemáticos del siglo XX]]
[[Categoría:Matemáticos de Canadá]]
[[Categoría:Matemáticos de Inglaterra]]
[[Categoría:Criptógrafos del Reino Unido]]
[[Categoría:Personal de Bletchley Park]]
[[Categoría:Alumnado del Trinity College (Cambridge)]]