グラフ理論の問題で分からないものがあります。
次の問題の答えがわかる方は、解答を教えてください。

単純グラフG=(V,E)で、分離度k=1のとき、|V|=p、|E|=qであるなら、
次の式が成り立つことを証明せよ。
  p-1<=q<=(1/2)×p×(p-1)

よろしくお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (1件)

分離度1というのは全ての頂点が連結していると言うことでしょうか。


だとするとほぼ自明のような気がしますが。

厳密にやりたいというのなら帰納法を使えばよいでしょう。
とりあえずpー1<=qだけについてやってみます。

p=1の時 pー1<=qは成り立つ。
p<kの時 pー1<=qが成り立つと仮定すると p=kの時

Gのある頂点vとそれに付随する辺を取り去ったグラフをG'とする。
vの次数をnとするとGが連結グラフなのでG'は高々n個の連結成分に分かれる。
その連結成分をr1,r2,,,rm(m<=n)と置き、各連結成分の頂点数をp1,p2,,pm、
各連結成分の辺数をq1,q2,,,qmと置く。

G'の頂点数はkー1なので
p1+p2+、、、+pm=k-1ーー(*)

また各rは連結グラフで頂点数がk-1以下なので帰納法の仮定よりpi-1<=qiが成り立つ。
(*)に代入すると
(q1+1)+(q2+1)+,,,(qm+1)>=k-1
q1+q2+,,,+qm+m>=k-1(**)
ここでGの辺の数は各連結成分の辺の数と頂点vから出ている辺の数の和なので
q=q1+q2+,,,+qm+n
となります。
よって
q=q1+q2+,,,+qm+n>=q1+q2+,,,+qm+m>=k-1=p-1

以上よりp-1<=qは成り立つ。


てな感じです。
分離度の定義が違ったらごめんなさい。
    • good
    • 0
この回答へのお礼

ありがとうございます
参考になりました

お礼日時:2001/10/08 18:40

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q英語の参考書・問題集・理論本

高1です。

何か、英語を勉強するための参考書や問題集、理論本などがが欲しいと思っています。でも、実際に本屋に赴いてみると溢れんばかりの本がおいてあって、優柔不断な僕にはとても選別しきれるものではありませんでした(^_^;)

同じ出版社から出ている本でもいろんなバージョンがあったり、それらの違いも良く分かりません。

僕は今、英語に関しては塾に行ってません。これからもできたら行きたくないと思っています。その分大学受験に向けての勉強を人一倍しなければと思い、質問させていただきました。(目指すはそこそこ名が知れた国公立、多分理系です)

皆さんが良いとお思いになる参考書や問題集、または英語に関する理論本を教えていただけたらうれしいです。

ちなみに単語帳は速読とシス単を持ってます。

Aベストアンサー

(文法)
辞書本:Forest&英文法解説等
解説本:明慶徹の英文法が面白いほどわかる本
    佐々木和彦の基礎からがっちり!英文法等
問題集:UPGRADE or Nestsage等
(構文読解)
解説本:ビジュアル英文解釈PART1.2
    ポレポレ英文解釈
    富田の英文読解100原則上下等
問題集:基礎英文問題精講
構文把握のプラチカ等
(長文読解)
解説本:佐々木和彦の英語長文が面白いほどとける本
パラグラフリーディングのストラテジー
    横山のロジカルリーディング等
問題集:長文読解アドバンテージ
"毎年出る"頻出英語長文
やっておきたい英語長文300・500・700等
(英作文)
解説本: 大矢英作文講義の実況中継等
解説本2:竹岡広信の英作文〈原則編〉が面白いほど書ける本等
例文暗記:ドラゴンイングリッシュ等
難関本:大学入試最難関大への英作文―書き方のストラテジー
    大学入試英作文実践講義 等

と分野用途によって色々あると思います。

(文法)
辞書本:Forest&英文法解説等
解説本:明慶徹の英文法が面白いほどわかる本
    佐々木和彦の基礎からがっちり!英文法等
問題集:UPGRADE or Nestsage等
(構文読解)
解説本:ビジュアル英文解釈PART1.2
    ポレポレ英文解釈
    富田の英文読解100原則上下等
問題集:基礎英文問題精講
構文把握のプラチカ等
(長文読解)
解説本:佐々木和彦の英語長文が面白いほどとける本
パラグラフリーディングのストラテジー
    横山のロジカルリーディング等
問題集:長文読解ア...続きを読む

Qgcd(p,q)=1,∃a,b∈G;#G=pq,#=p,#=qならばGは巡回群

