Embegut de Tutte

En dibuix de grafos i en teoria de grafos geomètrica, una incrustació de Tutte o incrustació baricéntrica d'un grafo pla 3-vèrtiços-conectat simple és un incrustat de llínees rectes sense creus en les propietats de que la cara exterior és un polígon convexo i de que cada vèrtiç interior està en el centroide (o baricentre) de les posicions dels seus veïns. Si el polígon exterior és fix, esta condició en els vèrtiços interiors determina la seua posició únicament com a solució a un sistema d'equacions llineals. Resoldre les equacions geomètricament produïx una incrustació plana. La teorema del resort de Tutte, provat per W. T. Tutte, 1963, establix que esta solució única sempre està lliure de creus, i com una condició més forta, que cada cara de la incrustació plana resultant és convexa. Es diu la teorema del resort perque dita incrustació es pot trobar com la posició d'equilibri per a un sistema de resorts que representa les vores del grafo.

Eixemple

Embebido de Tutte del grafo d'una gaveta. Els quatre vèrtiços exteriors estan fixos en els cantons d'un Quadrat unitat i cada vèrtiç restant està en el promig de les posicions dels seus veïns

Siga G el grafo d'una gaveta, i (seleccionant una de les seues cares cuadriláteras com a cara exterior) es fixen els quatre vèrtiços de la cara exterior en els quatre cantons d'un quadrat unitat, els punts les coordenades dels quals x i i són les quatre combinacions de zero i un.

Llavors, si els quatre vèrtiços restants es coloquen en els quatre punts les coordenades dels quals x i i són combinacions d'1/3 i 2/3, com en la figura, el resultat serà un incrustat de Tutte. Perque en cada vèrtiç interior v de l'incrustat, i per a cada una de les dos coordenades, els tres veïns de v tenen valors de coordenades que són iguals a v, menors en 1/3 , i majors en 1/3; el promig d'estos valors és el mateix que el valor de la pròpia coordenada de v.

Sistema d'equacions llineals

La condició de que un vèrtiç v estiga en el promig de les posicions dels seus veïns pot expressar-se com dos equació de primer grau, una per a la coordenada x de v i un atre per a la coordenada i de v. Per a un grafo en n vèrtiços, dels quals h estan fixos en la cara exterior, hi ha dos equacions per a cada vèrtiç interior i també dos incògnites (les coordenades) per a cada vèrtiç interior. Per lo tant, açò dona un sistema d'equacions llineals en 2(n − h) equacions i 2(n − h) incògnites, la solució de les quals és un incrustat de Tutte. Com va mostrar Tutte (1963), per a grafos plans conectats en 3 vèrtiços, este sistema no és degenerado. Per lo tant, té una solució única i (en la cara exterior fixa) el grafo té un incrustat de Tutte únic. Este incrustat es pot trobar en temps polinòmic resolent el sistema d'equacions, per eixemple, usant l'eliminació de Gauss-Jordan.