圖形的帶寬與輪廓

Abstract

圖形論之帶寬及輪廓在許多實際應用的領域裡是有用的參數，這兩個參數已經被廣泛地研究。許多文章對特殊或一般圖形的帶寬值及輪廓值均有著墨，本論文主要是在幾類組成圖上研究此二參數的作用方式。 首先，我們考慮帶寬問題，該問題尋求圖形 上的線性配置使能將邊的伸展達到最小化。明確地說，一個嵌射 的帶寬是 ，而圖形 的帶寬 則是所有這些嵌射之帶寬的最小值。於此論文中，我們會在三類距離圖(包括 )、 及 )上考慮帶寬問題；也會在與此三類距離圖作某些合成的圖類上考慮帶寬問題。我們在有些合成圖上導出了精確值，但對有些合成圖只能提出可達上界及下界。 接著，我們考慮輪廓問題，此問題與帶寬問題有著緊密的關係。目的在尋找一個嵌射，將圖形 的頂點集對應到正整數集，使得每一頂點的標號與它的閉鄰域中所有點之最小標號差的總和為最小。本論文在兩類組成圖(叉圖及構成圖)上考慮輪廓問題，在叉圖的部分吾人僅獲得 、 (其中 且 )及 的輪廓值；在構成圖的部分吾人則建立 之可達上界及下界，藉此也決定了當 為區間圖或某些特定圖時 的精確值。