- ベストアンサー
正則2部グラフ
正則2部グラフ 空でない正則2部グラフの2分割を(X,Y)とすると、XとYは同じ大きさであることを示せ。 という問題です。 2部グラフ…頂点集合が互いに素な部分集合XとYに分けられ、各辺の両端点は一方がXに、他方がYに含まれるグラフ 正則グラフ…すべての頂点の次数が等しいグラフ この定義は理解しています。ただ、問題が自明な感じがして証明が思いつきません。 どなたか証明法を教えてください。
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (2)
- alice_44
- ベストアンサー率44% (2109/4759)
X の頂点数を x、 Y の頂点数を y、 正則グラフの次数を n とすると、 X に接続する辺の総数が nx、 Y に接続する辺の総数が ny となって、 両者は等しい。 すなわち、nx = ny より x = y。
お礼
ご回答ありがとうございます。
- boiseweb
- ベストアンサー率52% (57/109)
質問者さんの理解に基づく「2分割」の定義を補足にどうぞ． 2分割とは，一般のグラフについて定義できるのか，正則グラフについてのみ定義できるのか，2部グラフについてのみ定義できるのか，それも含めて．
補足
「2部グラフにおいて」、頂点集合を二つの部分集合に、各集合内の頂点同士の間には辺が無いように分けること、と思っています。
関連するQ&A
- 正則性について。
--------------------------------------------------- f(z)=1/(bar(z)) z = x + iy とし z ≠ 0においてf(z)が正則であるかどうか判定せよ。 また、 Ｒ>０に対して複素積分 ∫_[|z|=R]f(z)dz の値を求めよ --------------------------------------------------- という問題なのですが、 u=x/x^2＋y^2, v=u/x^2＋y^2とすると、 ∂u/∂x = y^2-x^2/(x^2＋y^2)^2 ∂v/∂y = x^2-y^2/(x^2＋y^2)^2 となり、コーシー・リーマンの判定式を用いると、 ∂u/∂x≠∂v/∂yとなり、条件を満たさないので、 f(z)は正則ではないという結果が出ます。 f(z)が正則ではないのは、(bar(z))=0で特異点を持つためだと思うのですがこの問題の場合、z≠0で除外されていますよね？ この場合、正則なのでしょうか？ おそらく、特異点の捉え方がよくわかっていないのだと思います。 また、 次の問題はコーシーの積分公式で求めると思うのですが、 この公式は、bar(z)の場合にもそのまま当てはめてよいのでしょうか？ ご指導ご鞭撻の程、宜しくお願い致します。
- 締切済み
- 数学・算数
- 2次関数のグラフについて
2次関数のグラフについてのグラフの頂点の座標を求める問題があるのですが ｙ＝ｘ＾2＋6ｘ＋13 〔解〕 ｙ＝(ｘ＾2＋6ｘ)＋13 ＝(ｘ＾2＋6ｘ+9)-9+13 ＝(ｘ+3)＾2+4 よって 頂点(-3、4) となるのですが、なぜ２つ目の行の所が+9 になるのかがよく分かりません。 教えていただけるとうれしいです＞＜
- ベストアンサー
- 数学・算数
- グラフの証明を教えてください
背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをＧとします Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。 そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき Ｈの各頂点の次数は偶数である。 この証明を教えてください。
- 締切済み
- 数学・算数
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフ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は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- グラフの概形がわかりません。
関数y=x^2/x-1のグラフの概形はどうなりますか？ 分数関数は分母の次数>分子の次数にする、と教わったのですが、やり方わかりません。 教えてくださいm(__)m
- ベストアンサー
- 数学・算数
- 2次関数の最大・最小
2次関数の最大・最小 aが実数として、a<=x<=a+2で定義される関数f(x)=x^2-2x+3がある。この関数の最大値、最小値をそれぞれM(a),m(a)とするとき、関数b=M(a),b=m(a)のグラフをab平面に（別々に）書け。 最大・最小となる候補を利用 y=d(x-p)^2+qのグラフが下に凸の場合、 ・区間α<=x<=βにおける最小値は、x=pが区間内であれば、頂点のｙ座標q そうでなければ、区間の端点でのf(α）,f(β）のうち小さいほう ・区間α<=x<=βにおける最大値は、区間の端点での値f(α）,f(β）のうちの大きいほう である。結局、「最大値や最小値にｂなる可能性のある点は、頂点と両端の点の３つのみ」であるから、 「頂点のy座標（頂点が区間内にあるとき）、および区間の端点のｙ座標からなる３つのグラフを描いておき、最も高いところをたどったものが最大値のグラフ、最も低いものをたどったものが最小値のグラフである。 教えてほしいところ 「最大値や最小値にｂなる可能性のある点は、頂点と両端の点の３つのみ」であるのは理解できます。しかし、 「頂点のy座標（頂点が区間内にあるとき）、および区間の端点のｙ座標からなる３つのグラフを描いておき、最も高いところをたどったものが最大値のグラフ、最も低いものをたどったものが最小値のグラフである。という部分が理解できません。 何故、たどったものがそれぞれ最大値または最小値のグラフだといえるんですか？？ 論理的に教えてください
- ベストアンサー
- 数学・算数
- ２次関数のグラフの書き方
y=|2x＾2－x－5|のグラフはどのようにかけばいいんでしょうか？ 軸はx=1/4,頂点は(1/4,－41/8)になり、y＜0の部分はひっくリ返すということは分かったのですが、グラフとy軸との交点が求められません・・・ 求め方を教えてください！！
- ベストアンサー
- 数学・算数
お礼
ご回答ありがとうございます。