3連結グラフの定義を分かりやすく教えてください
お願いします

A 回答 (4件)

NO.2の者ですが、例え話のほうが間違いです。


 定義は正しいです。すみません。

 ある国にいくつかの町があり道でつながっていたとします。
 その国が3連結であるとは、どの二つの町を除いても
 その国のその他の町はつながっているということです。
 除くのは、道ではなく点のほうでした。

 連結度とは、最小切断集合の点の個数のことです。
 いくつ点を除くと連結でなくなるかということです。
 
    • good
    • 0

すいません。

NO1の者ですが
「3連結」という表現が有ることを知りませんでした。
しかし、tiezo-さんの町と橋の話から推測すると、

「グラフGが k-連結であるとは、Gからどんな(k-1)個の点を除去しても
 その結果得られるグラフは非連結でも単点でもない。」

「グラフGが k-連結であるとは、Gからどんな(k-1)個の道を除去しても
 その結果得られるグラフは非連結でも単点でもない。」

では、ないのでしょうか?
(僕の出しゃばりでしたらすいません。)
    • good
    • 0

連結の定義は、


 グラフにおいて任意の二点に道が存在することである。
k-連結の定義は
 グラフGが k-連結であるとは、Gからどんな(k-1)個の点を除去しても
 その結果得られるグラフは非連結でも単点でもない。

3連結グラフであれば、どんな2点を除去しても
非連結にも単点にもならないことです。
すなわち、連結であるということです。

たとえば、単なる連結であれば、一つの橋が壊れただけで
行けない所が出てくるかもわからないですが、
どの二つの橋が壊れても行けないところが
ないならば、その町は3連結の町であるということだと思います。
    • good
    • 0

こんばんわデス。


えっと、僕はまだ高校生のため、習ってないだけと言う可能性も有りますが、
これだけ待っても誰一人回答しないので、回答することにします。
「連結グラフ」なら分かりますが、「3連結グラフ」はやはり分かりません。
少し調べてみましたが、やはり分かりませんでした。
おそらく無いのでは無いでしょうか?どこで見かけたのでしょうか?
もしかしてこういう事は無いですか?

1○○グラフについて
 (うだうだうだ・・・)
2××グラフについて
 (うだうだうだ・・・)
3連結グラフについて
 (うだうだうだ・・・)

どうでしょうか?あと、「連結グラフ」の定義なら分かりますよね?
連結グラフの「位数が3」とか「3部グラフ」なら言うんですけどねぇ・・・
どうなんでしょう?
では、お役に立てませんでしたが、ずっと放置しておくよりかはマシかなと・・・
    • good
    • 0

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

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

Q(実数体R⊃)Aが非連結と連結の定義はこれで正しい?

(実数体R⊃)Aが非連結と連結の定義についてお伺いします。


(実数体R⊃)Aが非連結である。

A⊃∃B1,B2:空でない開集合 such that A=B1∪B2且つB1∩B2=φ


(実数体R⊃)Aが連結である。

Aは非連結でない


で正しいでしょうか?

Aベストアンサー

Aが開集合ならばこれでいいが、開集合でない集合にも連結、非連結を定義しようとするとこれではいけない。
Aが開集合でないとき、A=B1∪B2となる開集合B1、B2は存在しないから、全部連結になってしまう。

Q1+1=2、2×3=6の証明のための、3変数関数fでの定義と帰納的定義は同値?

過去の質問「1+1=2の証明って?」
http://oshiete1.goo.ne.jp/kotaeru.php3?q=217225
を精読しました。
過去の質問では、小さい自然数の定義した上で、プラスの定義を3変数関数fを使って、

●f(n,m,m)=n
●m≠kのとき、f(n,m,k) = f(s(n),m,s(k))
そして
●+(n,m)=f(n,m,0)

とされていました。

ここでは少し違って考えます。
まず、自然数(ここでは0も含める)の定義ですが、Peano's Axioms
http://mathworld.wolfram.com/PeanosAxioms.html
をみていただくとして、
自然数 a の 後者を suc(a) と書くことにします。
小さい自然数では、
0 := {}
1 := suc(0)
2 := suc(1)
3 := suc(2)
などとします。

次に+の定義ですが、帰納的に、
a+0:=a
a+suc(b):=suc(a+b)
で定義します。

