ネットワーク制御 の スパニングツリーに関する解説。

株式会社 日立ソリューションズ

HITACHI Inspire the Next

  • ホーム
  • ソリューション・商品
  • 事例紹介
  • セミナー・展示会
  • ビジネスコラム
  • 企業情報
  • お問い合わせ

スパニングツリー

読み方、または別称:すぱにんぐつりー

スパニングツリーとは、グラフ理論においてスパニング木(Spanning Tree)あるいは極大木(きょくだいき)、全域木(ぜんいきぎ)など木のことを指す。また、グラフG(V,E)においてT⊆Eとなる辺集合Tがある時、グラフS(V,T)が木(閉路を持たないグラフ)であるなら、S(V,T)をグラフG(V,E)のスパニング木とすると定義される。
要するに、あるグラフのすべての頂点とそのグラフを構成する辺の一部のみで構成される木のことを指す。各辺にコストがある場合は、最小コストで構成されるスパニング木は貪欲法O(|E|log|E|)となるアルゴリズムから知られている。
また、頂点から別の頂点へ移動する際、コストが最小になるスパニング木のことを最短経路木という。また、頂点から他のすべての頂点への移動コストが最小になるような最短経路木のことを求める問題は「最短経路問題」という。
この問題は、ダイクストラ法とワーシャル-フロイド法がある。ダイクストラ法は、単一の頂点から任意の頂点へ最短経路木を求める方法となり、ワーシャル-フロイド法は、任意の頂点から任意の頂点への移動コストが最小になる最短経路木を求める方法になる。

ページトップへ戻る

話題の用語

ITと社会用語辞典

ワークロード

ワークロードとは、システムのパフォーマンスを適正な状態に保つための指標のこと。

インターネット用語辞典

ライフログ

ライフログとは、人間の活動の記録(行動履歴)をデジタルデータとして記録すること、およびその記録のことである。

ページトップへ戻る

情報漏洩防止ソリューション 「秘文」

ITのお悩みをソリュっと解決! 特命課ソリュートくんがいく!

『オムニチャネル』から商品を探すページです。日立ソリューションズは、コンサルティングからシステム構築、サポートとトータルソリューションをご提供するシステムインテグレーション企業です。

ページトップへ戻る