Grafik işlemleri - Graph operations
Grafik işlemleri , ilk grafiklerden yeni grafikler üretir . Aşağıdaki ana kategorilere ayrılabilirler.
Tekli işlemler
Tekli işlemler, tek bir başlangıç grafiğinden yeni bir grafik oluşturur.
Temel işlemler
Temel işlemler veya düzenleme işlemleri, aynı zamanda grafik düzenleme işlemleri, birleştirme ve köşeler, bölme, örneğin bir köşe ekleme veya silme veya bir kenarının, basit bir yerel değişimi ile bir ilk baştaki bir yeni grafik oluşturmak kenar daralma , vb grafik düzenleme mesafe bir çift arasında grafikler, bir grafiği diğerine dönüştürmek için gereken minimum temel işlem sayısıdır.
Gelişmiş işlemler
Gelişmiş işlemler, aşağıdakiler gibi karmaşık değişikliklerle ilkinden yeni bir grafik oluşturur:
- transpoze grafiği ;
- tamamlayıcı grafik ;
- çizgi grafiği ;
- küçük grafik ;
- grafiğin yeniden yazılması ;
- grafiğin gücü ;
- ikili grafik ;
- medial grafik ;
- bölüm grafiği ;
- Y-Δ dönüşümü ;
- Mycielskian .
İkili işlemler
İkili işlemler, G 1 = ( V 1 , E 1 ) ve G 2 = ( V 2 , E 2 ) gibi iki başlangıç grafiğinden yeni bir grafik oluşturur :
- grafik birliği: G 1 ∪ G 2 . İki tanım var. En yaygın olanı, grafiklerin ayrık birleşiminde , birleşmenin ayrık olduğu varsayılır. Daha az yaygın olarak ( matematikteki genel birleşim tanımıyla daha tutarlı olsa da ) iki grafiğin birleşimi grafik olarak tanımlanır ( V 1 ∪ V 2 , E 1 ∪ E 2 ) .
- grafik kesişimi: G 1 ∩ G 2 = ( V 1 ∩ V 2 , E 1 ∩ E 2 ) ;
- grafik birleştirme: ilk grafiğin köşelerini ikinci grafiğin köşelerine bağlayan tüm kenarları içeren grafik. Değişmeli bir işlemdir (etiketsiz grafikler için);
-
köşe kümelerinin kartezyen çarpımına dayalı grafik ürünleri :
- kartezyen grafik ürünü : değişmeli ve ilişkisel bir işlemdir (etiketsiz grafikler için),
- sözlükbilimsel grafik ürünü (veya grafik bileşimi): ilişkisel (etiketsiz grafikler için) ve değişmeli olmayan işlemdir,
- güçlü grafik ürünü : değişmeli ve ilişkisel bir işlemdir (etiketsiz grafikler için),
- tensör grafik ürünü (veya doğrudan grafik ürünü, kategorik grafik ürünü, kardinal grafik ürünü, Kronecker grafik ürünü): değişmeli ve ilişkisel bir işlemdir (etiketsiz grafikler için),
- zig-zag grafik çarpımı ;
- diğer ürünlere dayalı grafik ürünü:
- köklü grafik ürünü : ilişkisel bir işlemdir (etiketsiz ancak köklü grafikler için),
- korona grafik ürünü : değişmeyen bir işlemdir;
-
seri-paralel grafik bileşimi :
- paralel grafik bileşimi: değişmeli bir işlemdir (etiketsiz grafikler için),
- seri grafik bileşimi: değişmeli olmayan bir işlemdir,
- kaynak grafik bileşimi: değişmeli bir işlemdir (etiketsiz grafikler için);
- Hajós inşaatı .
Notlar
- ^ Bondy, JA; Murty, USR (2008). Çizge Teorisi . Matematikte Lisansüstü Metinler. Springer. s. 29. ISBN 978-1-84628-969-9 .
- ^ Bir b c Harary, F . Çizge Teorisi . Okuma, MA: Addison-Wesley, 1994.
- ^ Reingold, O .; Vadhan, S .; Wigderson, A. (2002). "Entropi dalgaları, zig-zag grafik ürünü ve yeni sabit derece genişleticiler". Matematik Annals . 155 (1): 157–187. arXiv : matematik / 0406038 . doi : 10.2307 / 3062153 . JSTOR 3062153 . MR 1888797 .
- ^ Frucht, Robert ; Harary, Frank (1970). "İki grafiğin koronasında". Aequationes Mathematicae . 4 : 322–324. doi : 10.1007 / bf01844162 . hdl : 2027.42 / 44326 .
