グラフ理論の頂点に関する性質についての証明
- 全ての２頂点ｖ1,v2∈Gについて、ある一つの頂点ｗ∈Gが存在しｖ1とｗは隣接していて、かつ、v2とｗも隣接しているようなグラフGを考える。
- （a)ｖ∈Gとｗが非隣接ならばδ(ｖ）＝δ(ｗ）を証明せよ
- （b）ある頂点の次数ｋ＞１かつどの頂点にも隣接しているような頂点は一つもない時、すべての頂点の次数はｋになることを証明せよ
- ベストアンサー
グラフ理論の頂点に関する性質についての証明
全ての２頂点 v1,v2∈Gについて、ある一つの頂点ｗ∈Gが存在しｖ1とｗは隣接していて、かつ、v2とｗも隣接しているようなグラフGを考える。このとき・・・ （a)ｖ∈Gとｗが非隣接ならばδ(ｖ）＝δ(ｗ）を証明せよ （b）ある頂点の次数ｋ＞１かつどの頂点にも隣接しているような頂点は一つもない時、すべての頂点の次数はｋになることを証明せよ の２問について証明の仕方を教えていただけると助かります。問題の状況がそもそもわかりません・・・（δはその頂点から出ている辺の数） もとの問題が英文なのでそっちも載せておきます。 Let G be a graph. Suppose that for every pair of distinct vertices v1 and v2 in G, there is a unique vertex w in G such that v1 and w are adjacent and v2 and w are adjacent. (a) Prove that if v and w are nonadjacent vertices in G , then δ(v)＝δ(w). (b) Prove that if there is a vertex of degree k>1 and no vertex is adjacent to all other vertices, then the degree of every vertex is k.
- ringoss
- お礼率35% (6/17)
- 数学・算数
- 回答数2
- ありがとう数2
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
証明しちゃう方が早いかも (苦笑) v と w は隣接しないとします. このとき, 条件から「v と w の両方に隣接する頂点」は唯一存在します. これを u としましょう. v に隣接する頂点が u のみであれば, この時点で δ(v) ≦ δ(w) が証明できます. ということで, v に隣接する頂点が u の他にあるとしましょう. それらを x1, x2, ..., xk とします. さて, 全ての i に対し「xi と w の両方に隣接する頂点」が唯一に存在します. それを yi としましょう. ここで問題: 「i≠j だが yi = yj」ということはありえるでしょうか?
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
原文の「unique」を意識して訳すようにしてください. たぶんこれでいいと思うけど概略だけ: (a) 「v に隣接する頂点」と「w に隣接する頂点」の間に適切な対応を与えて δ(v) ≦ δ(w) を示す. 「v と w が隣接しないこと」も証明の中で使います. (b) v, w を隣接しない頂点とすると (a) より δ(v)=δ(w). この v, w に対して「両方に隣接する頂点」を u とすると, u 以外のすべての頂点が「v と w の少なくとも一方とは隣接しない」ことが分かります. そして, その中には u と隣接しない頂点が必ず存在します.
お礼
回答ありがとうございます。 （a)の適切な対応をもう少し教えていただけるとありがたいです。
関連するQ&A
- 英文を日本語に翻訳したいと思っています
英文を日本語に翻訳したいと思っています 数学のグラフをテーマにした英文です ※の部分だけで結構なのですが、私の訳はこうです 「辺はもし頂点ｖが辺の端点ならば範囲を含みます」 どうでしょうか？ incident withを上手く訳せたような気がしません ・Adjacency and Incidence Two vertices v and w in a graph are adjacent if an edge runs between them; if a loop occurs at v, v is adjacent to itself. An isolated vertex is not adjacent to any vertex. Adjacent edges have a common vertex. ※An edge is incident with a vertex v if v is an endpoint of the edge.
- ベストアンサー
- 英語
- 行列の証明問題
1. Suppose A is positive definite and symmetric. Prove that all the eigenvalues of A are positive. What can you say of these eigenvalues if A is a positive semidefinite matrix? 2. Prove that the sum of two symmetric positive definite matrices A, B ∈ Rd×d is positive definite. 3. Prove that if A is symmetric positive definite, then det A > 0 and thus A is invertible. On the contrary, show that if det A > 0, then A is not necessarily positive definite (you just need to provide a counterexample). 4. Prove that if A is positive semidefinite and λ > 0, then (A + λI) is positive definite. 5. Prove that if X ∈ Rd×n then XXT and XT X are both positive semidefinite. 6. Prove that if X ∈ Rd×n has rank d, then XXT is positive definite (invertible). 7. Let X ∈ Rd×n be a matrix, and Y ∈ Rn. Prove that minα∈Rd∥XTα－Y∥2 +λ∥α∥2 is attained for α = (XXT + λI)－1XY .
- 締切済み
- 数学・算数
- 隣接角について
こんにちは、 英文交じりの質問で申し訳ないのですが、宜しくお願い致します。 隣接角（Adjacent Angles）の定義は知ってます。 そして、隣り合ってる角の合計は１８０ ° まで、と解釈してます。 （Adjacent Angles Two angles are Adjacent if they have a common side and a common vertex (corner point) Adjacent angles add up to 180 degrees.） が、図のaからdまでの角度の合計がa + b + c + d = 360 ° の証明に adj ∠’s at a point sum to 360 °となってるのをみました。 隣接角は１８０度までなのに理解できません。それとも”adj ∠’s at a point sum to 360 °”は間違っているのでしょうか？ どなたか説明して頂けますか？
- ベストアンサー
- 数学・算数
- ハミルトングラフの証明
単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。
- 締切済み
- 数学・算数
- 帰納法の証明で後一歩
帰納法というんでしょうか、証明する問題を解いていますが後一歩でどうすればよいのか分かりません。 というか自分のやったところも書き方とかあっているかどうか分かりません。 問題の"any graph"というのも引っ掛かります。 Cycleが含まれるグラフだとVよりも大きくなるような気が…。 これがその問題です。 Let G = (V, E) be any graph. Prove the following claim: If there is any walk between vi ∈ V and vj ∈ V, then there must be a path of length no larger than |V|-1 between these two vertices. G = (V, E)はどんなタイプのグラフでもよいとする。次の主張を証明せよ: もしvi ∈ Vとvj ∈ Vの間にいくらかの歩行距離があれば、それらの二つの頂点の間には|V|-1よりも大きくない(つまり|V|-1よりも小さいか等しい)長さの経路が存在するはずである。 ※ちなみに|V|はVの絶対値ではなく、Vの全体の長さです。例えばV={v1, v2, v3}であれば|V|=3です。 自分のやったところまで書きます。 証明: もしvi ∈ Vとvj ∈ Vの間にいくらかの歩行距離があれば、 |(vi, vj)| <= |V|-1 であることを証明したい。 根拠: P(1)は真である、なぜなら |(v1, v2)| <= |{v1, v2}|-1 1 <= 2-1 1 <= 1 帰納的仮定: P(K)が真だと仮定すると |(v1, v2)(v2, v3)(v3, v4), ... ,(v_K-1, v_K)| <= |K|-1 そしてP(K+1)が真であることも証明しないといけないので |(v1, v2)(v2, v3)(v3, v4), ... ,(v_K-1, v_K)(v_K, v_K+1)| <= |K+1|-1 …これからどうすればいいのか分かりません。 |K+1|-1の部分はそのまま1をプラスマイナスして0なので |K|でいいと思うんですが、それが私の出来る精一杯です。 これからどうすればいいのか教えてください。
- 締切済み
- 数学・算数
- 楕円曲線上スカラー倍算のwidth-w NAF性質の証明について！
この間以下の論文を読みましたけど、なかなか納得できなくて、困っています。だれが教えていただけませんか。よろしくお願いします。 Minimality and Other Properties of the Width-w Nonadjacent Form (2004)http://citeseer.ist.psu.edu/648299.html 2.1. Uniqueness. Proposition 2.1. Every integer has at most one w-NAF. Proof. We suppose the result is false and show that this leads to a contradiction.Suppose there are two di erent w-NAFs, say (a_{l-1}... a_2a_1a_0)_2 and (b{l'-1}...b_2b_1b_0)_2, such that(a_{l-1}... a_2a_1a_0)_2 and (b{l'-1}...b_2b_1b_0)_2, where l and l' are the respective lengths of these representations. We can assume that l is as small as possible. These representations stand for the same integer, callit n. (###---###の部分がわかりません、この以後は理解できると思います。) ### If a0 = b0, then (a_{l-1}... a_2a_1)_2 and (b{l'-1}...b_2b_1)_2 and so we have two different, and shorter, w-NAFs which stand for the same integer,contrary to the minimality of l. So, it must be that a_0≠b_0. ### If n is even then a0 = b0 = 0. However, a_0≠b_0, so it must be that n is odd;hence, both a_0 and b_0 are nonzero. Because the representations are both w-NAFs, we have (a_{l-1}... {a_w}00...0a_0)_2 and (b{l'-1}...{b_w}00...0b_0)_2 ==> a_0=b_0 (mod 2^w). However, -(2^{w-1}-1)<=a_0, b_0<=2^{w-1}-1, and thus -2(2^{w-1}-1)<=a_0,b_0<=2(2^{w-1}-1): The only multiple of 2^w in this range is 0, and since 2^w|(a_0-b_0) it must be that a_0-b_0 = 0. However, this contradicts the fact that a_0≠b_0. Thus, the representations cannot exist and the result follows.
- 締切済み
- 数学・算数
- 和訳に関する質問です
和訳に関する質問です 私の訳はこうです ｎ頂点を持つGの様なグラフのトポロジー指標は異なるやり方での合計でグラフを全ての辺と確実にｋ辺をもつ互いに素な部分グラフに分割できます。ただしk≧0です。 文法、訳す単語の順番は大丈夫でしょうか？ The topological index of such a graph G with n vertices is the total number of different ways the graph can be partitioned into disjoint subgraphs containing all vertices and exactly k edges, where k≧0.
- ベストアンサー
- 英語
- 大学の数学の問題
かなり難しく困っております。ぜひよろしくお願いします。 1: dimＲ＾ｎ＝ｎ 2: dimＣ＾ｎ＝ｎ 3: Show that Ψ・φ：Ｕ→Ｗ is a linear map if φ：Ｕ→Ｖ and Ψ：Ｖ→Ｗ are linear maps. 4: Let a map φ：Ｕ→Ｖ be an isomorpism, and let a set(e1,...,ek),eiＥＵ be linearly independent. Then show that a set (e"1,...,e"k),e"i=φ(ei)ＥＶ is linearly independent.
- ベストアンサー
- 数学・算数
お礼
証明できました。ありがとうございました＾＾