Grafik yerleştirme - Graph embedding

Heawood grafik ve torus gömülü ilgili harita.

Gelen topolojik grafik teorisi , bir yerleştirme (aynı zamanda yazıldığından imbedding a) grafiğinde bir ilgili yüzeyi bir temsilidir ilgili olan noktaları ile ilişkili köşe ve basit yayların ( homeomorphic görüntüleri ile ilişkilidir) kenarları öyle ki: ${\görüntüleme stili G}$ ${\görüntüleme stili \Sigma }$${\görüntüleme stili G}$${\görüntüleme stili \Sigma }$${\görüntüleme stili \Sigma }$${\görüntüleme stili [0,1]}$

• bir kenarla ilişkili yayın uç noktaları, bir kenarla ilişkili uç köşeleriyle ilişkili noktalardır.${\görüntüleme stili e}$${\görüntüleme stili e,}$
• hiçbir yay diğer köşelerle ilişkili noktaları içermez,
• iki yay hiçbir zaman yaylardan birinin içinde olan bir noktada kesişmez.

İşte yüzeyi olan kompakt , bağlı - manifoldu . ${\görüntüleme stili 2}$

Gayri resmi olarak, bir grafiğin bir yüzeye gömülmesi, grafiğin, kenarlarının yalnızca uç noktalarında kesişebileceği şekilde yüzey üzerinde çizilmesidir. Herhangi bir sonlu grafiğin 3 boyutlu Öklid uzayına gömülebileceği iyi bilinmektedir . Bir düzlemsel grafik 2 boyutlu Öklid uzay gömülebilir biridir${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{2}.}$

Çoğu zaman, bir gömme , az önce açıklanan türden temsillerin bir denklik sınıfı ( homeomorfizmleri altında ) olarak kabul edilir . ${\görüntüleme stili \Sigma }$

Bazı yazarlar, kenarlar için kesişmeme koşulunu atlayarak "graf gömme" tanımının daha zayıf bir versiyonunu tanımlar. Bu tür bağlamlarda daha katı tanım, "geçişsiz grafik gömme" olarak tanımlanır.

Bu makale yalnızca grafik gömmenin katı tanımıyla ilgilidir. Daha zayıf tanım, " grafik çizimi " ve " çapraz sayı " makalelerinde tartışılmaktadır .

terminoloji

Bir grafik kapalı bir yüzeye gömülüyse, köşeleri ve kenarlarıyla ilişkili noktaların ve yayların birleşiminin tamamlayıcısı bir bölge (veya yüz ) ailesidir . Bir 2-hücreli gömme , hücresel gömme veya harita her yüz açık diske homeomorphic olduğu bir gömme olduğunu. Bir 2-hücresi gömme kapalı her yüzde bir kapak kapalı bir diske homeomorphic olduğu bir gömme olan. ${\görüntüleme stili G}$${\görüntüleme stili \Sigma }$${\görüntüleme stili G}$

Cinsi a grafik az tamsayıdır grafik bir yüzeyine gömülü şekildedir cinsi . Özellikle, düzlemsel bir grafiğin cinsi vardır , çünkü bir küre üzerinde kendinden kesişmeden çizilebilir. Yönlenemeyen cinsi a grafik az tamsayıdır grafiktir (yönlenemeyen) cinsi bir yönlenemeyen yüzeyi gömülü şekildedir . ${\görüntüleme stili n}$ ${\görüntüleme stili n}$${\görüntüleme stili 0}$${\görüntüleme stili n}$${\görüntüleme stili n}$

Euler cinsi bir grafiğin az tamsayıdır grafiktir (yönlendirilebilir) cinsi bir yönlendirilebilir yüzeyi gömülü şekildedir ya da (yönlenemeyen) cinsi bir yönlenemeyen yüzeyinde . Euler cinsi, yönlendirilemez cinsinden daha küçükse, bir grafik yönlendirilebilir şekilde basittir . ${\görüntüleme stili n}$${\görüntüleme stili n/2}$${\görüntüleme stili n}$

Maksimum cinsi a grafik tamsayıdır maksimumdur grafik şekildedir cell bir yönlendirilebilir yüzeyi gömülü cinsi . ${\görüntüleme stili n}$${\görüntüleme stili 2}$ ${\görüntüleme stili n}$

kombinatoryal gömme

Gömülü bir grafik , aynı tepe noktasına gelen kenarların döngüsel sıralarını benzersiz bir şekilde tanımlar . Tüm bu döngüsel sıraların kümesine döndürme sistemi denir . Aynı döndürme sistemine sahip gömmeler eşdeğer olarak kabul edilir ve gömmelerin karşılık gelen denklik sınıfına kombinatoryal gömme adı verilir ( önceki tanımı noktalar ve eğriler olarak ifade eden topolojik gömme teriminin aksine ). Bazen, döndürme sisteminin kendisine "kombinatoryal gömme" denir.

