多くの名前付きグラフ タイプがあります。この分類の背後にある基準は何なのか疑問に思っています。異なるタイプは異なるコンテキストで適用できますか? さらに、ビジネス アプリケーションは (設計とプログラミングの観点から) これらの分類から何か恩恵を受けることができますか? これはデザインパターンに似ていますか？
質問する
171 次
1 に答える
2
いくつかの理由から、グラフの一般的なファミリに名前を付けました。
特定のグラフ ファミリには、優れた単純なプロパティがあります。たとえば、ツリーには、任意のグラフを保持しない多数の有用なプロパティがあります (ノードの任意のペア間にパスが 1 つだけ存在する、ノードが最大限に非循環的である、接続が最小限であるなど)。 有向非巡回グラフは、通常のグラフでは不可能なトポロジー ソートが可能です。これらのタイプのグラフのいずれかで問題をモデル化できる場合は、グラフに特殊なアルゴリズムを使用して、任意のグラフから必ずしも取得できないプロパティを抽出できます。
特定のアルゴリズムは、特定の種類のグラフで高速に実行されます。現時点では多項式時間アルゴリズムを持たないグラフ上の多くの NP 困難な問題は、特定のタイプのグラフでは非常に簡単に解決できます。たとえば、最大独立集合問題(2 つのノードがエッジで接続されていないノードの最大のコレクションを選択する) は NP 困難ですが、ツリーと2 部グラフの場合は多項式時間で解くことができます。4 色問題 (隣接するノードに同じ色を割り当てることなく、グラフのノードを 4 つの異なる色のいずれかに色付けできるかどうかを判断する) は、一般に NP 困難ですが、平面グラフにはすぐに当てはまります(これは有名な4色です)。 -色定理)。
特定のアルゴリズムは、特定の種類のグラフではより簡単です。グラフ内のマッチングは、端点を共有する 2 つのエッジがないグラフ内のエッジのコレクションです。最大一致は、人々をグループにペアリングする方法を表すために使用できます。2 部グラフでは、最大一致を使用して、2 つのタスクが割り当てられた人はおらず、2 人の人に割り当てられたタスクはないように、人をタスクに割り当てる方法を表すことができます。二部グラフで最大の一致を見つけるための高速で理解しやすいアルゴリズムが多数あります。一般的なグラフに対応するアルゴリズムは、大幅に複雑になり、効率がわずかに低下します。
特定のグラフは歴史的に重要です。多くの名前付きグラフは、グラフを使用して任意のグラフのプロパティに関する推測を反証した人物にちなんで名付けられています。たとえば、ピーターセン グラフは、グラフについて正しいように見えても実際にはそうではない多くの定理の反例です。
特定のグラフは、理論的なコンピューター サイエンスで役立ちます。エキスパンダー グラフは、直観的に、ノードのコレクションがグラフ内の比例して大きいノードのコレクションに接続される必要があるグラフです。すべてのグラフがエキスパンダー グラフであるとは限りません。エキスパンダー グラフは、PCP の定理の 1 つの証明やSL = Lの証明など、理論的なコンピューター サイエンスの多くの結果で使用されます。
これは、私たちがさまざまなグラフ ファミリを気にかけている理由をすべて網羅したリストではありませんが、グラフ ファミリの使用と学習の動機付けに役立つことを願っています。
お役に立てれば！
于 2013-05-02T16:54:29.860 に答える