平面グラフの直線描画について
- 完全グラフの描画について、正三角形と長方形を例に説明します。
- 正三角形の場合は、各頂点とその重心を頂点とすれば、線分で描くことができます。
- しかし、完全グラフK5以上の場合は平面グラフにはなりません。頂点以外で曲がったりカーブしたりしない描画方法は存在しないかもしれません。
- ベストアンサー
平面グラフは直線だけで描けるか？
頂点を３つもつ完全グラフK3は、正三角形の各頂点に頂点をおけば、そして、それを直線(線分)で結べば、その線分は正三角形の辺になります 頂点を４つもつ完全グラフK4は、長方形の各頂点に頂点をおけば、そして、それを直線(線分)で結べば、長方形の辺と対角線になります。しかし、対角線は交差してしまうので、どちらか一方を迂回させて(線分でなく)描くことになります。 しかし、正三角形の各頂点とその重心を頂点とすれば、線分の長さは２種類になりますが、K4でも線分で描けます。 頂点を５つもつ完全グラフK5は平面グラフにはなりません。それ以上の完全グラフでも平面グラフにはなりません。 そこで質問です。完全グラフに限らず、どんな平面グラフでも、変形さえすれば、頂点以外で曲がったりカーブしたりすることなく、描くことはできるのでしょうか？
- corpus
- お礼率79% (330/414)
- 数学・算数
- 回答数2
- ありがとう数3
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
ちょうど手元にあった本を見ただけで, web とかを参考にしたわけではないんですが.... 「グラフ G が平面的 ⇔ G には K5 も K3,3 もマイナーとして含まない」 という有名な定理があるんですが, その証明方法 (の 1つ) として [1] K5 も K3,3 もマイナーとして含まない, 5点以上の 3連結グラフは平面的 [2] K5 も K3,3 もマイナーとして含まない 5点以上のグラフは, 隣接していない 2点をうまく選ぶとその間に辺を加えて得られるグラフにはやっぱり K5 も K3,3 もマイナーとして含まれない という 2つの命題を組合せる, というのがあるんですが, [1] を証明するときに実際に平面にグラフを描いていて, その描き方をよく見ると「単純グラフならどの辺も直線分で描ける」ことがわかるわけです. 手元で参考にした本は Bernhard Korte and Jens Vygen, Combinatorial Optimization, Springer ですが, グラフ理論の本で上の [1] を証明しているのがあれば多分どの本でもよいかと思います.
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
ちょいと調べてみましたが, 単純な (つまり自己ループや並行辺を持たない) 平面的グラフは直線分だけで平面上に描くことができます.
お礼
回答ありがとうございます。参考ＵＲＬも教えていただければと。
関連するQ&A
- 平面グラフの問いです。
平面グラフの頂点（節点）を凹凸多角形に、頂点連結用の辺（稜）を凹凸多角形の境界線に、それぞれ変換したとします。 その場合、元の平面グラフの連結性と、変換後の凹凸多角形の境界線共有性とは、同値になりますか。 つまり、平面グラフ頂点の彩色問題を、４色問題のような地図色分け問題に、変換できますか。
- ベストアンサー
- 数学・算数
- 平面上に四角形ABCDがあって、
平面上に四角形ABCDがあって、どの頂点も、残りの頂点の作る三角形の外部にある。△BCDの重心をA1、△CDAの重心をB１、△DABの重心をC1、△ABCの重心をD1とする。 （１）線分AA1、BB1、CC1、DD1は１点Pを共有することを示せ。 （２）（１）において、点Pは各線分をどのような比に分けるか。
- 締切済み
- 数学・算数
- にゃんこ先生の自作問題、シュターナーの定理、カヴァリエリの原理を使った等積変形
にゃんこ先生といいます。 空間にある４頂点でできた四面体とその体積を考えます。 カヴァリエリの原理とは、二つの立体図形を平面で切った切り口の面積が常に等しければ、体積も等しい、というものです。 つまり、四面体の３頂点をテーブルに接するように置き、残りの頂点をテーブルと水平に移動させても、変形する四面体の体積は同じです。 シュターナーの定理とは、四面体の一辺をその長さを固定したまま、その辺の方向にずらしても、体積は変わらないというものです。 別の言い方をすれば、ねじれの位置にある２本の直線を考え、それぞれの直線上に決まった長さの線分をとる。このとき、２線分から四面体ができるが、その体積は、線分の位置によらず一定。 http://mathworld.wolfram.com/SteinersTheorem.html の三番目参照。 この２種類の等積変形の片方、または、両方を使って、例えば、「立方体の一つの頂点と、隣り合う３頂点を取ってできる四面体（直角二等辺三角形の面が３つと、正三角形の面が１つ）」を、正四面体に変形することはできるのでしょうか？ または、任意の四面体を別の任意の四面体（ただし、同体積）に変形することはできるのでしょうか？
- 締切済み
- 数学・算数
- にゃんこ先生の自作問題・シュターナーの定理・カヴァリエリの原理を使った等積変形
にゃんこ先生といいます。 空間にある４頂点でできた四面体とその体積を考えます。 カヴァリエリの原理とは、二つの立体図形を平面で切った切り口の面積が常に等しければ、体積も等しい、というものです。 つまり、四面体の３頂点をテーブルに接するように置き、残りの頂点をテーブルと水平に移動させても、変形する四面体の体積は同じです。 シュターナーの定理とは、四面体の一辺をその長さを固定したまま、その辺の方向にずらしても、体積は変わらないというものです。 別の言い方をすれば、ねじれの位置にある２本の直線を考え、それぞれの直線上に決まった長さの線分をとる。このとき、２線分から四面体ができるが、その体積は、線分の位置によらず一定。 http://mathworld.wolfram.com/SteinersTheorem.html の三番目。 この２種類の等積変形の片方、または、両方を使って、例えば、「立方体の一つの頂点と、隣り合う３頂点を取ってできる四面体（直角二等辺三角形の面が３つと、正三角形の面が１つ）」を、正四面体に変形することはできるのでしょうか？ または、任意の四面体を別の任意の四面体（ただし、同体積）に変形することはできるのですか？
- ベストアンサー
- 数学・算数
- 図形ソフトが得意なお方へ。平面にある２つの直線のそれぞれから１点をとるとき、正三角形となる残りの頂点の存在領域の形状。
素朴な疑問です。 平面（もしくは空間）に３つの直線がある。それぞれから１点をとってきて、正三角形を作れるのでしょうか？ 作れるとしたら、具体的にどういった点を選べばよいのでしょうか？ さらに、平面（もしくは空間）に２つの直線があったとき、それぞれから１点をとって、それを１辺とする正三角形の残りの頂点を選ぶ。その頂点の存在可能な領域はどういった形状をしているのでしょうか？ 座標を用いて考えましたが、複雑すぎて最後まで導き出せませんでした。 コンピューターソフトで図形を描くことが得意な方は、よろしければ描いていただけると助かります。
- ベストアンサー
- 数学・算数
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフ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は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- 座標平面上に１辺の長さが２の正三角形ABCがある。
以下の問題の（２）の解説で２つ疑問があります。 １）解いた時に、△A'B'C'が重心（原点）を中心に動くことに気付きませんでした。気付く方は、どうして or どのような考察をして気付くのでしょうか？ ２）△ABCと△A'B'C'が重ならない部分 （例えば、線分ABと線分A'C'の交点をD,線分ABと線分C'B'の交点をEとした場合、△C'DE）が直角3角形になることに、どのようにして気付くのでしょうか？ 問題）座標平面上に１辺の長さが２の正三角形ABCがある。 ただし、△ABCの重心は原点の位置にあり、辺BCはx軸と平行である。 また、頂点Aはy軸上にあってy座標は正であり、頂点Cのx座標は正である。 直線ｙ＝ｘに関して３点A,B,Cと対称な点を、それぞれA',B',C'とする。 （１）C'の座標を求めよ。 （２）△ABCと△PQRが重なる部分の面積を求めよ。 解答）△ABCと△A'B'C'は、合同な３角形であり、△ABCを原点の周りに30度回転すると△C'B'A'と一致する。ゆえに、△ABCと△A'B'C'が重なる部分から，はみ出した６個の直角３角形は、すべて合同である。（以下省略）
- 締切済み
- 数学・算数
- 座標ポイントによるグラフの描き方
エクセルで長方形のグラフを描きたいと思っています。 座標の求め方がわからず困っています。 わかっているのは長方形の４辺の長さと対角の長さのみです。 座標の求め方を教えてください。 ４点のうちどこを原点にしても構いません。 宜しくお願いします。
- 締切済み
- その他MS Office製品
お礼
アドバイスありがとうございます。