Gömülü bir grafik, aynı zamanda, gömmenin yüzlerinin sınırlarını oluşturan kenarların doğal döngüsel sıralarını da tanımlar. Bununla birlikte, bazı durumlarda bazı kenarlar bir yüz sınırı boyunca iki kez geçilebildiğinden, bu yüze dayalı sıraları işlemek daha az basittir. Örneğin, tek bir yüzü olan ağaçların gömülmesi için durum her zaman böyledir. Bu birleşimsel rahatsızlığın üstesinden gelmek için, her kenarın uzunlamasına iki "yarım kenar" veya "yan" olarak "bölündüğü" düşünülebilir. Bu kurala göre, tüm yüz sınırı geçişlerinde, her yarım kenar yalnızca bir kez geçilir ve aynı kenarın iki yarım kenarı her zaman zıt yönlerde geçilir.

Hücresel yerleştirmeler için diğer eşdeğer temsiller arasında, gömülü bir grafiğin köşeleri ve kenarları için topolojik disklerin birbirine yapıştırılmasıyla oluşturulan bir topolojik alan olan şerit grafiği ve her bir kenar için dört köşesi olan kenar renkli bir kübik grafik olan grafik kodlu harita yer alır. gömülü grafik.

hesaplama karmaşıklığı

Grafik cins bulma sorunudur NP-zor (bir olup olmadığını belirlemek problemi -vertex grafiğidir cins sahip olan NP-tam ). ${\görüntüleme stili n}$${\görüntüleme stili g}$

Aynı zamanda, grafik cinsi problemi sabit parametreli izlenebilirdir , yani polinom zaman algoritmalarının, bir grafiğin belirli bir sabit cinsin bir yüzeyine gömülüp gömülemeyeceğini kontrol etmek ve aynı zamanda gömmeyi bulmak için bilinir.

Bu konudaki ilk atılım 1979'da, zaman karmaşıklığı O ( n ^{O ( g )} ) algoritmalarının bağımsız olarak Yıllık ACM Hesaplama Teorisi Sempozyumu'na sunulduğu zaman gerçekleşti : biri I. Filotti ve GL Miller , diğeri ise John Reif tarafından. . Yaklaşımları oldukça farklıydı, ancak program komitesinin önerisi üzerine ortak bir bildiri sundular. Ancak Wendy Myrvold ve William Kocay , 2011 yılında Filotti , Miller ve Reif tarafından verilen algoritmanın yanlış olduğunu kanıtladılar.

1999'da sabit cins durumunun grafik boyutunda zaman doğrusal ve cinste çift ​​üstel olarak çözülebileceği bildirildi .

Grafiklerin daha yüksek boyutlu uzaylara gömülmesi

Herhangi bir sonlu grafiğin üç boyutlu bir uzaya gömülebileceği bilinmektedir.

Bunu yapmanın bir yöntemi, noktaları uzayda herhangi bir doğrunun üzerine yerleştirmek ve kenarları, her biri ayrı bir yarım düzlemde bulunan ve tüm yarım düzlemlerin ortak sınırı bu çizgiye sahip olacak şekilde eğriler olarak çizmektir. Kenarların yarım düzlemler üzerine çizildiği böyle bir gömme , grafiğin kitap gömmesi olarak adlandırılır . Bu metafor , bir kenarın çizildiği düzlemlerin her birinin bir kitap sayfası gibi olduğunu hayal etmekten gelir. Aslında aynı "sayfada" birkaç kenarın çizilebileceği gözlendi; Kitap kalınlığı grafiğinin bir çekme için gerekli halfplanes minimum sayısıdır.

Alternatif olarak, herhangi bir sonlu grafik, köşeleri genel pozisyona yerleştirerek, dört tanesi eş düzlemli olmayacak şekilde, üç boyutta düz çizgi kenarlarıyla çizilebilir . Örneğin, bu yerleştirme ile elde edilebilir I alanına (th köşe i , i ² , ı ³ arasında) moment eğrisi .

Bir grafiğin üç boyutlu uzaya, iki döngünün topolojik olarak bağlantılı olmadığı bir gömülmesine , bağlantısız bir gömülme denir . Bir grafiğin, Petersen ailesinin yedi grafiğinden birine minör olarak sahip olmaması durumunda, bağlantısız bir gömme vardır .

Galeri

• 

  Petersen, grafik ve yansıtmalı düzlemde gömülü ilgili harita. Çember üzerindeki karşıt noktalar, yönlendirilemez cins 1'in kapalı bir yüzeyini verecek şekilde tanımlanır.

• 

  Pappus grafik ve torus gömülü ilgili harita.

• 

  Derece 7 Klein grafiği ve cins 3'ün yönlendirilebilir bir yüzeyine gömülü ilişkili harita.

Ayrıca bakınız

• Gömme , diğer gömme türleri için
• Kitap kalınlığı
• grafik kalınlığı
• Çift bağlantılı kenar listesi , düzlemde gömülü bir grafiği temsil eden bir veri yapısı
• Düzenli harita (grafik teorisi)
• Bir düzlemsel grafiğin düz çizgi düzlemsel gömülmesinin her zaman mümkün olduğunu söyleyen Fáry teoremi .
• Üçgenleme (geometri)

Referanslar