圖的中心及中位

Abstract

圖論□中心及中位的觀念，起源於作業研究的選址問題。為了實際應用， 中心及中位問題有許多不同的變型。本論文從演算法的觀點來探討加權中 位、中心、切中心的結構性質 。考慮一個圖型 G=(V,E)，距離 d_G(u, v) 表示在圖 G中點 u到點v最短路徑的長度。如果點 u到其他點的最大距 離最小則稱點 u為中心點，所有中心點所成的集合為中心集 C(G) 。圖 G 中所有具有最小距離和的點所成的集合稱為圖 G的中位集 M(G) ，圖 G的 加權中位集 M_w(G)是指加權條件下的中位集。在連通圖 G中點 v的切數 c(v) 表示圖 G去掉 v後，落在不同分圖的點所成的有序數對的個數，圖 G中所有具最大切數的點所成的集合稱為切中心集 CC(G)$ 。第一章，介 紹本論文的背景和基本定義。第二章，証明連通強弦圖的加權中位集是一 個團；對找尋連通強弦圖的加權中位集給定項性演算法；對找尋區間圖和 塊狀圖的加權中位集得到線性演算法。第三章，對任何有向圖 G，可嵌入 一個有向圖 H中，使得 H的中心集和 G同構；對任何不含傳達者的 n點競 賽圖 T，可嵌入一個 m點競賽圖T'使得T'的王和 T同構且 m小於 n的兩倍 ；對任何具有正加權的圖 G，可嵌入一個具有正加權的圖 H中，使 H的加 權中位集和 G同構。第四章，我們得到任何圖 G的切中心集的一個輪廓和 找尋切中心集 線性演算法 。第五章，我們從G1和G2的結構討論G1和G2的 一些運算後圖型的中心 和中位集。 Consider a graph G=(V,E). The distance d_G(u,v) from vertex u tortex v in G is the length of a shortest path from u to v. Artex u is a central vertex if the maximum distance from u toother vertex is minimum. The center C(G) of a graph G is the setall central vertices. The median M(G) of G is the set ofrtices with a minimum distance sum. The w-median M_w(G) of G ise weightd case of the median. The cutting number c(v) of artex in a connected graph G is the number of pairs of verticesand w such that u and w are in different components of G-v. Thetting center CC(G) of a graph G is the set of all vertices withximum c(v). In Chapter 2, we show that the w- median of a connectedrongly chordal graph is a clique. We then give a polynomial timegorithm for finding the weighted median of a connected stronglyordal graph. A linear time algorithm for the weighted medianoblem in interval graphs and block graphs. In Section 3, we embed an arbitrary digraph G into anothergraph H such that H_{C(H)} is isomorphic to G. We prove that antrivial n-tournament T is contained in an m-tournament, with< 2n, whose kings are the vertices of T if T contains noansmitter. We show that for every graph G with a positive weightnction w there exists a supergraph H with positive weightnction w' such that w(v)=w'(v) for all vertices in G and whose-median subgraph is isomorphic to G. In Chapter 4, we give a configuration for the cutting centeran arbitrary graph and a linear time algorithm for finding thetting center of a graph. In Chapter 5, we consider the centers and the medians of someeration for graphs G_1 and G_2.