Grafik gücü - Graph power

Bir grafiğin karesi

Olarak grafik teorisi , matematik bir dalı, k, güç inci G ^k bir bir yönsüz grafik G aynı seti olan başka bir grafiktir köşeler , ancak zaman içinde iki köşe bitişik bir mesafe içinde G en çok olduğu  k . Grafikler yetkileri benzer terminoloji kullanarak ifade edilir üs numaralarının: G, ² olarak adlandırılan kare arasında G , G ³ olarak adlandırılan küp arasında G , vs.

Grafik güçleri , (kuvvetlerden farklı olarak) genellikle orijinal grafikten çok daha fazla köşeye sahip olan bir grafiğin ürünlerinden ayırt edilmelidir .

Özellikleri

Bir grafiğin çapı d ise , d' inci gücü grafiğin tamamıdır . Bir grafik ailesi klik genişliğini sınırlandırdıysa , o zaman herhangi bir sabit d için d -inci güçleri de öyle .

Boyama

Bir grafiğin karesi üzerindeki grafik renklendirme , kablosuz iletişim ağlarının katılımcılarına frekansları atamak için kullanılabilir, böylece hiçbir iki katılımcı ortak komşularından herhangi birinde birbirine müdahale etmez ve yüksek açısal çözünürlüğe sahip grafik çizimlerini bulmak için kullanılabilir .

Hem renk sayısı ve dejenere bir k bir inci güç düzlemsel grafik maksimum derecede Ô vardır dejenere bir olduğunu gösterir bağlanmış, hırslı boyama algoritması, bu çok renkli grafik renklendirmek için kullanılabilir. Düzlemsel bir grafiğin karesinin özel durumu için, Wegner 1977'de düzlemsel grafiğin karesinin kromatik sayısının en fazla olduğu ve kromatik sayının en fazla olduğu bilinmektedir . Daha genel olarak, dejenere d ve maksimum derece Δ olan herhangi bir grafik için , grafiğin karesinin dejenerasyonu O'dur ( d Δ), düzlemsel grafikler dışındaki pek çok seyrek grafik türü de kromatik sayısı Δ ile orantılı olan karelere sahiptir. . ${\displaystyle O(\Delta ^{\lfloor k/2\rfloor })}$${\displaystyle \max \left(\Delta +5,{\frac {3\Delta }{2}}+1\sağ)}$${\displaystyle {\frac {5\Delta }{3}}+O(1)}$

Maksimum derece Δ ​​olan düzlemsel olmayan bir grafiğin karesinin kromatik sayısı, en kötü durumda Δ ² ile orantılı olabilse de , bu durumda O(Δ ² /log Δ) ile sınırlanan yüksek çevreli grafikler için daha küçüktür .

Bir grafiğin karesini renklendirmek için gereken minimum renk sayısını belirlemek, düzlemsel durumda bile NP-zordur .

Hamiltoniklik

Her bağlı grafiğin küpü mutlaka bir Hamilton döngüsü içerir . Bağlı bir grafiğin karesinin Hamiltonyen olması zorunlu değildir ve karenin Hamiltonyen olup olmadığını belirlemek NP-tamdır . Yine de, Fleischner teoremine göre , 2-köşe bağlantılı bir grafiğin karesi her zaman Hamiltonyendir.

hesaplama karmaşıklığı

K bir grafiğin inci güç n köşe ve m kenarları zaman O (de hesaplanabilir mn bir performans) enine arama daha karmaşık algoritmalar kullanan tüm diğer köşe mesafeleri veya biraz daha hızlı belirlemek için her tepe noktasından başlayarak. Seçenek olarak ise, varsa bir bir olan komşuluk matrisi ana Diagonal'da sıfır olmayan girişleri, daha sonra, sıfır olmayan girişleri için modifiye edilmiş grafik, A ^k vermek bitişik olması matris k bu inşa takip eden grafiğin güç inci, k inci güçler, matris çarpımı için zamanın logaritmik bir faktörü içinde olan bir süre içinde gerçekleştirilebilir .

K ağaçların güçler inci giriş grafiğin boyutu lineer zamanda kabul edilebilir.

Bir grafik verildiğinde, bunun başka bir grafiğin karesi olup olmadığına karar vermek NP-tamamlıdır . Dahası, yine NP-tam bir grafiktir bir olup olmadığını belirlemek için K , belirli bir sayıda, başka bir grafik inci güç k  ≥ 2, ya da bir olup olmadığını k bir inci güç bipartit grafik için, k  > 2.

uyarılmış alt grafikler

Bir küp grafiğinin yarım karesi olarak K ₄

Yarı-kare a bipartit grafik G alt grafiği olan G ² arasında bipartition bir tarafında indüklediği G . Harita grafikler düzlemsel grafiklerin yarı kareleridir ve yarıya bölünmüş küp grafikler hiperküp grafiklerin yarım kareleridir .

Yaprak güçleri , ağacın yaprakları tarafından indüklenen ağaçların güçlerinin alt grafikleridir. Bir k -yaprak gücü, üssü k olan bir yaprak gücüdür .

Referanslar