文献

J-GLOBAL ID：201602009747099736   整理番号：70A0229038

有向グラフの枝の向きの反転による有向閉路消去

Cycle elimination in weighted digraphs by orientation reversal of edges.

著者 (1件)： DEO N
資料名： Proc Hawaii Int Conf Syst  (Proceedings of the Hawaii International Conference on System Sciences)
巻： 3rd  号： PART1  ページ： 419-422  発行年： 1970年 
JST資料番号： D0758A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 枝に重みが指定された有向グラフの枝の部分集合で,それに属する枝の向きを反転すれば,有向閉路のないグラフを与えるようなもののうち童みの総和が最小であるようなものを見出す方法の考察。まず.このような部分集合が任意のグラフに対して存在し得ることを証明し.つぎに取り扱うグラフは強連結グラフに限っても良いことを示す。また極小な枝集合を反転して得られる有向閉路なしのグラフは.任意の2節点に対しそれらを結ぷ有向道は一方から他方へのものがちょう度1個であるようなグラフであることを示した。最後に,重みの総和を最小に近づける枝集合をもとめるアルゴリズムを与えた;写図3参4

シソーラス用語： グラフ ,  有向グラフ
準シソーラス用語： 強連結グラフ ,  消去法 ,  閉路消去 ,  有向グラフ(閉路消去) ,  有向閉路 ,  有向閉路(グラフ/消去法)

タイトルに関連する用語 (6件)： 有向グラフ ,  枝 ,  向き ,  反転 ,  閉路 ,  消去