gcd(p,q)=1とする。(G,・)を位数pq(つまり#G=pq)のアーベル群とせよ。
aの位数がp,bの位数がq(つまり#<a>=p,#<b>=q)であるような元a,b∈Gが存在する時,
(G,・)は巡回群である事(つまり,∃g∈G;<g>=G)を示せ。
また,このような群Gの例を挙げよ。

という問題はどのようにして示せばいいか分かりません。

是非,ご教示ください。m(_ _)m

Aベストアンサー

問題の条件においてGの元abの位数を考えてみましょう。
また例の方はp=2,q=3などとすればすぐに挙げられるでしょう。

Q超弦理論 1.

超弦理論が旧い弦理論と異なるのなぜか?つまり導入された理由は何か?少し外れるが日本語で超弦理論と書かれるが英語は何(知っているが、既に認知症で失語症を起こしている)

Aベストアンサー

No1です。次のペア?後の2つ?限界を超える?このセット?の意味が、よくわかりませんが、超対称性粒子は、

すべてのフェルミオンにはボゾン (電子(エレクトロン)>>セレクトロン等:もとのフェルミオンの名前の先頭にSをつける)
すべてのボゾンはフェルミオン (光子(フォトン)>>フォティーノ等:ものとボゾンの後ろに、inoをつける)

が対応し、その相手を超対称性パートナーと呼びます。

Q英語で何と言いますか?

下記の文、英語で何といいますか?


フォロワーに強く認識される理論


フォロワーに影響する理論


フォロワーの心にささる理論

Aベストアンサー

No.1です。ご質問の3題とも英訳すればtheoryが最初に来るような日本語だからtheoryが最初に来たまでです。

『followersのセオリー』が何かが分かりませんが、

Followers theory

Followers' theory

としても英語としてはなんらおかしくありませんが。

Q(i)spanX=V ならば x∈V,x=Σ[i=1..n](xi),(ii)x∈V,∥x∥^2=Σ[i=1..n]||^2ならばXは完

お世話になっています。

[Q]X={x1,x2,…,xn}を内積空間Vの正規直交集合とせよ。この時,次の(i),(ii)を示せ。
(i)spanX=V ならば x∈V,x=Σ[i=1..n](<x,xi>xi)
(ii)x∈V,∥x∥^2=Σ[i=1..n]|<x,xi>|^2ならばXは完全

完全の定義は「正規直交集合Xが完全とはVの中での最大個数の正規直交集合の時,Xを
完全と言う」です。
つまり,#X=max{#S∈N;(V⊃)Sが正規直交集合}を意味します。

証明で行き詰まっています。

(i)については
x∈Vを採ると,spanX=Vよりx=Σ[i=1..n]cixi (c∈F (i=1,2,…,n))と表せる。
これからΣ[i=1..n](<x,xi>xi)にどうやって持ってけばいいのでしょうか?

あと,(ii)についてはさっぱりわかりません。
何か助け舟をお願い致します。

Aベストアンサー

>x=Σ[i=1..n]cixi (c∈F (i=1,2,…,n))と表せる。
<xi,x>を計算すれば終わり

>(ii)についてはさっぱりわかりません
「任意の」x∈Vに対して
∥x∥^2=Σ[i=1..n]|<x,xi>|^2
ならばXは完全

x1,...,xnとは異なるyをとり,
x1,...,xn,yが正規直交であると仮定する.
||y||^2 = Σ[i=1..n]|<y,xi>|^2を計算すれば
矛盾がでてくる.

Q音楽理論を学べるソフト

DTMに興味があり、作曲したいのですが、音楽の経験は皆無で、今まで、キーボードの教本等で簡単な曲を練習したりしました。
作曲のためには音楽理論を理解している必要があると思い、音楽理論に関する本を数冊読んでみましたが、ほとんど理解出来ませんでした。


AppleのサイトのMade4Mac→音楽&オーディオ→音楽理論と選択し、検索したところ、音楽理論を学べるようなソフトウェアが表示され、こういったソフトで学ぶ方が、私には理解しやすいのではと思い、探しているのですが、紹介されているソフトは英語にしか対応していないようで、英語が苦手な私には利用は難しいです。
http://www.harmonicvision.com/
等。

音楽理論が学べるソフト(WindowsやMac)で、日本語に対応している物は無いでしょうか?
ご存知でしたら、お教え頂けると嬉しいです。

また、他に、音楽の知識が無くても、音楽理論の良い勉強法などもありましたら、お教え頂ければ幸いです。

Aベストアンサー

作曲する上で、音楽理論に対し知識がないよりはある方が、何かと
有利なのは、間違いないと思います。ただ、作曲能力と音楽理論
の知識の深さが比例するかといえば、そんなことは絶対ないと思い
ます。要は音楽理論というのは、単に作曲するための1つに過ぎない
という事なのだと思います。

実際には、知りませんが、数々の名曲を残している、ビートルズの
メンバーにしても、それほど深い音楽理論の知識は無かったのでは
ないかと思いますよ。

おそらく最低限必要な知識というのは、楽譜が読める(音楽記号の
意味がわかる)、それからコード理論の基礎がわかる(メジャー
コードとマイナーコードの違い等)、これぐらいの知識があれば、
差し当たり、作曲する上で充分と言えるのではないでしょうか?

あとは、いろんな音楽聴いて、耳を肥やす。これが大事だと思い
ます。そして、ただ聴くだけではなく、聴いた曲をコピーしてみて、
自分でそれを弾いてみたり、譜面にしてみたりすることって、
勉強になると思いますよ。

Q4次元のベクトルpとqに対して、|p|*|q|*sinθはどのようにかける?

2次元のベクトルp=(a,b)とベクトルq=(x,y)に対して、
なす角をθとすると、
|p|*|q|*cosθ=ax+by,
|p|*|q|*sinθ=±(ay-bx)
となります。

4次元のベクトルp=(a,b,c,d)とベクトルq=(x,y,z,w)に対しては、そのなす角θというものが、
|p|*|q|*cosθ=ax+by+cz+dw
で定義されますが、このとき、
|p|*|q|*sinθ
は成分を用いてどのようにかけるのでしょうか?

Aベストアンサー

n次元ベクトルに対して外積はm=Combination(n,2)次元空間のベクトルになります。
n次元ベクトルの直交基底ei(i=1,2,...,n)に対して、ei×ej=-ej×eiを直交基底にとります。
すると、成分表示すればたすき掛けが成分として出てきて、双線型性をもった「積」(m次元ベクトル)が定義できます。
u、vをn次元ベクトルとして、u×vはもとの空間の基底の取り方にはよらない(本当か?)ので
直交写像Tによっても外積はかわらないので
|u×v|=|(Tu)×(Tv)|
さらに、u,vの張る平面がe1,e2の平面と一致するようにTをとると、2次元の場合に帰着できて
|u×v| = |(Tu)×(Tv)| = |Tu||Tv|sinθ
となります。さらに
|Tu|=|u|, |Tv|=|v|
なので、
|u×v| = |(Tu)×(Tv)| = |Tu||Tv|sinθ = |u||v|sinθ
が成り立ちます。よって、
|u×v|^2=Σ(aibj-ajbi)^2 = |u|^2 |v|^2 (sinθ)^2
です。(本当か?)

n次元ベクトルに対して外積はm=Combination(n,2)次元空間のベクトルになります。
n次元ベクトルの直交基底ei(i=1,2,...,n)に対して、ei×ej=-ej×eiを直交基底にとります。
すると、成分表示すればたすき掛けが成分として出てきて、双線型性をもった「積」(m次元ベクトル)が定義できます。
u、vをn次元ベクトルとして、u×vはもとの空間の基底の取り方にはよらない(本当か?)ので
直交写像Tによっても外積はかわらないので
|u×v|=|(Tu)×(Tv)|
さらに、u,vの張る平面がe1,e2の平面と一致するようにTをとると...続きを読む

Q相対性理論を英訳してください。

万有引力は英語で
The law of universal gravitation.
ですが、相対性理論は英語でなんと言うんですか?

Aベストアンサー

スペースアルクで検索ができます。
3種類ほど出ました。
ここに貼りつけていいものかどうか迷いましたので下記にリンクを張らせて戴きます。

参考URL:http://www.alc.co.jp/index.html

Q異なる4点A(α)、B(β)、C(γ)、D(δ)で、|α|=|β|=|γ|=|δ|、α+β+γ+δ=

異なる4点A(α)、B(β)、C(γ)、D(δ)で、|α|=|β|=|γ|=|δ|、α+β+γ+δ=0のとき、A、B、C、Dを頂点とする四角形が長方形になることの証明を、どなたかお願いします。

Aベストアンサー

(1) 2次元ユークリッド平面上のベクトルの話だという限定を付けないと、長方形にはならない。(3次元なら、たとえば原点に重心がある正四面体の頂点がα,β,γ,δでも条件を満たすでしょ。)
(2) |α|=0の場合は例外だし、α,β,γ,δのうちに同じものが含まれる場合も例外。
ということに注意した上で
(3) |α|=|β|=|γ|=|δ|=1の場合に証明すれば、他の場合は自明なので、=1の場合だけ考える。
(4) x = (α+β) とすると、αとxがなす角θはxとβがなす角と同じ。
(5) (γ+δ) = -xでなくちゃならない。で、γとxがなす角ξはxとδがなす角と同じ。
あとはθ=ξを示せばよかろ。


人気Q&Aランキング

おすすめ情報