すると、
1+1=1+suc(0)=suc(1+0)=suc(1)=2
と証明できたことになります。

×の定義を、帰納的に、
a×0:=0
a×suc(b):=(a×b)+a
で定義します。

すると、
2×3=2×suc(2)
=(2×2)+2
=(2×suc(1))+2
=((2×1)+2)+2
=((2×suc(0))+2)+2
=(((2×0)+2)+2)+2
=((0+2)+2)+2
=((0+suc(1))+2)+2
=((suc(0+1))+2)+2
=((suc(0+suc(0)))+2)+2
=((suc(suc(0+0)))+2)+2
=((suc(suc(0)))+2)+2
=((suc(1))+2)+2
=(2+2)+2
=(2+suc(1))+2
=(suc(2+1))+2
=(suc(2+suc(0)))+2
=(suc(suc(2+0)))+2
=(suc(suc(2)))+2
=suc(3)+2
=4+2
=4+suc(1)
=suc(4+1)
=suc(4+suc(0))
=suc(suc(4+0))
=suc(suc(4))
=suc(5)
=6
と証明できたことになります。

上記のプラスの3変数関数fでの定義と、今回のプラスやカケルの帰納的定義は同値ですか?
違いがあるとしたらそれは何ですか?

ちなみに、s(n)=suc(n)です。

過去の質問「1+1=2の証明って?」
http://oshiete1.goo.ne.jp/kotaeru.php3?q=217225
を精読しました。
過去の質問では、小さい自然数の定義した上で、プラスの定義を3変数関数fを使って、

●f(n,m,m)=n
●m≠kのとき、f(n,m,k) = f(s(n),m,s(k))
そして
●+(n,m)=f(n,m,0)

とされていました。

ここでは少し違って考えます。
まず、自然数(ここでは0も含める)の定義ですが、Peano's Axioms
http://mathworld.wolfram.com/PeanosAxioms.html
をみていただくとして、
自然数 a の 後者を su...続きを読む

Aベストアンサー

No.1へのコメントについてです。

> 3変数関数fでの定義は、数え上げ、かつ、記述が複雑な傾向がありそうです。
> 再帰的定義は、数え下げ、かつ、記述が簡易な傾向がありそうです。

 手続き型のプログラミングに慣れていると、再帰的な定義は分かりにくくて困るようです。手順に沿って順番にやっていくループによる操作の方がイメージしやすい。これはひとつには、「この関数は結局何をやってるのか」を知っているかどうかの違いだと思います。実際、fjfsghさんの+が足し算を意味していると分かっていて定義を見るのと、予備知識なしに意味を知るために定義を読むのとでは難しさが全く違います。 後者の場合、再帰が複数箇所に現れるともっと大変で、例えば、Ackermann関数
 A(0,n) = n+1 (n≧0のとき)
 A(m,0) = A(m-1,1) (m≧1のとき)
 A(m,n) = A(m-1,A(m,n-1)) (m≧1, n≧1のとき)
が何をやるものか、定義だけ見てもなかなか分からないでしょう。
 手続き型であるfの方は、補助変数が沢山あるので、操作に従ってナニがどう変わって行くか、ナニが変化しないかが見つけやすく、意味を(直感による帰納を使って)推測しやすいのだろうと思います。
 ですから、過去の質問「1+1=2の証明って?」において、「どういう演算を表しているか」を先に言わずに、しかも分かりやすく説明する、という目的には、fの方が適していた訳です。
 しかし、数学の対象として扱う場合には、fは冗長な補助変数を抱えているのが邪魔ですし、定義が長いので大変。再帰的な定義は数学的帰納法に素直に乗る(数学的帰納法と再帰的定義は表裏一体なのだから当たり前)。だから、再帰的定義の方が大抵便利です。

 計算可能性(計算不可能な関数とはどんなものか。真偽を決定できない命題はあるか)を論じるために、算術を手続き型のプロセスとして構築し直したのがアラン・チューリング、再帰的な関数(原始帰納関数、帰納関数)として構築し直したのがクルト・ゲーデルでしょう。
 結局、両者の方法は同等であることが示されました。これらは情報工学の基礎理論である「計算の理論(計算論、アルゴリズム理論)」と呼ばれる分野の話であり、同時に、ヒルベルトの形式主義(数学を記号の操作とみなすことによって、あらゆる定理を自動的に導く方法を構築できないか?)の(否定的な)研究、という意味を持っていて、20世紀の数学の重要な流れのひとつと言えます。
 なお、チューリングの考えた「チューリングマシン」は、あるプログラムの出力を別のブログラムに入力として与える、というやり方で複雑な計算を構成します。ゲーデルの帰納関数では、同じ事をやるのに、関数の変数に別の関数を代入する、というやり方で実現します。それぞれ手続き型のプログラミング言語と再帰型のプログラミング言語(LISP, PROLOGなど。もちろんC言語でも再帰は書けますが)の基礎になっています。

