圖之距離和

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

Title:	圖之距離和
Authors:	林強;商珍綾
Contributors:	中央大學數學系
Keywords:	數學類
Date:	2008-09-01
Issue Date:	2012-10-01 15:09:46 (UTC+8)
Publisher:	行政院國家科學委員會
Abstract:	本計畫的目的在探討圖形（graph）中的一點到其他點的距離和之一些相關問題. 定義. 若x為一連通圖(connected graph)的一點，則x之距離和（status）為 Σ∈=)(),()(GVyyxdxs. 第一年計畫 1. 圖的點距離和（Status of a graph）定義. 一連通圖之點距離和（status）為任一點到其他點距離和之最小值. 問題1. 在圖的點數及其他參數如：最大度數（maximum degree）或直徑（diameter）固定下, 何種圖形有最大的點距離和？何種圖形有最小的點距離和？ 2. 圖形的距離和數列（Status sequence of a graph）定義. 一連通圖所有的點的距離和（status）以遞增形式排出的數列，稱為此圖的距離和數列（Status sequence）. 定義. 令T為一樹(tree). (1)若T的任何相異兩點yx,都有)()(ysxs≠的性質，則稱T為距離和---1對1 （status-injective）. (2)若T的相異兩點yx,只要,)()(ysxs=yx,就都是端點（endvertices）, 則稱T為弱距離和---1對1（weakly status-injective）. (3)若T中任意的相異兩個非端點（non-endvertices）yx,, 皆有的性質，則稱T為內部距離和---1對1（status-injective）. )()(ysxs≠ 根據定義，距離和---1對1的樹是弱距離和---1對1。弱距離和---1對1的樹是內部距離和---1對1. 問題2. 距離和---1對1（或甚至弱距離和---1對1，內部距離和---1對1）的樹是否可由距離和數列唯一決定？第二年計畫 1. 嵌入問題（Embedding problem）定義. 一圖G之距離和---中心（median）為圖G限制到{})()()(:)(GVxxstsGVt∈∀≤∈ 的子圖. P.J. Slater (Medians of arbitrary graphs, J. Graph Theory vol. 4, 389 – 392 , 1980) 證得：任意圖皆可成為另一圖的距離和---中心（median）. H.-Y. Lee 與 G. J. Chang (Medians of graphs and kings of tournaments, Taiwanese J. of Mathematics, Vol. 1, 103-110, 1997) 把這結果推廣到點有加權的圖形. 我們將探討問題1. 把上面embedding的結果推廣到邊與點都有加權的圖形，加權可以考慮正實數，亦可限制為正整數. 2. 圖之位移（Displacements of graphs）定義. 設G為一連通圖. (1)若 ψ為之一重排（permutation），則 G對ψ之位移（displacement）為 )(GV Σ∈=)()(x) ,()(GVxxdGDψψ. (2) G之位移（displacement）定義為之所有的重排ψ的位移的最大值. )(GV)(GDψ 問題2. 探討連通圖的點距離和（status）與位移（displacement）的關係. ; The purpose of this project is to investigate the sum of the distances between a vertex and the other vertices in a graph. Definition. Let G be a connected graph. The status of a vertex x in G, is denoted and defined by Σ∈=)(),()(GVyyxdxs. First year project 1. Status of a graph Definition. The status of a connected graph G is the minimum of all statuses of vertices in G. We will investigate the following problem. Problem 1. Under the conditions that the order is fixed and some other parameter (for example, maximum degree, diameter) is also fixed, which graphs have the maximum status (respectively, the minimum status)? 2. Status sequence of a graph Definition. Let G be a connected graph. The status sequence of G is the list of statuses of all vertices of G. We (C. Lin, J.-L. Shang, An uniqueness result for the status sequence of spiders,整理中) can prove that in the family of trees any spider is uniquely determined by its status sequence. We want to find more trees which are uniquely determined by their own status sequences. Definition. Let T be a tree. (1) T is status-injective if s(x) ≠ s(y) whenever x and y are distinct vertices in T. (2) T is weakly status-injective if x and y are endvertices of T whenever x and y are distinct vertices in T with s(x) = s(y). (3) T is internally status-injective if s(x) ≠ s(y) whenever x and y are distinct non-endvertices of T. By the definitions, a status-injective tree is weakly status-injective, and a weakly status-injective tree is internally status-injective. We will investigate the following problem. Problem 2. Is every status-injective tree or even every weakly status-injective tree or every internally status-injective tree uniquely determined by its status sequence in the family of trees? Second year project 1. Embedding problem Definition. The median of a connected graph G is defined to be the subgraph of G induced by the set (i.e. the set of all vertices with smallest statuses). {)()()(:)(GVxxstsGVt∈∀≤∈ There are embedding results about medians. P.J. Slater (Medians of arbitrary graphs, J. Graph Theory vol. 4, 389 – 392 , 1980) proved that any graph can be the median of some other graph. H.-Y. Lee and G. J. Chang generalized this result to graphs with weights on the vertices as follows. Definition. Let G be a connected graph and there exists a vertex weight function V(G) :w→+R. The status of a vertex x in G is defined by Σ∈=)(),()()(GVyyxdywxs. And the w-median of G is defined to be the subgraph of G induced by {})()()(:)(GVxxstsGVt∈∀≤∈. H.-Y. Lee and G. J. Chang (Medians of graphs and kings of tournaments, Taiwanese J. of Mathematics, Vol. 1, 103-110, 1997) proved that for any graph G with a positive vertex weight function w, there exists a graph H with a positive vertex weight functionsuch that G is an induced subgraph of H with w′)()(vwvw′= for all vertices v in G and G is the-median of H. We want to know if the result holds when the weights are assigned to the edges as well as vertices. w′ Definition. Let G be a connected graph with a weight functionV(G)∪E(G)→:w+R. (1) The length of a path P in G is defined by Σ∈=)()()(PEeewPl. (2) For vertices x, y in G, the distance between x and y is defined by )(min),(Plyxd= where P is taken over all paths joining x and y. (3) The status of a vertex x is defined by Σ∈=)(),()()(GVyyxdywxs. (4) The w-median of G is defined to be the subgraph of G induced by the set {})()()(:)(GVxxstsGVt∈∀≤∈. Problem 1. Let G be a connected graph with a positive weight function w on vertices and edges. Does there exist a graph H with a positive weight function w′ on vertices and edges such that G is an induced subgraph of H with w(v) = w′(v) for all vertices v in G, w(e) = (e) for all edges e in G and G is thew′w′-median of H. We can also consider the problem in which the weights are restricted to the positive integers. 2. Displacements of graphs Definition. Suppose that G is a graph. (1) For a permutation ψ of V(G), the displacement of G with respect to ψ is defined by Σ∈=)()(x) ,()(GVxxdGDψψ. (2) The displacement of G is defined by D(G) = max where the maximum is taken over all permutations ψ of V(G). )(GDψ Problem 2. Explore the relationship between the displacement and the status of a connected graph. ; 研究期間 9708 ~ 9807
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Mathematics] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	318	View/Open

社群 sharing

Loading...