大会名称 |
---|
2016年 総合大会 |
大会コ-ド |
2016G |
開催年 |
2016 |
発行日 |
2016/3/1 |
セッション番号 |
AS-1 |
セッション名 |
グラフ理論の工学的魅力を語る - 基礎から最前線の応用まで |
講演日 |
2016/3/17 |
講演場所(会議室等) |
総合学習プラザ 2F 第16講義室 |
講演番号 |
AS-1-2 |
タイトル |
代数的連結度最大グラフに関する一定理の拡張 |
著者名 |
◎石井涼也, 高橋規一, |
キーワード |
代数的連結度, 完全多部グラフ, 最大化, 合意アルゴリズム |
抄録 |
本研究の目的は,指定された頂点数と辺数の下で代数的連結度を最大にするグラフ構造を求めることである.この問題に関する先行研究として,Ogiwaraらは,ある種の完全2部グラフがそれと同じ頂点数と辺数をもつグラフの中で代数的連結度を最大にすることを証明した.本稿では,この結果を完全多部グラフに適用可能な形に拡張する.また,Ogiwaraらの条件を満たす完全2部グラフに,ある本数以下の辺を加えたものも上記の意味で代数的連結度が最大であることを示す. |
本文pdf |
PDF download
|