問題タブ [undirected-graph]

対角線を含むグリッドの形でグラフを初期化するために for ループを実装しようとしています。基本的に、グラフで複製したい値で初期化された配列があります。そのため、複数の if ステートメントを持つネストされた for ループがあります。if ステートメントは特殊なケースを処理するために使用されます。つまり、インデックス 1,1 の要素には 3 つの隣接要素しかありません。

グラフ関数を手動で初期化すると、セグメント フォールトが発生せず、適切な BFS が出力されるため、グラフ関数が機能することはわかっていますが、ループ セグメント フォールトは発生します。ご覧ください：

グラフ クラス:

メインプログラムで：

注:グラフの頂点を 0 ではなく 1 から開始したかったのです。これが、行列に余分な行と列がある理由です。また、私のグラフでは両方向にエッジを追加する必要があるため、1--->0 および 0--->1 になります。

2-D 平面 (xy) に一連の点があり、n 点とします。

(x1, y1), (x2, y2), (x3, y3), ......................., (xn, yn)

私の目的はグラフを描くことです。グラフ内の 2 つのノード (点) は iff で接続され abs(difference in x coordinate) + abs(difference in y coordinate) = L(given)ます。

できますO(n*n)。効率よくできるかな。

ところで、私はこの問題を解決しようとしています

A、B、C、 の5 つの要素がDありEます。

各要素間の距離は、以下のマトリックスによって与えられます。

距離の合計が より小さい要素のすべての組み合わせを選択したいと考えています10。

次の方法で再帰的に実行できます。

• 最初に、2 項目の適格な組み合わせのセットを見つけます。
• 次に、以前に見つかった適格な 2 アイテムの組み合わせに別のアイテムを追加して、3 アイテムの適格な組み合わせのセットを見つけます。
• 等。

上記の例を手作業で行うと、次の組み合わせが得られます。

要素の数が多い場合 (250 など)、Octave でこれを体系的に行うにはどうすればよいでしょうか?

無向加重グラフ G=(V,E) があります。ここで、V はノードを表し、E はエッジを表します。ダイクストラ アルゴリズムを使用して、ソース ノード s をルートとし、グラフ G のすべてのノード V にまたがる最短パス ツリー Ts=(s,V) を取得しました。次に、サブツリー Tm=(s,K) を選択しました (ここで Kは、s をすべての V ノードの中で K ノードのみに接続する最短パス ツリー Ts=(s, V) の V) のサブセットです。つまり、サブツリー Tm は、最短パス ツリー Ts のサブセットです。

私の質問は、最短パス ツリー Ts のこのサブツリー Tm も最短ツリーであることを、引数またはレンマ/定理によってどのように証明できるかということです。前もって感謝します。

私は部屋のコレクションを持っています。各部屋は、基本的な方向 (北、南、東、西) を介して 1 つ以上の他の部屋に接続されています。部屋は、A が B の西にある場合、B が A の東になるように接続されています。したがって、無向グラフ。次に、この部屋のコレクションを座標平面でグラフ化する必要があります。すべてのエッジは X 軸または Y 軸に平行でなければなりません。

私はいくつかの異なるアプローチを試しましたが、これまでのところ最も効果的だと思うのは次のとおりです。

1. 「中心」を見つけて (0,0) を割り当てます (他のすべての部屋への最短経路の長さの合計が最小になる部屋)。これが本当に必要かどうかはわかりませんが、出力の中央揃えが容易になります。
2. 中心 C から出て、遭遇した各部屋 R に座標 (X, Y) を割り当てます。ここで、P は C=>R を結ぶパスであり、座標平面上で最大の変位が生じます。X は、P に沿った正味の水平移動です。 、Y は P に沿った正味の垂直移動です。

次の方向のベクトルを想定します: 北 = [0,1] 南 = [0,-1] 東 = [1,0] 西 = [-1,0]

無向加重グラフがあり、それを正式に説明する必要があります。オートマトンまたはラベル付き遷移システムによる抽象化は、無向グラフでは定義されていないようで、有向グラフのみがカバーされています。グラフ内の状態は互いに依存していますが、方向自体は関係ありません。

そのようなグラフを正式に説明するためにどの数学モデルを使用できるか知っていますか?