Konvexní vkládání - Convex embedding
v teorie geometrických grafů, a konvexní vkládání grafu je vložení grafu do a Euklidovský prostor, přičemž jeho vrcholy jsou reprezentovány jako body a jeho hrany jako úsečky, takže všechny vrcholy mimo zadanou podmnožinu patří do konvexní obal jejich sousedů. Přesněji řečeno, pokud je podmnožina vrcholů grafu, pak konvexní -embedding vloží graf takovým způsobem, že každý vrchol buď patří nebo je umístěn v konvexním trupu sousedů. Konvexní vložení do -dimenzionální euklidovský prostor je prý v obecná pozice pokud každá podmnožina jeho vrcholů se rozprostírá v podprostoru dimenze .[1]
Konvexní embeddings byly představeny W. T. Tutte v roce 1963. Tutte ukázal, že pokud je vnější obličej a rovinný graf je fixován na tvar daného konvexního mnohoúhelníku v rovině a zbývající vrcholy jsou umístěny řešením a soustava lineárních rovnic popisující chování ideálních pružin na okrajích grafu, bude výsledkem konvexní - shromáždění. Silnější je, že každá tvář vložení vytvořená tímto způsobem bude konvexní mnohoúhelník, jehož výsledkem bude a konvexní kresba grafu.[2]
Kromě rovinnosti získaly konvexní vložky zájem o výsledek z roku 1988 Nati Linial, László Lovász, a Avi Wigderson že graf je k-vertex-connected právě když má -dimenzionální konvexní - pro některé shromažďování v obecné poloze z jeho vrcholů, a že pokud ano k-vertex-propojené, pak může být zabudováno takové vložení polynomiální čas výběrem být libovolnou podmnožinou vrcholy a řešení Tuttova systému lineárních rovnic.[1]
Jednorozměrné konvexní vložení (v obecné poloze) pro zadanou sadu dvou vrcholů jsou ekvivalentní bipolární orientace daného grafu.[1]
Reference
- ^ A b C Linial, N.; Lovász, L.; Wigderson, A. (1988), „Gumičky, konvexní vložení a připojení grafů“, Combinatorica, 8 (1): 91–102, doi:10.1007 / BF02122557, PAN 0951998
- ^ Tutte, W. T. (1963), „Jak nakreslit graf“, Proceedings of the London Mathematical Society, 13: 743–767, doi:10,1112 / plms / s3-13.1.743, PAN 0158387.