- 締切済み
エッジ（辺）の定義について
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- jmh
- ベストアンサー率23% (71/304)
教えてください。「有向グラフ」っていうのは、ａ1からａ2への矢印は、複数本はないモノなの？
- stomachman
- ベストアンサー率57% (1014/1775)
ノードの集合Aに対して、エッジの集合Eは E⊂A×A と定義されます。A×Aとは A×A = {<x,y>| x∈A ∧ y∈A} ですから、エッジeはノードx,yの順序対<x,y>です。 ∀e(e∈E ⇒ ∃x∃y(x∈A ∧ y∈A ∧ e = <x,y>)) 一方、Eはノードからノードへの写像 E: A→A と見ることもできます。なぜなら E: A→A とは E⊂A×A のことに他ならないからです。
関連するQ&A
- ４色定理はなぜグラフ理論で証明できないのでしょうか
４色定理についてですが、引っかかるところがあります。 現在はコンピュータで量的な証明がなされていると聞きますが、グラフ理論で証明されたという話は聞きません。 私の中ではグラフ理論で簡単に説明できるのではないかな、という甘い考えがあります（内容は下記に記載しました）。 ただ、こうした考えは以前もたくさんあって否定されているのだと思います。そこで何が悪いのかを教えて頂きたいのです。 納得できる回答が無かった場合は、私は私の考えが正しいんじゃないかと思っているので、私の胸の内で「私の考えで正しいのだ」と自己完結しようと思います。 この質問の内容は、「下記のようなグラフ理論の考え方で5色の塗りわけは無理＝４色の塗りわけで事足りるので、二次元における地図の塗りわけは４色が最大値であり、４色でことたりる」ということの説明ではどこか不足があるのだろう、その不備を教えて頂ければ、というのが論旨となります。 内容は極めて簡単なのですが、文章が少々難しくなってしまいました。ですが、どなたかお付き合い頂ける方、この論旨の問題点をご存知の方、あるいは少しでもこうではないかとおっしゃって頂ける方がいらっしゃいましたら教えて下さい。 尚、万が一の可能性として「こりゃ世紀の大発見也」みたいなこともあるかもしれませんが（とは言いつつも全く期待してません。まあ、今この文章を書きながら自分自身に笑っていますが）、賛同頂ける方、欠点は無い、と言う方もいらっしゃいましたら教えて下さい。 しかし私自身モヤモヤしているのも事実なので、これが正しいのか穴があるのかを教えて頂きたいのです。 ＜序論＞ 例えば、二次元平面に描かれた任意数のノードとエッジで観察するとき、地図でのいわゆる４色定理の観点から見ると、ノードが国、エッジが国境になります。 もともと４色問題の根源は、地図での色塗りの組み合わせにおいて、本当に必要な色の数として４色が最大値なのか、５色必要なパターンは無いのか、という点が論点であると私は考えています。 つまり、これをグラフ理論から見れば、 ・塗りわけが必要なのは、ノードがエッジによって接続されているケース であり、４色が必要なものは ・４つのノードが「全て」４つともエッジによって接続されているケース を想定するものです。 そして５色が必要なものは ・５つのノードが「全て」５つともエッジによって接続されているケース を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。 ＜前提などの説明＞ まず根源的な前提として、エッジを延ばすことのできる条件とはなんでしょうか？ それはノード間において遮蔽物が無いことです。遮蔽物が無いという状況はどんな状況でしょうか。 逆に言えば遮蔽物とは何か、ということなのですが、この地図塗りわけの問題をグラフ理論に適用すると、閉路グラフの「内部」にノードＡを一つプロットし、「外部」にノードＢをプロットします。 今回は地図塗りわけの問題をグラフ問題に展開していますので、エッジ間の交差はありません。 ですので、閉路グラフの内と外にプロットされているノードＡとＢは直接エッジで接続することはできない、というのが前提となります。 三次元での考えではこれらは無視できるのですが、今回は地図塗りわけがお題となるので、二次元平面上での問題となります。 ＜本論＞ 序文にも書きましたが、 ・５つのノードが「全て」５つともエッジによって接続されているケース を想定し、これが存在しないことを証明すれば、塗りわけの最大色数は４ということになります。 まず一つずつ考えて生きます。 １．２つのノードの場合 →存在するノードが互いに全てエッジによって接続されている。 ○－○を想像して頂ければＯＫです。 この場合２色必要になります。 ２．３つのノードの場合 →存在するノードが互いに全てエッジによって接続されている。 正三角形の頂点に○をくっつけた図を想像して頂ければＯＫです。 この場合３色必要になります。 ３．４つのノードの場合 →存在するノードが互いに全てエッジによって接続されている。 正三角形の頂点に○をくっつけて、その中央に○を描き、 それらが全て互いに接続されている図を想像して頂ければＯＫです。 ４つのノードが互いに全てエッジによって接続されているケースはトポロジー的に必ずこのようになると思います。 この場合４色必要になります。 ４．５つのノードの場合 さて、それでは５つのノードが互いに全てエッジで接続されるケースを考えてみましょう。 実は上記３．「４つのノードの場合」で閉路グラフが構成されており、どこに５つ目のノードをプロットしようとも、その閉路の中の全てのノードにエッジを届かせることはできません。 ここでは前提として頂点Ａ、Ｂ、Ｃからなる正三角形と、その中央に位置する点Ｄ、そしてこれらの点をノードとし、全て互いにエッジで接続しあったグラフを用います。 そして５つ目の点Ｅを任意の位置にプロットし、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できたなら、地図の塗りわけとして５色必要、こうしたモデルがグラフでできないと証明できたなら５つは必要でなく、地図の塗りわけとしての最大必要色数は４色ということになります。 点Ｅを置く位置としてはグラフ図中の任意の位置となりますが、これを分類すると （１）三角形ＡＢＣの外に点Ｅを置く場合 （２）三角形ＡＢDの内側に点Ｅを置く場合 （３）三角形ＡCDの内側に点Ｅを置く場合 （４）三角形BCDの内側に点Ｅを置く場合 の４種に分けられると思います。 これを一つずつ見ていきましょう。 （１）三角形ＡＢＣの外に点Ｅを置く場合 点Ｅは、三角形ＡＢＣに構成される閉塞グラフの内側にある点Ｄにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 （２）三角形ＡＢDの内側に点Ｅを置く場合 点Ｅは、三角形ＡＢＤに構成される閉塞グラフの外側にある点Ｃにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 （３）三角形ＡCDの内側に点Ｅを置く場合 点Ｅは、三角形ＡＣＤに構成される閉塞グラフの外側にある点Ｂにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 （４）三角形BCDの内側に点Ｅを置く場合 点Ｅは、三角形BＣＤに構成される閉塞グラフの外側にある点Ａにエッジが届かない。 よって点Ｅのこの位置のプロットでは、ノードのＡＢＣＤＥが５つ全て互いにエッジで接続できない。 以上のことからノードのＡＢＣＤＥが５つ全て互いにエッジで接続できるグラフは存在しない。よって地図塗りわけに対しての必要な最大の色数は４色である。 尚、数学的哲理的考察としては、任意ノード数で、互いに全てのノードをエッジで接続するケースを考えた場合、三つのノードで閉路グラフが形成され、四つ目のノードで「その閉路グラフの内側か外側に」プロットされてしまう。更に上記の例で言えばこの四つ目のノード自体をプロットすることにより、閉路グラフがＡＢＣ、ＡＢＤ、ＡＣＤ、ＢＣＤと四つ形成されてしまう。そしてそこから追加のノード点Ｅをどこに打とうとも、閉路グラフの内側に点Ｅを打てばその外側に、閉路グラフの外側に点Ｅを打てばその内側に、自分とは異なるノードが存在するので、点Ｅからそこのノードに到達するエッジを延ばすことはできない。 となります。 実は、数年前もここで同じような質問をさせて頂いたことはあります。ただ、その時に納得できたように思われたのですが、やはり何か私の心の中でモヤモヤしているものがあったので、再度の質問をさせて頂くことにしました。 どなたかご教授頂ける方がいらっしゃいましたら、宜しくお願い致します。
- 締切済み
- 数学・算数
- 数学的な記法
以下、数式をtex記法で表記します。 アルゴリズムを表記するにあたって困っていることがあります。 有向グラフにおいて、ある節v1を始点・ある節v2終点とする辺は e_{v1,v2} またその逆方向は e_{v2,v1} と書けて e_{v1,v2}≠e_{v2,v1}ですよね。 では無向グラフにおいて、ある節v1とある節v2を結ぶ辺を表記するにはどうすればよいでしょうか。 e_{a,b}とe_{b,a}は同じ辺を表すものとする というような注意書きを入れて e_{v1,v2} と表すしかありませんか。 こういった場合に使うべき数学的な記法がわかりません。 うまく説明できているか心配ですがアドバイスをお願いします。
- 締切済み
- 数学・算数
- ネットワーク図のデータベース設計
データベースのテーブル設計を考えています。 多数の「ノード」があり、「エッジ」（そのノード同士の関係）をデータベースに記録したいと思っています。 例えば、A, B, C, D, E という5つのノードがあり、 「AとBは関係がある(関係の分類：X)」 「BとCは関係がある(関係の分類：X)」 「CとDは関係がある(関係の分類：X)」 「DとAは関係がある(関係の分類：X)」 「AとEは関係がある(関係の分類：Y)」 「BとDは関係がある(関係の分類：Z)」 という事を表現したいのです。 図：等幅フォントでないと崩れてしまうと思いますが、一応…。 E +---+ | | | A-B-C-D | | +-----+ ここで私が考えたのは、テーブル「node」と「edge」を用意します。nodeには、"ノードID", "ノード名"(A～E等) フィールドを作り、edgeには "ノードID1", "ノードID2", "関係" フィールドを作ります。 node : 1, A 2, B 3, C 4, D 5, E edge : 1, 2, X 2, 3, X 3, 4, X 4, 1, X 1, 5, Y 2, 3, Z このように記録しておけば、ネットワーク図をデータベース化することができると思います。 ただ、この場合、edgeテーブルで 1,2,X と 2,1,X は、同じ関係を違う表現で表記してしまうので、混乱の元になってしまいそうです。また、edgeテーブルから「Aと関係があるノードをリストアップしたい」場合も、何だかスマートではない気がするのです。 こういった事例では、どのようにデータベースを設計すると良いのでしょうか？ # MySQLカテゴリで質問させて頂きましたが、Postgresの独自機能により解決できるパターンもありましたらご指摘頂ければ幸いです。
- ベストアンサー
- MySQL
- 「比」の正確な定義
普段何気なく使っている「比」の正確な定義について調べてみたのですが まったく見つけられませんでした。 「比（ひ）とは2つ（または3つ以上）の数の関係を表したもの」 といった記述がありましたが、曖昧でこれで定義できたとは到底言えません 比が持つ性質についても説明できていませんし 数のどの範囲で定義するかも説明されていません 「aとbは０でない実数とする aとbの比 とは a/bのことである。 a:bと書く」 こういった記述も良く見ます。これは↑の定義よりは遥かに優れていると思います 比の等式の a:b＝ka:kb は真である a:b=c:d ⇔ a/b=c/d ⇔ ad=bc といった振る舞いも説明できますし 数のどの範囲で定義されるかも明記されています。 しかしa:bという表記の他に a:b:cやa:b:c=x:y:zといった表記が存在しますよね？ この定義はその表記を説明できません。 よって実用上ですら完全であるとは言えません。 比の正しい定義と、定義する数の範囲について教えてください
- ベストアンサー
- 数学・算数
- 余因子行列と逆行列
行列Aの余因子行列を(~A)とすると(A^-1)=(1/|A|)(~A)のときA(A^-1)=Eとなることの証明ですが、行列A,行列(~A)、この2つの行列の積の(i,j)成分をCijとおくとCij=ai1Aj1+ai2Aj2+・・・+ainAjn(i=1,2,3,・・・,n,j=1,2,3,・・・,n)となる。 (1)i=jのときCii=|A|となる (2)i≠jのときcij=ai1Aj1+ai2Aj2+・・・+ainAjn(i≠j)となり、これは、行列式の第j行による余因子展開の式になっているが、その第j行の成分が[ai1 ai2 ・・・ ain] となって、第i行の成分と一致していることになるので第i行と第j行が同じ成分の行列式となるので、これは0となる。 とありますが(2)の第j行の成分が 第i行の成分と一致していることになるというのが理解できません。実際にAjnがある値を持ったとすると、AinとAjnが等しい値でなかったとしても cij=ai1Aj1+ai2Aj2+・・・+ainAjnがciiと等しいと言えるのでしょうか？ どなたか詳しく教えて頂けないでしょうか？
- ベストアンサー
- 数学・算数
- ブルバキをお読みになったことがある方に質問です。
一章の構成法則や理論における代入、演繹法則の証明で ”順次示していく””・・・を仮定して・・・”のような文があります。 この論理が正当化されるのは、ここでの記号列の列が有限であることから、 記号列AがAより前の記号列Bをもちいて書かれている ということが無限に続くことが無いことから・・という事実があるからだと 思われますがもっとスマートな説明のしかたはないでしょうか？ 構成法則や理論における代入ではこれをつかわない証明をかけるのですが、演繹法則のほうはできませんでした。もし演繹法則の証明でこの証明法を使わないものがあるなら解決するのですが。 例 Aを理論Tにおける関係式[対象式]、xおよびyを文字とする。このとき(y|x)Aは、Tにおける関係式[対象式]。 例の証明 A1,A2,・・・,An を構成手続きとし、そのなかにAがあらわれるものとする。Atを関係式[対象式]とし、 (y|x)Atが関係式であることを順次しめしていく。このことがA1,A2,・・・A(i-1)に対しては証明されたと仮定してAiに対して証明する。Aiが文字ならば、(y|x)Aiは文字。構成手続き中でAiよりまえに関係式Ajがあり、かつAiが￢Ajならば(1)によって(y|x)Aiは￢(y|x)Ajと一致し、￢(y|x)Ajは(2)によって関係式。 （V,特殊記号s,τについても同様） (1)(y|x)￢Aは￢(y|x)Aと同じ (2)Aが理論Tの関係式のとき、￢AはTの関係式
- 締切済み
- 数学・算数
- 【離散数理・2項関係】
【2項関係】 次の問いの答えを教えてください。 次の2項関係は反射性、対称性、反対称性、推移性、半順序性、全順序性のどれを満たすか。 １）ｘとｙが英単語のとき、ｘRｙはｘはｙよりも辞書の配列順で前にある。 ２）有向グラフG＝（V,E）において点aから点bに有向路があるとき、aRbとする。 ３）無向グラフG＝（V,E）において点aから点bに路があるとき、aRbとする。 よろしくお願いします。
- 締切済み
- 数学・算数
- 定義はどこまで可能ですか？
初歩的な質問です。 科学全般に言えることですが、哲学的思考は言葉を定義できないと正確な議論ができません。 辞書をパラパラひも解くと、 【定義】ある概念の内包を構成する諸属性のうち、本質的な属性を挙げることによって、他の概念から区別しその内包を限定すること。 とあります。 では、とまた見ると、 【概念】事物が思考によって捉えられたり表現される時の思考内容や表象、またその言語表現の意味内容 【属性】それを否定すれば事物の存在そのものも否定されてしまうような性質 【本質】存在者の何であるかを規定するもの これを一部乱暴に置き換えると、 【定義とは】「ある事物が思考によって捉えられたり表現される時の思考内容や表象、またその言語表現の意味内容」の内包を構成する諸々の「それを否定すれば事物の存在そのものも否定されてしまうような性質」のうち存在者の何であるかを規定するものの属性を挙げることによって、他の概念から区別しその内包を限定すること。 分かりやすいような呪文のような言葉になります。 さらにこの文章を緻密に「定義」していくと、さらにエンドレスです。 さらに「真理」だの「永遠」だの「存在」だのを定義しても同じようなジレンマに陥ると思います。 と言う事は、定義は重要でありつつも、どこかで「まあ、だいたいこう意味だと。」と妥協しないと、いつまで経っても肝心の思考が始まらず、言葉の定義作業だけで終わってしまいます。 とどのつまり、哲学にとって定義とは何なのでしょうか？ 。
- ベストアンサー
- 哲学・倫理・宗教学
- 国の定義
質問です。 一般的な国の定義って、宇宙単位で考えても通用しますか？ A連星をA国 B銀河腕をB国 C銀河をC国 D銀河群をD国 E領域をE国 F点からG点をFG国 よろしくお願いします。
- 締切済み
- その他（人文・社会科学）
