木数学

ウィキペディア

木 (数学)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/06 05:38 UTC 版)

「樹形図」はこの項目へ転送されています。小比類巻かほるのアルバムについては「樹形図 (アルバム)」をご覧ください。

木
6つの頂点と5つの辺からなる木の例
頂点	n
辺	n − 1
彩色数	2
テンプレートを表示

数学、特にグラフ理論の分野における木（き、英: tree）とは、連結で閉路を持たない(無向)グラフである。有向グラフについての木（有向木）についても論じられるが、当記事では専ら無向木を扱う（有向木については節にまとめた）。

閉路を持たない（連結であるとは限らない）グラフを森（もり、英: forest）という。木は明らかに森である。あるいは、森を一般的な場合とし、連結な森を木という、とすることもある。

→コンピュータ上での木の扱いについては「木構造 (データ構造)」を参照

特徴づけ

n 個の点からなるグラフ T について次は同値である^[1]。

• T は木である
• T に閉路はなく、 n − 1 本の辺を持つ
• T は連結で、 n − 1 本の辺を持つ
• T は連結で、すべての辺は橋である
• T の任意の2点を結ぶ道がちょうど1つある
• T に閉路はないが、新しい辺をつけ加えると閉路が必ず1つできる

性質

木 T には、以下のような性質がある。

• T の2点を結ぶ T に含まれない辺 e に対して、T + e には e を通るただ一つの閉路があり、この閉路上の任意の辺 f に対して T + e - f は木となる。
• 頂点が2つ以上ある木には少なくとも2個の端末点がある。また、端末点とは次数1の点である。

上の定理から、木には必ず端末点があり、その端末点を除去すると位数の一つ小さい木が得られる。逆に言えば、位数 n の木は、位数 n − 1 の木に一つの新しい点と、これに接続する一本の新しい辺を加えて得られる。

根つき木

あるノードを選んで、それを一番「上」にあると考えると、そのノードを基準として2つのノードに上下の関係を考えることが出来る（すべてのノードの組み合わせについて定義されるとは限らない）。このとき、その一番上のノードを根（ね、英: root）という。根を持つ木を単なる木と区別して根付き木という。

根つき木に関する用語は、それを家系図に見たてたものが多く使われる。

• 点 v₁ と v₂ が辺で結ばれており、しかも v₁ の方が v₂ よりも根に近いとき、v₁ は v₂ の親であるといい、v₂ は v₁ の子であるという。
• 点 v₂ と v₃ が共通の親を持つとき、v₂ と v₃ は兄弟という。
• 根つき木上の2点 v₁, v₂ に対し、v₂ と根を結ぶ経路上に v₁ があるとき、v₁ は v₂ の先祖であるといい、v₂ は v₁ の子孫であるという。

また、根つき木に関する用語として、他に以下のようなものがある。

• 子を持たない点を葉という。
• 各辺の長さを1とするとき、点と根との経路の長さをその点の高さという。また、根から最も経路の長さが長くなる点までの長さを、その木の高さという。

n分木

n を自然数とする。葉ではない各点に対しその点の子の数が常に n であるような木をn分木(nぶんぎ; n-ary tree)という。特に二分木はいくつかのアルゴリズムと密接に関わるデータ構造である（ただし大抵は次で述べる有向木による二分木）。

有向木

一般に、無向木は任意の点を根とみなすことができる。それに対し有向木は、根である点をただ1つだけ持つ。辺の向きとして、根から葉に向かっている場合と、葉から根に向かっている場合とがある。混在はできない（混在してしまうと閉路ができてしまう）^[2]。

閉路を持たない任意の有向グラフは有向非巡回グラフ（Directed Acyclic Graph、DAG^[3]）である。有向木は連結な有向非巡回グラフでもあるが、連結な有向非巡回グラフが必ずしも有向木とは限らない（DAGでは子孫あるいは親の共有がある場合がある。そうするとそれは木ではない）。

脚注

1. ^ ウィルソン 2007, p. 60.
2. ^ データ構造などの実装としてはしばしば、Unixのファイルシステムにおける .. というディレクトリエントリなどのように、逆向きのリンクを持たせることがある。
3. ^ 頻出するデータ構造であり、アクロニム風に「だぐ」と呼ばれることも多い。

参考文献

• ウィルソン, R. J.『グラフ理論』 原書第4版、西関隆夫・西関裕子、近代科学社、2007年。ISBN 978-4-7649-0296-1。 

関連項目

• カクタスグラフ
• 系統樹

外部リンク

• Graph Theory (Reinhard Diestel)

表 話 編 歴 グラフ理論
要素・定義・表現	頂点 辺（英語版） グラフ 無向 有向 ラベル付き（英語版） 重み付き（英語版） ハイパーグラフ 接続行列 隣接行列 隣接リスト
指標	位数（英語版） サイズ（英語版） 次数 次数行列 距離（英語版） 半径 直径 内周 (頂点)彩色数 辺彩色数（英語版） 点連結度 辺連結度 交叉数（英語版）
部分構造	ループ（英語版） 多重辺（英語版） 部分グラフ（英語版） 誘導部分グラフ 道 閉道 連結成分（英語版） 強連結成分（英語版） 橋（英語版） カット クリーク 独立集合 支配集合（英語版） マッチング オイラー路 シュタイナー木 全域木 ハミルトン路
全体構造	連結グラフ 正則グラフ 立方体グラフ ケージ 強正則グラフ 木 平面グラフ 2部グラフ 有向非巡回グラフ 弦グラフ ムーアグラフ パーフェクトグラフ 対称グラフ 半対称グラフ 頂点推移グラフ 辺推移グラフ 距離推移グラフ 補グラフ 双対グラフ グラフ同型
固有名を持つグラフ	パスグラフ（英語版）Pn 閉路グラフCn 完全グラフKn 完全2部グラフKm,n スターSn = K1,n 車輪グラフWn 空グラフ ピーターセングラフ ヒーウッドグラフ マギーグラフ ホフマンシングルトングラフ フォークマングラフ
トピック・定理	一筆書き オイラーの多面体定理 クラトフスキの定理 四色定理 五色定理 ケイリーの公式 プリューファー列 最短経路問題 巡回セールスマン問題 中国人郵便配達問題 ダイクストラ法 ベルマン-フォード法 ワーシャル-フロイド法 ハミルトン閉路問題 最大クリーク問題 頂点被覆問題 最小頂点被覆問題 最大独立集合問題 最大流最小カット定理 支配集合問題 次数直径問題 安定結婚問題
カテゴリ / コモンズ

典拠管理データベース: 国立図書館	ドイツ イスラエル アメリカ チェコ

Weblio日本語例文用例辞書

「木 (数学)」の例文・使い方・用例・文例

• 雨が降らなかったせいで草木が枯れてしまった
• その木は実がたわわになっている
• 道路の向こう側に木がある
• 木が道路に倒れている
• これらの木は東京の湿気の多い気候によく適応している
• 彼女は木にもたれ掛かっていた
• 秋の色に赤々と輝く木々
• 木材の長さに目をやる
• 通り沿いの桜の木
• 木に囲まれた城
• 木を3メートルずつ離して植えた
• 周囲が10メートルの太い木
• 彼は木曜日にヨガの教室に通っている
• この木の葉は秋には黄色くなる
• 彼の木綿のズボンはまるでスカートのように膨らんでいた
• 冬になると木々の葉が落ちる
• 実を結ばなくなった老木
• この木はあまり実がならないだろう
• よく実のなる木
• 木の葉が色を変えると，まもなく冬がくる