ベストアンサー グラフの極大マッチングが、その頂点被覆集合である理由は何ですか? 2010/06/08 10:24 グラフの極大マッチングが、その頂点被覆集合である理由は何ですか? よろしくお願いします。 みんなの回答 (1) 専門家の回答 質問者が選んだベストアンサー ベストアンサー Tacosan ベストアンサー率23% (3656/15482) 2010/06/08 12:04 回答No.1 「極大マッチング」や「頂点被覆集合」をどのように定義していますか? 通報する ありがとう 0 カテゴリ 学問・教育数学・算数 関連するQ&A 図のような6個の頂点からなる無向グラフがある。この 図のような6個の頂点からなる無向グラフがある。このグラフ上を動く離散時間ランダムウォークを考える。時刻tで頂点iにいるとき、iを始点とする辺の中からランダムに選択し、時刻t+1で、選択した辺の終点jの位置に移 動する。例えば、頂点1にいるとき、それまでの軌跡とは独立に確率1/2で頂点2又は6に移動する。頂点1からスタートしたとき、初めて同じ頂点1に帰ってくるまでの時間の期待値は8となるそうですが、その理由がわかりません。どなたか教えて下さいませんか。 折れ線グラフの頂点 折れ線グラフの各頂点のことをなんというのでしょうか? each top point となるのでしょうか? グラフが空集合とグラフが存在しない 集合の本に、「(写像の)グラフが空集合である」ことと「グラフ(や写像)が存在しない」ことは区別しなければならなく、「グラフが存在しない」に当たるのは、「グラフ全体からなる集合が空集合である」と書いてありました。 グラフが空集合に等しいということは空集合という集合としてグラフが存在していることだと理解していますが、 グラフが存在しないということについては理解できません。 どなたかご教授下さい Excellのグラフ頂点に文字を入れたいのですが・・・ 初めまして。現在、Excell(2003)で論文作成中の学生です。 早速質問なのですが、Excellの横棒グラフのグラフ頂点に文字を入れたいのですが、何か手っ取り早い方法はないでしょうか? 詳しい説明をすると、1つのグラフにつき20本ほどの棒の頂点1つ1つに、それぞれ統計解析結果の文字列(aとかbとかだいたい1、2文字)を書き込みたいのです。 現在のところ、オートシェイプでテキストボックスを作成し、それに文字を入れて、グラフ頂点の位置に移動させ、グラフを最後面にする形で作業していますが、この方法だと少し時間がかかってしまうので、何か他によい方法があれば是非、ご教授お願いします。 開集合がコンパクトでない理由 コンパクトとは、有限と無限に関するもの(有界閉集合)である ことは何となく分かっているつもりです。 しかし、開集合がコンパクトでない理由がいまいち分かりません。 たとえば、よく教科書に掲載されている例として 開区間(-1,1)を、Xn=(-n/(n+1),n/(n+1)) (n∈N) ※Nは自然数全体 で覆うというものがあり、これは有限部分被覆を持たないというものです。 でも、Xnの最後は(-1,1)なので、この一つをとりだせば それだけで有限被覆となると思います。 この矛盾はどこから来るのか分かりません。 どなたか、ご教授ねがいます。 グラフ理論の問題 ちょっとした定理なのですが… Vを頂点集合としてKをVの部分集合とする。KがグラフGのクリークをなすための必要十分条件は、V-K がGの補グラフG^の頂点被覆になることである。 図で証明は出来るのですが、数式ではキビシい感じなんです。 これは一体どうすれば宜しいのでしょうか? 2部グラフの最大マッチングの求め方 2部グラフの最大マッチングを求める方法が, あらゆる資料で学習してもどうしても分かりません. ※類似した質問の回答を見ても納得することができませんでした. 特に,補充パス(増大道)に関して 大変恐れ入りますが 2部グラフの最大マッチングを求める手順を ご教授いただけないでしょうか. よろしくお願いいたします. 二次関数 グラフの頂点の座標について 二次関数の問題にて y=x^2+10x+5 のグラフの頂点の座標は とゆう問いがありまして 答えが(-5,-20)とありました… y=a(x-p)^2+q は(p,q)と頂点の座標を表せるのはわかるのですが…式の変形が意味が解りません… すいませんが分かりやすく解説をお願い致します! 積み上げグラフと集合グラフの組み合わせは可能でしょうか? Excel2000 + Windows95 の環境で、グラフ作成に関しての質問です。 A B C D E ------------------ 1| aa 10 5 4 3 2| bb 10 3 2 1 というような表がある場合に、B+CとD+Eの値を比較するためのグラフを作成し たいと思っています。 そこで、B+C,D+Eに関しては「積み上げ縦棒グラフ」の形でそれぞれを一本の グラフにして、且つB+CとD+Eを比較する為のこの2本のグラフを「集合縦棒グ ラフ」の形で一つの要素として扱いたいのです。 このような積み上げグラフと集合グラフの組み合わせは可能でしょうか。 現在は下記のような表から積み上げた手棒グラフを作成し、X軸のメモリとラ ベルの間隔を2にして擬似的に表現していますが、要素ごとに2本のグラフがくっ ついていないのが不満です。 A B C D E ------------------ 1| aa 10 5 2| aa 4 3 3| bb 10 3 4| bb 2 1 ご教授よろしくお願いいたします。 2次関数のグラフの頂点の座標について 2次関数のグラフの頂点の座標の答えを知りたいです。 (1)y=x^2+4x+1 (2)y=-3x^2+6x (3)y=-3分の1x^2-2x+1 回答よろしくお願いします。 2部グラフの最大マッチングとフローチャート JAVAで2部グラフの最大マッチングを求めるプログラムを作るのですが、本やネットを使って調べているのですが、まったく理解ができません。 どなたか教えていただけないでしょうか? 集合縦棒+積み上げ縦棒グラフ 以前にも同じ質問がありましたが分からないので教え て下さい。 集合縦棒のグラフを積み上げにしたいのです。 例えば13,14,15年のリンゴ,ミカン,ナシ の売上を 月別にグラフで表したい場合などです。 エクセルで出来ないのであれば、出来るソフトを教え てください。無料でダウンロード出来るような・・・。 よろしくお願いいたします。 エクセルで「積み上げ棒グラフ」と「集合棒グラフ」を合せる方法 現在、積み上げ棒でグラフ化しています。 これに、昨年度の積み上げ棒グラフを、並べて表示して、比較できるようにしたいと思います。 イメージとしては、昨年と今年度のデータを集合棒グラフで表示したい、かつそれぞれのデータは積み上げ棒グラフになっている、という感じでしょうか? なにかいい方法があったら教えてください! よろしくお願いします! n角形の頂点をt色以下で塗り分けるグラフ彩色 http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%BD%A9%E8%89%B2 によると、 隣接する頂点同士が同じ色にならないように全頂点に彩色する問題を頂点彩色という。 彩色多項式とは、与えられたグラフをt色以下で彩色したときの彩色の組合せ数を求める式である。 閉路グラフC_n(つまり、n角形)をt色以下で彩色したときの彩色多項式は、 (t-1)^n+(-1)^n*(t-1) これがどのように示されるのかがわからないので、どうか教えていただけないでしょうか。 エクセルで積み上げ棒グラフと集合縦棒を混在させる エクセルでグラフを作っているのですが 過去10年位の需要と供給の集合縦棒グラフを作り その需要と供給の内訳が解るように積み上げ棒グラフに変えたいのですが出来ません。 つまり、一つの項目に2本の積み上げ棒グラフを入れることができません。 よろしくお願いします。 これらが2部グラフではない理由を教えてください。 これらのグラフが2部グラフではない理由を教えてください。 また、右下のグラフのグラフ理論での名称を教えてください。 Excel2003グラフ - 集合縦棒を前後に並べる方法 りんご、みかん、バナナの月別の販売実績を年度ごとに比較表示する表の作り方を教えてください。 グラフの種類として「集合縦棒」を使い、横軸に月、 縦軸に販売実績、系列としてりんご、みかん、バナナを指定し表を作ります。 これを1年分として、前年度との比較ができる棒グラフを作成したいのですが、方法がわかりません。 複合グラフを使用すればいいと思うのですが、 「集合縦棒」同士で複合グラフを作成する方法はありますか? そのほか、よい方法がありましたら教えてください。 グラフ理論について 全然分からなくて困っています。誰か助けてください。 1.グラフKn,Kn ̄、Km,n,Cn,Tn〔Tnは位数nの木〕の染色数をそれぞれ求めよ。 2.グラフKn,Km,n,Cn,Tnの辺染色数をそれぞれ求めよ。 3.オイラーの多面体公式を証明せよ。 4.以下の問題を証明せよ。 〔1〕頂点数が3以上の平面グラフGが極大平面グラフであるための必要十分条件は、Gのすべての領域が三角形であることである。 〔2〕4頂点以上の極大平面グラフGにおいて、 △〔G〕 不等式 Σ 〔6-i〕Ni =12 〔Ni = {次数がiの頂点の数}〕が成立する。 〔3〕4頂点以上の平面的グラフには、次数5以下の頂点が存在する。 〔4〕K5,K3,3は非平面的グラフである。 〔5〕平面的グラフは5-彩色可能である。 グラフ理論の頂点に関する性質についての証明 全ての2頂点 v1,v2∈Gについて、ある一つの頂点w∈Gが存在しv1とwは隣接していて、かつ、v2とwも隣接しているようなグラフGを考える。このとき・・・ (a)v∈Gとwが非隣接ならばδ(v)=δ(w)を証明せよ (b)ある頂点の次数k>1かつどの頂点にも隣接しているような頂点は一つもない時、すべての頂点の次数はkになることを証明せよ の2問について証明の仕方を教えていただけると助かります。問題の状況がそもそもわかりません・・・(δはその頂点から出ている辺の数) もとの問題が英文なのでそっちも載せておきます。 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. エクセル 集合横棒グラフ 軸の反転 こんにちは。 エクセルで集合横棒グラフを作って 軸の反転をすると、グラフの下にあった数値軸が 上に移動してしまい、うまくいきません。 どうやったらいいのでしょうか? OSはWin98、Excel2000です。 過去の質問を検索してみましたが わかりませんでした。 よろしくお願いします。 注目のQ&A 「前置詞」が入った曲といえば? 緊急性のない救急車の利用は罪になるの? 助手席で寝ると怒る運転手 世界がEV車に全部切り替えてしまうなら ハズキルーペのCMって…。 全て黒の5色ペンが、欲しいです 長距離だったりしても 老人ホームが自分の住所になるのか? 彼氏と付き合って2日目で別れを告げられショックです 店長のチクチク言葉の対処法 カテゴリ 学問・教育 人文・社会科学 語学 自然科学 数学・算数 応用科学(農工医) 学校 受験・進学 留学 その他(学問・教育) カテゴリ一覧を見る あなたにピッタリな商品が見つかる! OKWAVE セレクト コスメ化粧品 化粧水・クレンジングなど 健康食品・サプリ コンブチャなど バス用品 入浴剤・アミノ酸シャンプーなど スマホアプリ マッチングアプリなど ヘアケア 白髪染めヘアカラーなど