圖的點排序

Vertex Ranking of Graphs

鄧乃心(Nancy N.H. Teng)

指導教授 ： 張鎮華

國立臺灣大學/理學院/數學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.00739

摘要

圖的點排序是將圖 G 上的每一個點 v 給定一個適當的自然數 f(v) 作為排序，使得對於排序相同的相異兩點 u 和 v ，圖形 G 上每一條 u 到 v 的路徑中，都存在一點 w 有著較高的排序，意即f(w)>f(u)=f(v) 。在所有點排序中，最大排序最小者，我們稱之為一個最佳點排序。而在最佳點排序中，最大排序定為圖 G 的點排序數 r(G)。一個點排序問題就是要找出圖 G 的點排序數 r(G) 。相同的，圖的邊排序只是將排序的對象由點換成邊，而排序完以後有著相對應的性質。

前人已經知道部分圖形的點排序數，像是路徑、圈。也有一些演算法可以找到樹圖的最佳點排序，或最佳邊排序。在這篇論文裡，
我們嘗試簡化樹圖的點排序演算法之證明，並且提出一個塊狀圖的點排序演算法，另外還有部分仙人掌圖的結果。

關鍵字

排序

並列摘要

A vertex ranking of a graph G is a mapping f from V(G) to the set of all natural numbers such that for any path between two distinct vertices u and v with f(u)=f(v) there is a vertex w in the path with f(w)>f(u). In this definition, we call the value f(v) the rank of the vertex v. A vertex ranking of G is optimal if the largest rank assigned is the smallest in value among all vertex rankings of G. The vertex ranking number r(G) is the
largest rank used in an optimal vertex ranking. The vertex ranking problem is to determine the vertex ranking number r(G) of a given graph G. The edge ranking problem can be defined analogously except that the mapping f is now from the edge set to the set of all nature numbers.

In the literature, vertex ranking numbers are determined for paths, cycles and cographs. There are also polynomial-time algorithms for the vertex ranking problem and the edge ranking problem [2,9,4]on trees. In this thesis, we
give a simple proof for the correctness of the algorithm for the vertex ranking on trees. We also propose an algorithm which gives an optimal vertex ranking of a block graph. Finally, we establish results for the vertex ranking problem on cacti.

並列關鍵字

ranking

參考文獻

Optimal node ranking of trees, Inform. Process. Lett. 28(1988), 225-229.

edge ranking problem of trees and graphs, Discrete Appl. Math. 30(1991), 43-52.

[3] T. W. Lam and F. L. Yue, Edge ranking of graphs is

hard, Discrete Appl. Math. 85(1998), 71-86.

Zhao, Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Discrete Appl. Math. 154(2006), 2402-2410.