No.1へのコメントについてです。

> 3変数関数fでの定義は、数え上げ、かつ、記述が複雑な傾向がありそうです。
> 再帰的定義は、数え下げ、かつ、記述が簡易な傾向がありそうです。

 手続き型のプログラミングに慣れていると、再帰的な定義は分かりにくくて困るようです。手順に沿って順番にやっていくループによる操作の方がイメージしやすい。これはひとつには、「この関数は結局何をやってるのか」を知っているかどうかの違いだと思います。実際、fjfsghさんの+が足し算を意味していると分かっていて定...続きを読む

Qグラフを書くのが得意な方お願いします

(1)y=2X^2-4

(2)y≧x+4

グラフを書くのに標準形などに直そうとしたのですがよく分かりません、
どのように頂点や傾きを求めるのでしょうか?

Aベストアンサー

>(1)y=2X^2-4
 平方完成する。

>(2)y≧x+4
(2)y=x+4
のグラフは描かけますよね、それにyの範囲の説明を付けるだけ。

Qf(x)>0とはどういうグラフなのですか?グラフが下に凸の場合グラフが上に凸の場合それぞれ教え

f(x)>0とはどういうグラフなのですか?
グラフが下に凸の場合
グラフが上に凸の場合
それぞれ教えてください!

馬鹿な質問なんですが…

Aベストアンサー

これは、二次曲線グラフの書き方に関する問題ですね。 平方完成させると、
f(x)=ax²+4x+a
=a(x²+(4/a)x+1)
=a(x+2/a)²+a-4/a

(1)最後の4/aというものはaが0の時は計算できませんので、別途考える必要があるためです。 ちなみにa=0であればf(x)=4xですので、すべてのxで条件を満たせません。 さらにa<0の場合は下に伸びていく(上に凸)なグラフですので、条件を満たせません。 なので、a>0で原点がx軸より上にあればすべてのxにおいてf(x)>0になります。

なので、
a>0 と a-4/a>0 の双方を満たす範囲のaを求めればよいわけです。
a²-4>0
(a+2)(a-2)>0
となりますから、a>2ということになります。

(2)の場合は、一部でもx軸の上にグラフがかかっていればよいので、上に凸なグラフも含みますので、a<0の場合も考慮に入れなくてはいけないということになります。
a<0の場合は
a²-4>0 ⇒(a+2)(a-2)<0
ここの不等式の向きが逆になるのがポイントです。

Qこのグラフの中央値ってどうやって求めればいいんですか? 明日テストなので教えてくださいお願いします!

このグラフの中央値ってどうやって求めればいいんですか?
明日テストなので教えてくださいお願いします!!

Aベストアンサー

>どうやって求めればいいんですか?
 という発想だと、いつまでたっても数学は苦手のまま・・
 この問題はどうやって解くの・・・・じゃなくて、どういう意味??
  そういう意味なら、こうしたら解ける!!!
   ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄

 中央値とは、サンプルの最小値と最大値の[中央の値]
        ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
 10人でテストをして、最低点が40点で、最高点が100点満点だったら
10 20 30 40 50 60 70 80 90 100
      ←―――↑―――→
         中央の70 = (100+40)/2
 40点とった子以外の全員が、100点以上とっていても、中央値は70点
 平均点は、90.4点だけどね。

>このグラフの中央値
 もうわかるね。
 どうやって解くか・・・そんな勉強ではなく、どうやって解くかは自分で考え付くようにする。そのためには、「中央値」という言葉の意味を知る。


人気Q&Aランキング

おすすめ情報