加權圖之和、中位點及位移; Sums, Medians and Displacements of Weighted Graphs

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/7796

Title:	加權圖之和、中位點及位移;Sums, Medians and Displacements of Weighted Graphs
Authors:	張原禎;Y-Z Chang
Contributors:	數學研究所
Keywords:	加權圖;和;中位點;位移;weighted graph;sum;median;displacement
Date:	2001-07-11
Issue Date:	2009-09-22 11:05:39 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	在這篇論文，我們探討連通加權圖之和、中位點及位移，而且我們考慮的圖形都是在有限的情況下。假設是一個圖形，如果它的邊有一正實數的加權(也就是存在一個函數對到正實數)，以來表示這個邊的加權，這種圖形我們稱為加權圖，我們以來表示它。在連通加權圖上的路徑，這條路徑的加權定義為 = 。對於加權圖上的兩點，這兩點的加權距離定義為，這個最小值是在所有連接的路徑中取的。對於加權圖上的一點，這一點的加權和我們定義為 = ，而這個加權圖的和我們將它定義為。如果加權圖上的一點v滿足，則我們稱v為此一加權圖的中位點。如果加權圖的每個邊的加權都是1時，則在加權圖中，假設是的一個重排函數，則的加權位移我們定義為。這個圖形的加權和我們定義為，這個最大值是在V(G)的所有重排函數的加權位移取的。在這篇論文，我們將探討： 1. 中位點在連通加權圖的位置。 2. 有n個點及最大degree為k之連通圖的和之範圍。 3. 加權圖的位移跟和之間的關係。 In this paper, we consider sums, medians and displacements of connected, weighted graphs. All graphs considered in this paper are finite graphs. Suppose that is a graph with positive weights on edges, (i.e, there exists a weight function to R ). w(e) is called the weight on an edge . Then is called a weighted graph. Suppose that is a connected, weighted graph. For a path in the weight of is defined by = . For two vertices in the weight distance between x and y is defined by , where the minimum is taken over all paths P which join x and y. For a vertex x the weight sum of x is = . The weight sum of a graph is . If a vertex v satisfies , then v is called a weight median of . If for every edge in then Suppose is a permutation of . Then the weight displacement of is defined by . The weight displacement of is defined by , where the maximum is taken over all permutations of . In this paper, we consider 1. The locations of weight medians of a connected, weighted graph. 2. The range of if is a connected graph of order n and with maximum degree. 3. The relationship between the weight sum and the weight displacement of a connected graph.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...