text: 在數學的一個分支圖論中，一個無向圖的"k"次冪"G""k"指的是另一個有相同頂點集的圖，但在G中所有距離小於"k"的頂點在該圖中是相鄰的。圖的次冪常用數的次冪相關術語來表示："G"2被稱為"G"的平方，"G"3被稱為立方，以此類推。圖的次冪應該與圖本身的乘積區別開來，圖的乘積通常比原圖有更多的頂點。屬性.如果一個圖的直徑是d，那麼它的d次冪就是完全圖。如果一個圖族具有有界的團寬，那麼對於任意固定的d，它的d次冪也具有有界的團寬。著色.圖平方的著色可以用來為無線通訊網路的參與者分配頻率，使兩個參與者互動時不受任何共同鄰居的干擾，並可以在圖繪製時找到角解析度高的圖。最大度為Δ的平面圖的"k"次冪其著色數和簡併度均為formula_1，其中簡併度表明顏色貪婪演算法可利用這麼多顏色給圖著色。 考慮一個平面圖平方的特例，Wegner在1977年推算出平面圖平方的最大著色數為formula_2而目前更普遍的最大著色數為formula_3。 更一般地說，對任何簡併度為"d"和最大度為Δ的圖，圖平方的簡併度為"O"("d"Δ)，因此許多不是平面圖的稀疏圖其平方的著色數與Δ成比例。儘管最大度為Δ的非平面圖平方的著色數最壞情況是與Δ2成比例，對於高圍長的圖來說其往往更小，通常在這種情況下量級為O(Δ2/log Δ)。確定為圖平方著色需要的顏色數是NP困難，即使在平面圖中也是如此。哈密頓性.每個連通圖的立方必然包含一個哈密頓迴圈。一個連通圖的平方不一定滿足哈密頓性，它是否滿足哈密頓性是NP完備的。然而，根據弗萊施納定理，2-頂點連通圖的平方總是滿足哈密頓性的。計算複雜度.一個有"n" 個頂點和"m"條邊的圖的"k"次冪可以透過從每個頂點開始執行廣度優先搜尋來確定到所有其他頂點的距離，從而在時間O("mn")中計算出來。如果"A"是一個圖的鄰接矩陣，修改主對角線的非零元素，那麼"Ak"的非零項給出了圖的"k"次冪的鄰接矩陣，由此可以在矩陣乘法時間的對數因子內構造出第k次冪的時間量。樹的"k"次冪可以在輸入圖的尺寸上用時間線性的方式識別。給定一個圖，判斷它是否是另一個圖的平方是NP完全的。此外，對於給定的數字k≥2，確定一個圖是否是另一個圖的k次冪，或是二分圖的k次冪，是NP完全的。匯出子圖.二分圖G的半二分是G"平分為兩部分的一部分。平面圖的半二分是地圖圖，超立方圖的半二分是半立方圖。葉冪是由樹的葉匯出的樹的次冪子圖。"k"的葉冪。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 圖的次冪
metadata: https://zh.wikipedia.org/wiki?curid=6633784