- ベストアンサー
グラフ理論においての「木」
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
木(tree)では、任意の2点は、一つの路(path)で結ばれているから、ある点から数えて奇数番目の点と偶数番目の点で二分割すれば、二部グラフになる。 木に含まれる路の長さが、2以内であれば完全二部グラフになる。
その他の回答 (1)
- Mell-Lily
- ベストアンサー率27% (258/936)
参考URLをご覧ください。
関連するQ&A
- K(3,3)完全二部グラフ 非平面性 グラフ理論
連結な平面グラフにおいて位数=p、サイズ=q,とおくと q=<3p-6 という公式？定理？がありますが、 完全二部グラフK(3,3)の非平面性を証明するのに使おうと思ったら 9<=18-6=12 で成り立ってしまいます。 すべての領域が四角形以上なら q=<2p-4というのを使えば証明できるのですが、前の方の公式がこの場合に使えないのはなぜなんでしょう
- 締切済み
- 情報工学
- グラフ理論（木について）の証明
2点以上の点からなる木は、2部グラフであることを数学的帰納法を用いて証明するには、どのようにしたらよいのでしょうか？ ※使っても良い事実として、「2点以上の点からなる木では葉が存在する」というものがあります。 点の個数が2のときは明らかであることは分かるのですが、その後どのようにしたらよいのかが分かりません。 （もし、点の個数を使うときはn，辺の個数はeを用いて教えてください） よろしくお願いします。
- 締切済み
- 数学・算数
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフKn,Kn￣、Km,n,Cn,Tn〔Ｔnは位数nの木〕の染色数をそれぞれ求めよ。 ２．グラフKn,Km,n,Cn,Tnの辺染色数をそれぞれ求めよ。 ３．オイラーの多面体公式を証明せよ。 ４．以下の問題を証明せよ。 〔１〕頂点数が３以上の平面グラフGが極大平面グラフであるための必要十分条件は、Gのすべての領域が三角形であることである。 〔２〕４頂点以上の極大平面グラフGにおいて、 △〔G〕 不等式 Σ 〔6-i〕Ni =12 〔Ni = {次数がiの頂点の数}〕が成立する。 〔３〕４頂点以上の平面的グラフには、次数５以下の頂点が存在する。 〔４〕K5,K3,3は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- グラフ理論の木（tree,木構造,樹木）について
グラフ理論でいう木（[木構造][tree][樹木]）のグラフにおいて、「点数が７の木」の種類が一体何種類あるのかがわかりません。 どなたかわかる方いたら教えてください。お願いします。
- ベストアンサー
- 数学・算数
- グラフ理論の問題(木について)
次のことを証明せよ。 1.木の全ての最長路はその中心点を通過する。 2.木の最長路が1つ識別されると、木の中心が示される。 という問題です。 最長路の長さが偶数の場合と基数の場合に場合分けをしたとき 偶数の場合は両端の点から同じ距離にある点が中心点であり、 基数の場合は両端の点から同じ距離にあるような、隣接した2点が中心点になることを使うようなのですが、どのように使うのでしょうか。 また、なぜこうなるのでしょうか。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- ハミルトングラフの証明
単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。
- 締切済み
- 数学・算数
