グラフ理論はサブセクションの1つです。数学。その主な特徴は、オブジェクトの研究における幾何学的手法です。その創始者は有名な数学者L.オイラーであると考えられています。
19世紀末までのグラフ理論の適用面白い問題を解決することになり、大きな一般的な注目を集めませんでした。グラフ理論が独立した数学的分野に形成された20世紀から、サイバネティックス、物理学、ロジスティクス、プログラミング、生物学、エレクトロニクス、輸送、通信システムなどの科学分野で幅広い応用が見出されました。
グラフ理論の基本概念
ベースはグラフです。用語では、グラフと同一のネットワークのような概念に出くわすことがあります。後者は、空でない数のポイント、つまり頂点、およびセグメント、つまりエッジであり、その両端は指定された数のポイントに対応します。グラフ理論は、エッジと頂点の値には意味がありません。たとえば、それらをつなぐ都市と道路。最初のグラフはグラフの頂点で、2番目のグラフはエッジです。理論上、アークは非常に重要です。エッジに方向がある場合は、アークの名前を持ち、エッジが方向付けられたグラフの場合は、有向グラフと呼ばれます。
理論の用語では、次の概念も区別されます。
サブグラフは、すべてのエッジと頂点が頂点とエッジの中にあるグラフです。
接続されたグラフは、2つの異なる頂点のチェーンを接続したグラフです。
重み付き連結グラフは、重み関数を持つグラフです。
ツリーは、サイクルのない接続されたグラフです。
スケルトンは、ツリーであるサブグラフです。
平面にグラフをプロットするとき特定の表記法：選択された頂点は最も単純な表面上の点に対応し、頂点間にエッジがある場合、対応する点はセグメントによって結合されます。グラフが方向付けられている場合、これらのセグメントは矢印に置き換えられます。
ただし、グラフの画像と比較しないでくださいつまり、1つのグラフに複数のグラフィック表現を与えることができるためです。平面上の描画は、頂点のペアがエッジで結合されており、どのペアが結合されていないかを確認するために与えられます。
グラフ理論のいくつかの問題には、次のものがあります。
- 最短チェーンのタスク（機器の交換、救急車の配置、電話交換）。
- 最大フローの問題（動的ネットワークでのトラフィックの合理化、作業配分、帯域幅編成）。
- コーティングとパッケージングの問題（コントロールセンターの配置）。
- グラフの色付け（電子コンピューターのメモリ割り当て）。
- 通信ネットワークとグラフ（通信ネットワークの作成、通信ネットワークの分析）。
現在、グラフ理論の知識がなければほとんどのタスクをプログラムすることは不可能です。これにより、コンピューターでの作業が容易になり、簡素化されます。
プログラミングは多くの構造を使用し、問題を解決するための普遍的な方法であり、そのうちの1つはグラフ理論です。その価値を過大評価することは困難です。プログラミングのグラフ理論により、情報の検索を簡素化し、プログラムを最適化し、データを変換および配布できます。理論のアルゴリズムのおかげで、特定の問題を解決するためにそれらを使用および評価し、プログラムの最終バージョンの数学的信頼性の程度を低下させることなくアルゴリズムを修正することが可能になります。
制御システムまたはモデルの重要な特性一連のアクションとデータ単位の一連のバイナリ関係です。これらの構造は、プログラムの一部であり、プログラムが変換する情報です。したがって、グラフはプログラマーの構成の基礎となります。
