圖之著色與控制問題

Abstract

著色問題是圖論中重要的課題,旨在將圖的 點或邊著色,使得滿足某種性質.控制問題則在 找最少點去控制圖的所有點,有時這些點必須 滿足其他的性質,例如:連通、獨立、點團等.本 計畫最主要在研究圖著色與控制問題,並涉及 獨立集與網路的廣播和散播問題.在點著色方 面,本計畫將探討距離圖上的點著色問題和稱 為L(2,1)標號的一種點著色推廣問題.距離圖是 以某度量空間的元素為頂點,兩點距離是某一指定數則連邊,所形成的圖;此種圖上點著色數 的結果,目前以一維或二維歐氏空間之子空間 為主,我們的目標除了在低維空間將前人之未 完成的結果加強外,更希望往高維空間研究. L(2,1)標號是要求相鄰兩點所著顏色至少差2,距 離為2的不同點要著不同色;我們的目標是在前 人的上下界定理以外,研究演算法的設計.控制 問題源自運籌學中的選趾問題,是要找一最小 點集,使不被找出來的點和至少某一被找出來 的點相鄰.也可以更要求此集合為連通、獨立 、點團等性質.本計畫旨在從演算法的眼光在 設計有效算則,一般而言,這些問題是所謂NP難, 過去十餘年來,在各種不同的特殊圖類(例如:樹 形圖、強弦圖、排列圖、區間圖、反比圖)均 有很好的結果,我們的重點將放在距離不變圖 和具最大鄰旁次序圖.獨立集是圖中兩兩不相 鄰的點集,圖的點著色也可以說是將圖的所有點分割成最少的獨立集.極大獨立集是一不為 其他獨立集之真子集的獨立集,這也相當於圖 的獨立控制集.本計畫旨在計算圖中獨立集及 最大獨立的數目的上下界,並了解達到上下界 的圖的構造.散播和廣播是在研究通信網路中 一群人散播消息的問題.假設有n個人1,2,...,n,每 個人在開始時所知道恰好一項消息,而不曉得 其他人的消息,他們要用電話來傳播這些消息, 每次某兩個人打電話總是在一單位時間內將目 前所知道的消息交換完畢.散播次數問題是在 求最小的通話次數,以使所有人知道所有消息; 散播時間問題是在允許若干對的人可以在同一 時間通電話時,所有人知道所有消息的最短時間;廣播時間問題,則是在求某一特定人將他的 消息傳給所有人的最短時間.本計畫是在研究 上述問題的不同變形問題:集對集廣播次數問 題和時間問題、多人同時通話、通話時間和傳 送消息多少成比例、單向通話、每人至少(或 恰好)知道k個消息等.