圖的雙極定向及其算法.pdf

1、雙極定向在VLSI設(shè)計及其它工程計算中都有著廣泛的應(yīng)用，同時也是許多畫圖算法的基礎(chǔ)，因而近年來越來越受到人們的重視，得到了廣泛而深入的研究。 雙極定向的概念最早由Brooks，Tutte等人在1940年提出，當(dāng)時討論的是一個純數(shù)學(xué)的問題，1967年，A.Lempel及S.Even等人在一篇關(guān)于平面檢測的文章中提出了雙極標(biāo)數(shù)的概念。Even和Tarian在1976年給出了計算無向連通圖的雙極標(biāo)數(shù)的線性算法。從此，雙極定向被廣泛地應(yīng)

2、用在VLSI設(shè)計及圖的可視性表示、正交畫圖等畫圖算法中。 本文在分析了圖的基本圈的結(jié)構(gòu)的基礎(chǔ)上，提出了兩種基本構(gòu)型。通過對這兩種構(gòu)型的優(yōu)化，給出了一個圖的雙極定向的算法。全文共分四章： 第一章介紹了一些基本概念及其相關(guān)背景。 第二章介紹了兩種雙極定向的基本算法，并對算法進(jìn)行了改進(jìn)，給出了具體的算例。 第三章利用吸收規(guī)則，分析了圖的圈的結(jié)構(gòu)，構(gòu)造了圖的雙極定向的新算法，并對算法進(jìn)行了簡單分析。 第四