B - P + G = 1、(*)

ここで、B は頂点の総数、P はエッジの総数、G はポリゴン (面) の数です。

証拠。 与えられたパーティションの多角形に対角線が描かれた場合、等号が変わらないことを証明しましょう (図 2、a)。

a) b)

図2

実際、このような対角線を描画した後、新しいパーティションには B 個の頂点、P+1 個のエッジが含まれ、ポリゴンの数は 1 つ増加します。 したがって、私たちは、

B - (P + 1) + (G+1) = B - P + G。

このプロパティを使用して、入力ポリゴンを三角形に分割する対角線を描き、結果として得られる分割について、関係の実現可能性を示します。

これを行うには、外側のエッジを順番に削除して、三角形の数を減らします。 この場合、次の 2 つのケースが考えられます。

三角形 ABC を削除するには、2 つのエッジ (この場合は AB と BC) を削除する必要があります。

三角形 MKN を削除するには、1 つのエッジ (この場合は MN) を削除する必要があります。

どちらの場合でも、等価性は変わりません。 たとえば、最初のケースでは、三角形を削除した後、グラフは B-1 頂点、P-2 エッジ、および G-1 ポリゴンで構成されます。

(B - 1) - (P + 2) + (G -1) = B - P + G。

したがって、三角形を 1 つ削除しても等式は変わりません。

この三角形を削除するプロセスを続けると、最終的には 1 つの三角形で構成されるパーティションに到達します。 このようなパーティションの場合、B = 3、P = 3、G = 1 となるため、次のようになります。

B - P + G = 1。

これは、元のパーティションにも等式が成り立つことを意味し、そこから最終的に、多角形のこのパーティションに対して関係が有効であることがわかります。

オイラーの関係は多角形の形状に依存しないことに注意してください。 ポリゴンは、側面に隙間がない限り、変形、拡大、縮小、さらには側面を湾曲させることができます。 オイラーの関係は変わりません。

それでは、3 つの家と 3 つの井戸の問題の解決に進みましょう。

解決 。 これができると仮定しましょう。 家を点 D1、D2、D3 でマークし、井戸を点 K1、K2、K3 でマークしましょう (図 1)。 各ハウスポイントと各井戸ポイントを接続します。 ペアで交差しない 9 つのエッジが得られます。

これらのエッジは平面上に多角形を形成し、より小さな多角形に分割されます。 したがって、このパーティションでは、オイラー関係 B - P + G = 1 が満たされる必要があります。

検討中の面にもう 1 つの面を追加しましょう。これは、ポリゴンに対して面の外側の部分です。 この場合、オイラー関係は B - P + G = 2 の形式になり、B = 6 および P = 9 となります。

したがって、Г = 5 となります。問題の条件によれば、どのパスも 2 つの家または 2 つの井戸を直接接続する必要がないため、5 つの面のそれぞれには少なくとも 4 つのエッジがあります。 各エッジは正確に 2 つの面上にあるため、エッジの数は少なくとも (5 4)/2 = 10 でなければならず、これはエッジの数が 9 であるという条件と矛盾します。

結果として生じる矛盾は、問題に対する答えが否定的であることを示しています - 各家から各村まで交差しないパスを描くことは不可能です

化学におけるグラフ理論

グラフ理論を、トポロジー、モデルとも呼ばれるさまざまなクラスの化学および化学技術グラフの構築および分析に適用します。 頂点間の接続の性質のみを考慮するモデル。 これらのグラフの円弧 (エッジ) と頂点は、化学および化学技術の概念、現象、プロセス、またはオブジェクトを反映し、したがって、それらの間の定性的および定量的な関係、または特定の関係を反映します。

理論上の問題。 ケミカル グラフを使用すると、化学変換を予測し、本質を説明し、化学のいくつかの基本概念 (構造、配置、確認、分子の量子力学的および統計力学的相互作用、異性性など) を体系化することができます。ケミカル グラフには、分子グラフ、二部グラフ、シグナル グラフが含まれます。の運動反応方程式。 分子グラフは、立体化学や構造トポロジー、クラスターの化学、ポリマーなどで使用され、分子の構造を表示する無向グラフです。 これらのグラフの頂点と端は、対応する原子とそれらの間の化学結合に対応します。

立体化学組織内。 最も一般的に使用されるのは分子ツリーです。原子に対応するすべての頂点のみを含む分子グラフのスパン ツリーです。分子ツリーのセットをコンパイルし、その同型性を確立することで、分子構造を決定し、アルカンの異性体の総数を見つけることができます。アルケンとアルキン。 分子グラフを使用すると、さまざまな化合物の分子のコーディング、命名法、構造的特徴 (分岐、環状など) に関連する問題を、分子グラフとそのツリーの純粋に数学的な特徴と特性の分析と比較に減らすことができます。それらに対応する行列。 分子の構造と化合物の物理化学的（薬理学的を含む）特性との間の多数の相関関係を特定するために、20 を超えるいわゆる相関関係が開発されています。 分子ツリーの行列と数値特性を使用して決定される、分子のトポロジカル インデックス (Wiener、Balaban、Hosoya、Plata、Randich など)。 たとえば、ウィナー指数 W = (m3 + m)/6 (m は C 原子に対応する頂点の数) は、分子体積と屈折、生成エンタルピー、粘度、表面張力、化合物のクロマトグラフィー定数、オクタン価と相関します。炭化水素の数やフィジオールの数も。 薬物の作用。 特定の物質の互変異性体とその反応性を決定するために、またアミノ酸、核酸、炭水化物、その他の複雑な天然化合物の分類に使用される分子グラフの重要なパラメーターは、平均および合計 (H) 情報容量です。 頂点がモノマーユニットに対応し、エッジがモノマーユニット間の化学結合に対応するポリマーの分子グラフを解析すると、たとえば品質につながる排除体積の影響を説明することができます。 ポリマーの予測される特性の変化。 グラフ理論と人工知能の原理を使用して、化学における情報検索システムのソフトウェアや、分子構造の同定と有機合成の合理的な計画のための自動システムが開発されています。 合理的な化学経路を選択するための操作をコンピュータ上で実際に実装するため。 逆合成およびシントニック原理に基づく変換では、解決オプションのマルチレベル分岐検索グラフが使用されます。その頂点は試薬と生成物の分子グラフに対応し、円弧は変換を表します。

化学技術システム (CTS) の分析と最適化の多次元問題を解決するには、フロー、情報フロー、信号および信頼性グラフの化学技術グラフが使用されます。 化学の勉強用。 多数の粒子からなる系における擾乱の物理学では、いわゆるものを使用します。 ファインマン線図はグラフであり、その頂点は物理粒子の基本相互作用、衝突後の粒子の経路のエッジに対応します。 特に、これらのグラフにより、振動反応のメカニズムを研究し、反応システムの安定性を判断することができます。マテリアル フロー グラフは、化学システム内の化学物質の流量の変化を表示します。 熱流量グラフには、CTS の熱バランスが表示されます。 グラフの頂点は、物理的な流れの熱消費が変化するデバイスに対応し、さらにシステムの熱エネルギーのソースとシンクにも対応します。 アークは物理的な熱流と架空の (デバイス内の物理化学的エネルギー変換) 熱流に対応し、アークの重みは流れのエンタルピーに等しくなります。 材料グラフと熱グラフは、複雑な化学システムの材料と熱のバランスに関する連立方程式を解くためのアルゴリズムを自動開発するためのプログラムをコンパイルするために使用されます。 情報フロー グラフは、数式系の論理情報構造を表示します。 XTSモデル。 これらのシステムを計算するための最適なアルゴリズムを開発するために使用されます。 二部情報グラフは、頂点がそれぞれ対応する無向グラフまたは有向グラフです。 方程式 f1 ～ f6 と変数 q1 ～ V であり、分岐はそれらの関係を反映しています。 情報グラフ – 方程式を解く順序を示す有向グラフ。 グラフの頂点はこれらの方程式、XTS 情報のソースと受信者に対応し、枝は情報に対応します。 変数。 シグナル グラフは、化学技術プロセスおよびシステムの数学モデルの線形方程式系に対応します。 信頼性グラフは、さまざまな信頼性指標 X を計算するために使用されます。

使用した文献:

1. Berge K.、T. g. およびその応用、フランス語からの翻訳、M.、1962 年。

2. Kemeny J.、Snell J.、Thompson J.、有限数学入門、トランス。 英語より、第 2 版、M.、1963 年。

3.Ope O.、グラフとその応用、トランス。 英語から、M.、1965年。

4. Belykh O.V.、Belyak E.V.、社会学におけるテクノロジー使用の可能性、『人間と社会』、第 1 巻。 1、[L.]、1966年。

5. 社会学研究における定量的方法、M.、1966年。 Belyaev E.V.、「社会学的測定の問題」、「VF」、1967 年、第 7 号。 バベラス。 本書では、タスク指向グループのコミュニケーション パターンについて説明しています。 ラーナー D.、ラスウェル H.、政治学、スタンフォード、1951 年。

市立自治教育施設第二高等学校

準備した

レグココネッツ・ウラジスラフ、クラス10Aの生徒

グラフ理論の実践的応用

スーパーバイザー

L.I. ノスコバ、数学教師

アート・ブリュホヴェツカヤ

2011年

1.はじめに………………………………………………………………………….3

2. グラフ理論の出現の歴史……………………………………………….……..4

3. グラフ理論の基本的な定義と定理…………………………………………6

4. グラフを使って解く問題………………………………..…………………………..8

4.1 有名な問題…………………………………….………………………………8

4.2 いくつかの興味深い問題……………………………….………………..9

5. 人々の生活のさまざまな分野におけるグラフの応用…………………………………………11

6. 問題の解決…………………………………………………………………………12

7. 結論……………….…………………………………………………….13

8. 参考文献リスト…………………………………………………………………………14

9.付録……………………………………………………………………………………15

導入

パズルや楽しいゲームを解くことから生まれたグラフ理論は、現在では幅広い問題に関連する疑問を解決するための、シンプルでアクセスしやすい強力なツールとなっています。 グラフは文字通り遍在します。 グラフの形式では、たとえば、道路地図と電気回路、地理的地図と化合物の分子、人々と人々のグループ間のつながりを解釈できます。 過去 40 年にわたり、グラフ理論は数学の最も急速に発展した分野の 1 つになりました。 これは、急速に拡大するアプリケーション分野の需要によって推進されています。 集積回路や制御回路の設計、オートマトン、論理回路、プログラムのブロック図の研究、経済学や統計学、化学や生物学、スケジューリング理論などに使用されます。 それが理由です 関連性テーマは、一方ではグラフと関連する調査手法の人気によって決まりますが、他方ではそれを実装するための未開発の総合的なシステムによって決まります。

人生の多くの問題を解決するには長い計算が必要ですが、場合によってはその計算さえも成功しないことがあります。 これは何ですか 研究課題。 問題を解決するための、単純かつ合理的で短くエレガントな解決策を見つけることは可能かという疑問が生じます。 グラフを使用すると問題解決が容易になりますか? これにより決定されました 私の研究テーマ：「グラフ理論の実践」

目的この研究は、グラフを使用して実際の問題を迅速に解決する方法を学ぶことでした。

研究仮説。グラフ手法は非常に重要であり、科学や人間の活動のさまざまな分野で広く使用されています。

研究目的:

1. この問題に関する文献やインターネット リソースを調べます。

2.実際の問題を解決する際のグラフ法の有効性を確認します。

3. 結論を出します。

研究の実際的な意義その結果は間違いなく多くの人々の関心を呼び起こすだろうということです。 皆さんの中には、自分の家系図を作ろうとした人はいませんか？ これを正しく行うにはどうすればよいでしょうか? 輸送企業の責任者は、おそらく、目的地から複数の居住地に商品を輸送する際に、輸送をより収益性の高い方法で利用するという問題を解決する必要があります。 すべての学童は論理的な輸血の問題に遭遇したことがあります。 グラフを使用すると簡単に解決できることがわかりました。

作業では次の方法が使用されます。 観察、検索、選択、分析。

グラフ理論の歴史

グラフ理論の創始者は数学者レオンハルト・オイラー (1707-1783) であると考えられています。 この理論の歴史は、偉大な科学者の書簡を通じてたどることができます。 以下は、1736 年 3 月 13 日にサンクトペテルブルクからイタリアの数学者で技術者のマリノーニに宛てたオイラーの手紙から抜粋されたラテン語本文の翻訳です。

「私はかつて、ケーニヒスベルク市に位置し、川に囲まれ、7 つの橋が架けられている島についての問題を尋ねられました。

【付録図1】問題は、誰かが各橋を一度だけ通過し、継続的に橋の周りを回ることができるかどうかです。 そして、まだ誰もこれを実行できていないが、それが不可能であることを証明した人はいないと知らされました。 しかし、この問題は些細なことではあるが、幾何学も代数学も組み合わせ技術もそれを解決するには十分ではないという点で、私には注目に値するもののように思えた。 いろいろ考えた結果、完全に説得力のある証明に基づいた簡単なルールを見つけました。このルールを使えば、この種のすべての問題において、そのような迂回路が、位置する橋の数に関係なく通過できるかどうかを即座に判断することができます。か否か。 ケーニヒスベルク橋は、次の図に示すように配置されています。 【付録図2】ここで、A は島を示し、B、C、D は川の支流によって互いに分離された大陸の部分を示します。

この種の問題を解決するために発見した方法について、オイラーは次のように書いています。

「この解決策は、その性質上、明らかに数学とはほとんど関係がありません。なぜこの解決策を他の人ではなく数学者に期待する必要があるのか​​理解できません。なぜなら、この決定は推論だけで裏付けられており、根拠はありません。この解決策を見つけるためには数学に関わる必要があるのに、数学には固有の法則が存在するのに、数学とほとんど関係のない問題が他の人よりも数学者によって解決される可能性が高いことがどうしてわかるのか、私にはわかりません。」

それでは、ケーニヒスベルクの各橋を 1 回通過するだけで、これらの橋を迂回することは可能でしょうか? 答えを見つけるために、オイラーがマリノーニに宛てた手紙を続けてみましょう。

「問題は、これら 7 つの橋をすべて 1 回ずつ通過して回ることが可能かどうかを判断することです。私のルールは、この質問に対する次の解決策につながります。まず、セクションがいくつあるかを確認する必要があります。この例では、A、B、C、D という 4 つのセクションがあります。次に、番号がどちらであるかを区別する必要があります。これらの個々のセクションにつながる橋の数は偶数か奇数であるため、この場合、5 つの橋がセクション A につながり、3 つの橋がそれぞれ残りのセクションにつながります。つまり、個々のセクションにつながる橋の数は奇数であり、これだけでも次のようになります。これが問題を解決するのに十分であることが判明したら、次のルールを適用します。各セクションにつながる橋の数が偶数であれば、問題の迂回が可能であると同時に、これらの数値のうち 2 つが奇数である場合、1 つだけが奇数であることはできませんが、その場合でも、規定どおりに遷移を完了できますが、必ず迂回の先頭だけを取得する必要があります。奇数の橋がつながっている 2 つのセクションのうちの 1 つ。 最終的に、奇数の橋がつながっているセクションが 2 つ以上ある場合、そのような移動は一般に不可能です...他のより深刻な問題がここに持ち込まれる可能性がある場合、この方法はさらに大きな利益をもたらす可能性があり、そうすべきです無視しないでください。」

グラフ理論の基本的な定義と定理

グラフ理論は数学者の努力によって作成された数学分野であるため、その表現には必要な厳密な定義が含まれています。 それでは、この理論の基本概念を整理して紹介しましょう。

定義1.グラフは、グラフの頂点と呼ばれる有限数の点と、これらの頂点の一部を接続するペアの線 (グラフのエッジまたは円弧と呼ばれます) の集合です。

この定義は別の方法で定式化することもできます。グラフは空ではない点 (頂点) とセグメント (エッジ) の集合であり、その両端は指定された点の集合に属します。

以下では、グラフの頂点をラテン文字 A、B、C、D で表します。 グラフ全体を大文字 1 文字で表す場合もあります。

定義2.どのエッジにも属さないグラフの頂点は孤立と呼ばれます。

定義3.孤立した頂点のみで構成されるグラフは null と呼ばれます - カウント .

表記: O " – エッジのない頂点を持つグラフ

定義4.頂点の各ペアがエッジによって接続されているグラフは完全と呼ばれます。

指定: U" – n 個の頂点と、これらの頂点の考えられるすべてのペアを接続するエッジで構成されるグラフ。 このようなグラフは、すべての対角線が描かれた n 角形として表すことができます。

定義5.頂点の次数は、その頂点が属するエッジの数です。

定義6. k 個の頂点すべての次数が同じグラフを同次次数グラフと呼びます。 .

定義7.特定のグラフの補足は、完全なグラフを取得するために元のグラフに追加する必要があるすべてのエッジとその端で構成されるグラフです。

定義8.エッジが頂点でのみ交差するように平面上で表現できるグラフを平面と呼びます。

定義9.グラフの頂点やエッジを含まない平面グラフの多角形は、その面と呼ばれます。

平面グラフとグラフ面の概念は、さまざまな地図の「正しい」色付けに関する問題を解決するときに使用されます。

定義10.パス A から X は、A から X に至る一連のエッジであり、隣接する 2 つのエッジすべてが共通の頂点を持ち、複数回出現するエッジはありません。

定義11.サイクルとは、開始点と終了点が一致するパスです。

定義12.単純サイクルとは、グラフのどの頂点も複数回通過しないサイクルです。

定義13.パスの長さ , ループ状に敷いた , このパスのエッジの数が呼び出されます。

定義14．グラフ内の 2 つの頂点 A と B が、A から B に向かうパスが存在する (存在しない) 場合、接続されている (切断されている) と呼ばれます。

定義15．グラフの頂点が 2 つすべて接続されている場合、そのグラフは接続されていると呼ばれます。 グラフに切断された頂点のペアが少なくとも 1 つ含まれている場合、そのグラフは切断されていると呼ばれます。

定義16．ツリーは、循環を含まない接続されたグラフです。

樹木グラフの 3 次元モデルは、たとえば、複雑に枝分かれした樹冠を持つ本物の木です。 川とその支流も木を形成しますが、地球の表面ではすでに平らです。

定義17．完全にツリーから構成される切断されたグラフはフォレストと呼ばれます。

定義18．すべての n 個の頂点に 1 から n までの番号が付けられているツリーは、再番号付けされた頂点を持つツリーと呼ばれます。

そこで、グラフ理論の基本的な定義を検討しました。これがなければ定理を証明することは不可能であり、結果として問題を解決することは不可能です。

グラフを使って解決する問題

有名な問題

巡回セールスマン問題

巡回セールスマン問題は、組み合わせ論の有名な問題の 1 つです。 これは 1934 年に提唱され、優秀な数学者たちがそれに全力を尽くしました。

問題文は以下の通りです。
巡回セールスマン（行商人）は、最初の都市を出発し、順番は不明ですが、都市 2、1、3...n を 1 回訪問し、最初の都市に戻らなければなりません。 都市間の距離はわかっています。 巡回セールスマンの閉ざされた道（ツアー）を最短にするためには、どのような順序で都市を回ればよいでしょうか？

巡回セールスマン問題の解決法

貪欲なアルゴリズム 「最寄りの（まだ入っていない）都市に行ってください。」
このアルゴリズムは「貪欲」と呼ばれます。最後のステップでは、貪欲に対して多大な代償を払わなければならないためです。
たとえば、図のネットワークを考えてみましょう。 【付録図3】、狭いひし形を表します。 巡回セールスマンが都市 1 から開始するとします。「最も近い都市に行く」アルゴリズムにより、彼は都市 2、次に都市 3、そして都市 4 に移動します。 最後のステップでは、欲望の代償を支払わなければならず、ダイヤモンドの長い対角線に沿って戻ってきます。 結果的には最短ではなく最長のツアーとなるでしょう。

ケーニヒスベルク橋の問題。

問題は次のように定式化される。
ケーニヒスベルク市は、プレーゲル川と 2 つの島のほとりに位置しています。 市内のさまざまな部分は 7 つの橋で結ばれていました。 日曜日には町民が市内を散歩した。 質問: 家を出るとき、各橋をちょうど 1 回歩いて戻るような方法で散歩することは可能ですか?
プレーゲル川にかかる橋は写真のように位置しています。[付録図1]。

ブリッジ図に対応するグラフを考えてみましょう [付録図 2]。

問題の質問に答えるには、グラフがオイラー型かどうかを確認するだけで十分です。 (少なくとも 1 つの頂点から偶数のブリッジが延長されている必要があります)。 街を歩いてすべての橋を渡って戻ってくることはできません。

いくつかの興味深いタスク

1.「ルート」。

問題 1

覚えているように、死んだ魂のハンター、チチコフは有名な地主を一度ずつ訪問しました。 彼はマニロフ、コロボチカ、ノズドリョフ、ソバケヴィチ、プリーシキン、テンテトニコフ、ベトリシチェフ将軍、ペトゥク、コンスタンツホルゴ、コシュカレフ大佐の順で彼らを訪問した。 チチコフが地所の相対的な位置とそれらを結ぶ田舎道をスケッチした図が発見された。 チチコフがいずれかの道路を複数回運転しなかった場合、どの財産が誰に属するかを決定する [付録図4]。

解決:

道路地図は、チチコフが団地 E から旅を始め、団地 O で終わったことを示しています。団地 B と C に通じる道は 2 本しかないため、チチコフはこれらの道に沿って移動しなければならなかったことがわかります。 それらを太線でマークしましょう。 A を通過するルートのセクション AC と AB が特定されました。 チチコフはAE、AK、A​​Mの道路を走行しませんでした。 それらを消してみましょう。 ED を太線でマークしましょう。 DKを消してみましょう。 MO と MN を消してみましょう。 太線 MF でマークしましょう。 FOを取り消し線で消します。 FH、NK、KOを太線でマークしましょう。 この条件で唯一可能なルートを探してみましょう。 そして、私たちは次のようになります：E - マニロフに属する、D - コロボチカ、C - ノズドレフ、A - ソバケビッチ、B - プリューシキン、M - テンテトニコフ、F - ベトリシチェフ、N - ペトゥク、K - コンスタンツホルゴ、O - コシュカレフ 【付録図5】.

問題 2

図はその地域の地図を示しています [付録図6]。

矢印の方向にのみ移動できます。 各ポイントを訪れるのは 1 回までです。 ポイント 1 からポイント 9 まで行く方法は何通りありますか? どのルートが最短でどのルートが最長ですか。

解決:

頂点 1 から順に回路をツリーに「階層化」します。 【付録図7】。 木を手に入れましょう。 1 から 9 までの値を取得する可能な方法の数は、ツリーの「ぶら下がっている」頂点の数と同じです (14 個あります)。 明らかに最短パスは 1-5-9 です。 最長は 1-2-3-6-5-7-8-9 です。

2 「グループ、デート」

問題 1

音楽祭の参加者は会った後、住所が記載された封筒を交換しました。 次のことを証明してください:

a) 偶数の封筒が渡された。

b) 奇数回封筒を交換した参加者の数が偶数である。

解決策: フェスティバルの参加者を A 1、A 2、A 3 とします。 。 。 、n はグラフの頂点であり、エッジはエンベロープを交換する人たちを表す頂点のペアを接続します。 【付録図8】

解決：

a) 各頂点 A i の次数は、参加者 A i が友人に与えた封筒の数を示します。 送信されたエンベロープの総数 N は、グラフのすべての頂点の次数の合計 N = 次数に等しくなります。 1 + ステップ。 Ａ２＋＋。 。 。 +ステップ。 n -1 + 度。 そして、n、N = 2p、ここで、p はグラフのエッジの数です。 N – 偶数。 その結果、偶数の封筒が渡されました。

b) 等式 N = 度。 1 + ステップ。 Ａ２＋＋。 。 。 +ステップ。 n -1 + 度。 そして、奇数項の合計は偶数である必要があり、これは奇数項の数が偶数である場合にのみ可能です。 これは、奇数回封筒を交換した参加者の数が偶数であることを意味します。

問題 2

ある日、アンドレイ、ボリス、ヴォロディア、ダーシャ、ガリヤは夕方に映画に行くことに同意しました。 彼らは電話で映画とショーの選択を調整することにしました。 電話連絡が取れない場合は映画館への旅行を中止することも決定した。 夕方になっても全員が映画館に集まらなかったため、映画鑑賞は中止となった。 翌日、彼らは誰が誰に電話をかけてきたのかを調べ始めました。 アンドレイはボリスとヴォロディア、ヴォロディアはボリスとダーシャ、ボリスはアンドレイとダーシャ、ダーシャはアンドレイとヴォロディア、ガリヤはアンドレイ、ヴォロディア、ボリスと呼ばれていたことが判明しました。 電話が通じなかったために会議に来なかった人は誰ですか?

解決：

5 つの点を描き、A、B、C、D、D という文字でラベルを付けましょう。これらは名前の最初の文字です。 電話をかけてきた人の名前に対応する点を結んでみましょう。

【付録図9】

写真から、アンドレイ、ボリス、ヴォロディアの各人が他の全員に電話をかけていたことは明らかです。 それが彼らが映画館に来た理由です。 しかし、ガリヤとダーシャはお互いに電話をすることができず（点Gと点Eは線分で結ばれていない）、したがって合意に従って映画館には来なかった。

人々の生活のさまざまな分野でのグラフの応用

上記の例に加えて、グラフは建設、電気工学、管理、物流、地理、機械工学、社会学、プログラミング、技術プロセスと生産の自動化、心理学、広告などで広く使用されています。

科学技術のどの分野でもグラフに遭遇します。 グラフは、数学的、経済的、論理的な問題やさまざまなパズルを解決したり、物理学、化学、電子機器、オートメーションの問題の条件を単純化したりできる素晴らしい数学オブジェクトです。 多くの数学的事実は、グラフという言語で簡単に定式化できます。 グラフ理論は多くの科学の一部です。 グラフ理論は、最も美しく視覚的な数学理論の 1 つです。 最近、グラフ理論は応用問題への応用がますます増えています。 グラフ理論の応用に基づいた比較的若い化学分野である計算化学さえも登場しています。

分子グラフ、立体化学および構造トポロジー、クラスターの化学、ポリマーなどで使用され、分子の構造を表示する無向グラフです。 【付録図10】。 これらのグラフの頂点と辺は、対応する原子とそれらの間の化学結合に対応します。

分子グラフとツリー: 【付録図10】 a、b - それぞれマルチグラフ。 エチレンとホルムアルデヒド。 彼らは言う ペンタン異性体 (ツリー 4、5 はツリー 2 と同形です)。

生物の立体化学において最も多い。 分子ツリーは、C 原子に対応するすべての頂点のみを含む分子グラフの主要なツリーとしてよく使用されます。 木とその同型性の確立により、彼らが言うことを決定することが可能になります。 構造を調べて、アルカン、アルケン、アルキンの異性体の総数を調べます。

タンパク質ネットワーク

タンパク質ネットワークは、細胞内で連携して機能し、体内で起こる相互接続されたプロセスを制御する、物理的に相互作用するタンパク質のグループです。 【添付図】 11]。

階層システムグラフ木と呼ばれます。 木の独特の特徴は、その任意の 2 つの頂点間には 1 つのパスしか存在しないことです。 ツリーにはサイクルやループは含まれません。

通常、階層システムを表すツリーには、ツリーのルートと呼ばれる 1 つの主要な頂点があります。 ツリーの各頂点 (ルートを除く) には祖先が 1 つだけあり、祖先によって指定されるオブジェクトは 1 つの最上位クラスに含まれます。 ツリーのどの頂点でも、複数の子孫 (下位レベルのクラスに対応する頂点) を生成できます。

ツリーの頂点のペアごとに、それらを接続する一意のパスがあります。 この特性は、家系図 (グラフ理論の意味での「木」) の形式で表される人の家系図のすべての祖先を、たとえば男系で検索するときに使用されます。

私の家系図の例 [付録図 12]。

別の例。 写真は聖書の家系図を示しています [付録図 13]。

問題解決

1.輸送タスク。 クラスノダール市に基地を設け、一度の旅行でクリムスク、テムリュク、スラビャンスク・ナ・クバン、ティマシェフスクの各都市に原材料を配布し、時間と燃料をできるだけ少なくしてクラスノダールに戻るようにする。 。

解決：

まず、考えられるすべての移動ルートのグラフを作成しましょう 【付録図14】、これらの集落間の実際の道路とそれらの間の距離を考慮して。 この問題を解決するには、ツリー状の別のグラフを作成する必要があります。 【付録図15】.

ソリューションの便宜上、都市を番号で指定します: クラスノダール - 1、クリムスク - 2、テムリュク - 3、スラビャンスク - 4、ティマシェフスク - 5。

結果は 24 個の解になりますが、必要なのは最短パスだけです。 すべての解決策のうち、満足できる解決策は 2 つだけです。これは 350 km です。

同様に、ある地域から別の地域への実際の輸送を計算することは可能であり、また、計算する必要があると思います。

輸血に関する論理的な問題。バケツには8リットルの水が入っており、5リットルと3リットルの容量の2つの受け皿があります。 5リットルの鍋に4リットルの水を注ぎ、バケツに4リットルを残す必要があります。つまり、水をバケツと大きな鍋に均等に注ぎます。

解決：

あらゆる瞬間の状況は 3 つの数字で表すことができます [付録図 16]。

その結果、2 つの解が得られます。1 つは 7 手で、もう 1 つは 8 手でです。

結論

したがって、問題の解決方法を学ぶには、問題が何であるか、どのように構造化されているか、どのようなコンポーネントで構成されているか、問題を解決するためのツールは何かを理解する必要があります。

グラフ理論を使用して実際の問題を解決すると、解決のあらゆる段階、あらゆる段階で創造性を発揮する必要があることが明らかになりました。

最初から、最初の段階では、問題の状態を分析してエンコードできる必要があるという事実にあります。 第 2 段階は、グラフの幾何学的表現で構成される概略表記です。この段階では、条件の要素と対応する条件の要素の間の対応関係を見つけるのは決して簡単ではないため、創造性の要素が非常に重要です。グラフ。

輸送の問題や家系図を作成するタスクを解決しているときに、グラフ手法は確かに興味深く、美しく、視覚的に優れているという結論に達しました。

グラフは経済学、経営学、テクノロジーの分野で広く使われていると確信しました。 グラフ理論はプログラミングにも使用されますが、これについてはこの記事では説明しませんでしたが、時間の問題だと思います。

この科学的研究では、数学的グラフとその応用分野を検証し、グラフを使用していくつかの問題を解決します。 グラフ理論の基礎の知識は、生産や経営管理に関連するさまざまな領域 (ネットワーク構築スケジュール、メール配信スケジュールなど) で必要です。 さらに、科学論文の執筆中に、WORD テキスト エディタを使用したコンピュータでの作業をマスターしました。 こうして、科学的研究の目的は達成されました。

したがって、上記のすべてから、グラフ理論の実用的な価値は疑いなく帰結し、その証明がこの研究の目標でした。

文学

バージ K.グラフ理論とその応用。 -M.: IIL、1962 年。

ケメニー J.、スネル J.、トンプソン J.有限数学の入門。 -M.: IIL、1963 年。

オレO。グラフとその応用。 -M.: ミール、1965年。

ハラリ F.グラフ理論。 -M.: ミール、1973年。

ジコフ A.A.有限グラフ理論。 -ノボシビルスク：科学、1969年。

ベレジナ L.Yu.グラフとその応用。 -M.: 教育、1979 年。-144 ページ。

「ソロス教育ジャーナル」第 11 号、1996 年 (記事「フラット グラフ」)。

ガードナー M.「数学的余暇」、M.「世界」、1972 年 (第 35 章)。

Olehnik S. N.、Nesterenko Yu. V.、Potapov M. K. 「古い面白い問題」、M. 「科学」、1988 (パート 2、セクション 8; 付録 4)。

応用

応用

P

米。 6

米。 7

米。 8

応用

応用

応用

P

米。 14

応用

主題に関する高等数学の概要:

グラフ理論の化学への応用

グループNH-202の学生による演奏

モスクワ 2011
グラフは、離散構造を研究する有限数学の分野です。 さまざまな理論的および応用的な問題を解決するために使用されます。
いくつかの 基本的な概念。グラフは点 (頂点) の集合、および線で接続されたこれらの点 (すべてではない) のペアの集合です (図 1、a)。 グラフ内の線が方向を向いている場合 (つまり、矢印が頂点の接続方向を示している場合)、それらは円弧または枝と呼ばれます。 方向が定まっていない場合は、 - エッジ。 したがって、円弧のみを含むグラフは有向グラフまたは有向グラフと呼ばれます。 エッジ非指向のみ。 アークとリブ - 混合。 複数のエッジを持つグラフはマルチグラフと呼ばれます。 2 つの素なサブセット (部分) に属するエッジのみを含むグラフは 2 部構成です。 パラメータの特定の重みまたは数値に対応する円弧 (エッジ) および (または) 頂点が重み付けされます。 グラフ内のパスは、頂点と円弧の交互のシーケンスであり、どの頂点も繰り返されません (たとえば、図 1、a の a、b)。 輪郭 - 最初と最後の頂点が一致する閉じたパス (f、h など)。 ループ - 同じ頂点で始まり同じ頂点で終わる円弧 (エッジ)。 グラフ パスは、頂点が繰り返されない一連のエッジです (たとえば、c、d、e)。 サイクル - 最初の頂点と最後の頂点が一致する閉じたチェーン。 グラフの頂点のペアがチェーンまたはパスによって接続されている場合、そのグラフは接続されていると呼ばれます。 それ以外の場合、グラフは切断されたと呼ばれます。
ツリーは、サイクルや等高線を含まない、接続された無向グラフです (図 1、b)。 グラフの全域サブグラフは、すべての頂点と特定のエッジのみを含むグラフのサブセットです。 グラフのスパニング ツリーは、そのスパニング サブグラフ、つまりツリーです。 頂点とエッジ (円弧) のセット間に 1 対 1 の対応がある場合、グラフは同形であると呼ばれます。
グラフ理論とその応用の問題を解決するために、グラフは行列 (隣接関係、出現率、2 行など) および特殊な行列を使用して表現されます。 数値的特性。 たとえば、隣接行列（図1c）では、行と列はグラフの頂点の数に対応し、その要素は値0と1をとります（それぞれ、間の円弧の有無）指定された頂点のペア); 出現率行列（図1d）では、行は頂点の数に対応し、列は円弧の数に対応し、要素は値0、+ 1、および-1（それぞれ、不在）を取ります。 、頂点に出入りする円弧の存在）。 最も一般的な数値特性: 頂点の数 (m)、円弧またはエッジの数 (n)、循環数、またはグラフのランク (n - m + k、ここで、k は接続された部分グラフの数)例えば、図１のグラフの場合、ｂランクは１０－６＋１＝５）となる。
グラフ理論の応用は、トポロジカル モデルとも呼ばれる、さまざまなクラスの化学グラフおよび化学技術グラフの構築と分析に基づいています。 頂点間の接続の性質のみを考慮するモデル。 これらのグラフの円弧 (エッジ) と頂点は、化学および化学技術の概念、現象、プロセスまたはオブジェクト、およびそれに応じてそれらの間の定性的および定量的な関係、または特定の関係を表示します。

米。 1. いくつかの基本概念の図: 混合グラフ。 b 全域木 (実線の円弧 a、h、d、f、h) と有向グラフの特定の部分グラフ (点線の円弧 c、e、g、k、l)。 c、r行列それぞれ。 有向グラフの隣接性と出現率。
理論上の問題。ケミカル グラフを使用すると、化学変換を予測し、本質を説明し、化学のいくつかの基本概念 (構造、配置、立体配座、分子の量子力学および統計力学的相互作用、異性性など) を体系化することができます。ケミカル グラフには、分子グラフ、二部グラフ、シグナル グラフが含まれます。の運動反応方程式。
立体化学や構造トポロジー、クラスターやポリマーなどの化学で使用される分子グラフは、分子の構造を表示する無向グラフです (図 2)。 これらのグラフの頂点と辺は、それぞれ原子と原子間の化学結合に対応します。

米。 2. 分子グラフと分子ツリー: a、b - それぞれマルチグラフ。 エチレンとホルムアルデヒド。 彼らは言う ペンタン異性体 (ツリー 4、5 はツリー 2 と同形です)。
有機物質の立体化学では、C 原子に対応するすべての頂点のみを含む分子グラフのスパニング ツリーである分子ツリーが最もよく使用されます (図 2、a および b)。 分子ツリーのセットを編集し、その同型性を確立すると、分子構造を決定し、アルカン、アルケン、およびアルキンの異性体の総数を見つけることができます (図 2、c)。
分子グラフを使用すると、さまざまな化合物の分子のコーディング、命名法、構造的特徴 (分岐、環状など) に関連する問題を、分子グラフとそのツリーの純粋に数学的な特徴と特性の分析と比較に減らすことができます。それらに対応する行列。 分子の構造と化合物の物理化学的 (薬理学的を含む) 特性の間の定量的な相関関係を特定するために、分子のトポロジカル指標の名前が 2 万以上開発されています (Wiener、Balaban、Hosoya、Plat、Randich など)。行列と分子ツリーの数値特性を使用して決定されます。 たとえば、ウィナー指数 W = (m 3 + m)/6 (m は C 原子に対応する頂点の数) は、分子体積と屈折、生成エンタルピー、粘度、表面張力、化合物のクロマトグラフィー定数、炭化水素のオクタン価や薬物の生理活性さえも。
特定の物質の互変異性体とその反応性を決定するために、またアミノ酸、核酸、炭水化物、その他の複雑な天然化合物の分類に使用される分子グラフの重要なパラメーターは、平均および合計 (H) 情報容量です。 パラメーターは、シャノンの情報エントロピーの公式を使用して計算されます。 ここで、 p t は、グラフの頂点 m が i 番目のタイプまたは同値クラス k に属する確率です。 i = 、パラメータ。 無機クラスターやメビウスの輪などの分子構造の研究は、結局のところ、複雑な多面体 (クラスターの場合は多面体など) または特殊な多面体にそれらを配置 (埋め込み) することによって、対応する分子グラフの同型性を確立することになります。 多次元曲面 (リーマン曲面など)。 頂点がモノマーユニットに対応し、エッジがモノマーユニット間の化学結合に対応するポリマーの分子グラフの分析により、たとえば排除体積の影響を説明することが可能になり、ポリマーの予測特性の質的変化につながります。 。

米。 3. 反応グラフ: 二部構成。 b-信号レベルの動態。 r 1、g 2 -r-tion; a 1 -a 6 -試薬; k レート定数 p-tsny; s-complex ラプラス変換変数。
グラフ理論と人工知能の原理を使用して、化学における情報検索システムだけでなく、分子構造の特定や有機合成の合理的な計画のための自動化システム用のソフトウェアが開発されています。 逆合成原理とシントニック原理に基づいて化学変換の合理的な経路を選択する操作をコンピュータ上で実際に実装するために、解決オプションのマルチレベル分岐検索グラフが使用されます。その頂点は試薬と生成物の分子グラフに対応します。そして円弧は物質の変化を表します。

米。 4. 単一回路化学技術システムと対応するグラフ: 構造図。 b、cはそれぞれマテリアルフローグラフ。 総質量流量と成分 A の流量による。 r - 熱流量グラフ。 図のグラフの分析から得られる、マテリアルバランスの連立方程式 (f 1 ～ f 6) の d フラグメント。 4、bおよびc。 電子二部構成の情報ダイグラフ。 g情報グラフ、Iミキサー。 II-反応器; III-蒸留塔; IV冷蔵庫; I 1 -I 8 -テクノロジー。 ストリーム; q-質量流量; H は流れのエンタルピーです。 私。 s と i*、s* - それぞれ 物質と熱の流れの実際および架空のソースとシンク。 c-試薬の濃度。 V は反応器の容積です。
さまざまな化合物の分子グラフの行列表現は、(対応する行列要素を変換した後) 量子化学の行列法と同等です。 したがって、複雑な量子化学計算を実行する場合、グラフ理論が使用されます。これは、分子軌道の数、特性、エネルギーの決定、共役交互および非交互ポリエンの反応性の予測、物質の芳香族特性および反芳香族特性の同定などに使用されます。
化学物理学において多数の粒子で構成される系の乱れを研究するには、いわゆるファインマン図が使用されます。このグラフの頂点は物理粒子の基本相互作用に対応し、エッジは衝突後の粒子の経路に対応します。 特に、これらのグラフにより、振動反応のメカニズムを研究し、反応系の安定性を判断することが可能になります。
既知の相互作用の所定のセットに対する試薬分子の変換の合理的な経路を選択するには、二部反応グラフが使用されます (頂点は分子とこれらの反応に対応し、円弧は反応における分子の相互作用に対応します。図 3、a)。 このようなグラフにより、最小数の中間反応、許容される試薬のリストからの最小数の試薬を必要とする化学変換の最適な経路を選択するための対話型アルゴリズムを開発したり、生成物の最高収率を達成したりすることが可能になります。
反応速度論方程式の信号グラフは、代数演算子形式で表現された反応速度方程式系を表示します (図 3b)。 グラフの頂点は、試薬の濃度の形のいわゆる情報変数または信号に対応し、円弧は信号の関係に対応し、円弧の重みは速度定数によって決定されます。 このようなグラフは、複雑な触媒反応の機構と速度論、複雑な化合物の形成における複雑な相平衡の研究、および溶液の相加的特性のパラメーターの計算に使用されます。
応用問題。化学技術システム (CTS) の分析と最適化の多次元問題を解決するために、次の化学技術グラフが使用されます (図 4): フロー、情報フロー、信号および信頼性グラフ。 加重有向グラフであるフロー グラフには、物理​​的な流れの総質量流量および一部の化学成分または元素の質量流量に関するパラメトリックな材料、および熱グラフが含まれます。 リストされたグラフは、特定の化学系における物質とエネルギーの物理的および化学的変換に対応します。
パラメトリック フロー グラフは、CTS 要素による物理的な流れのパラメーター (質量流量など) の変換を表示します。 グラフの頂点はデバイスの数学的モデル、指定されたフローのソースとシンクに対応し、円弧はフロー自体に対応し、円弧の重みはそのパラメータの数に等しくなります。対応する流れ。 パラメトリック グラフは、複数回路化学システムの技術モードを分析するためのアルゴリズムを開発するために使用されます。 このようなアルゴリズムは、任意のシステムの個々のデバイスの数学モデルの方程式系を計算するシーケンスを確立し、可変入力フローの既知の値を使用して出力フローのパラメーターを決定します。
マテリアルフローグラフは、化学物質中の物質使用量の推移を表示します。 グラフの頂点は、物理的な流れの総質量流量と一部の化学成分または元素の質量流量が変換されるデバイス、および流れまたはこれらの成分の物質のソースとシンクに対応します。 したがって、グラフの円弧は、任意のコンポーネントの物理的な流れ、または物理的および架空の（装置内の物質の化学変化）ソースおよびシンクに対応し、円弧の重みは両方のタイプの質量流量に等しくなります。 熱流量グラフには、CTS の熱バランスが表示されます。 グラフの頂点は、物理的な流れの熱消費が変化するデバイスに対応し、さらにシステムの熱エネルギーのソースとシンクにも対応します。 アークは物理的な熱流と架空の (デバイス内の物理化学的エネルギー変換) 熱流に対応し、アークの重みは流れのエンタルピーに等しくなります。 材料グラフと熱グラフは、複雑な化学システムの材料と熱のバランスに関する連立方程式を解くためのアルゴリズムを自動開発するためのプログラムをコンパイルするために使用されます。
情報ストック​​ グラフは、CTS の数学モデルの方程式系の論理情報構造を表示します。 これらのシステムを計算するための最適なアルゴリズムを開発するために使用されます。 二部情報グラフ（図４、ｅ）は無向または有向グラフであり、その頂点はそれぞれ方程式ｆ １ ～ｆ ６ および変数ｑ １ ～Ｖに対応し、枝はそれらの関係を反映する。 情報グラフ (図 4、g) - 方程式を解く順序を示す有向グラフ。 グラフの頂点はこれらの方程式、XTS 情報のソースと受信者に対応し、枝は情報変数に対応します。
シグナル グラフは、化学技術プロセスおよびシステムの数学モデルの線形方程式系に対応します。 グラフの頂点は信号 (温度など) に対応し、枝は信号間の接続に対応します。 このようなグラフは、マルチパラメータプロセスや化学システムの静的モードと動的モードを分析するだけでなく、それらの最も重要な特性 (安定性、感度、制御性) の指標を分析するために使用されます。
信頼性グラフは、化学装置の信頼性を表すさまざまな指標を計算するために使用されます。 これらのグラフの多数のグループ (たとえば、パラメトリック、論理関数) の中で、いわゆるフォールト ツリーが特に重要です。 このような各ツリーは、個々のプロセスと CTS デバイスの多くの単純な障害の相互関係を表示する重み付き有向グラフであり、これが多くの二次的な障害とその結果としてのシステム全体の障害につながります。
信頼性の高い最適な生産（リソースの節約を含む）を自動合成するためのプログラムの複合体を作成するには、人工知能、指向性セマンティック、またはセマンティックの原理に沿って、CTS ソリューション オプションのグラフが使用されます。 これらのグラフは、特定の場合にはツリーであり、一連の合理的な代替 CTS スキーム (たとえば、目的製品の 5 成分混合物を精留によって分離する場合に 14 通りが可能) を生成する手順と、それらの間で順序付けられた選択の手順を示しています。システム効率の何らかの基準に従って最適なスキーム。
等.............

さらに、オイラーは生涯の最後の 12 年間、重病を患い、失明し、重病にもかかわらず、仕事と創作を続けました。

統計計算によると、オイラーは平均して 1 週間に 1 件の発見を行ったことが示されています。

オイラーの著作で扱われていない数学的問題を見つけるのは困難です。

その後の世代のすべての数学者は何らかの形でオイラーを研究しました。そして、有名なフランスの科学者 P.S. ラプラスは、「オイラーを読んでください。彼は私たち全員の教師です。」と言いました。

ラグランジュは、「本当に数学が好きなら、オイラーを読んでください。彼の作品のプレゼンテーションは、その驚くべき明快さと正確さで注目に値します。」と述べています。 確かに、彼の計算の優雅さは最高のレベルに達しました。 コンドルセはオイラーを追悼するアカデミーでのスピーチを次の言葉で締めくくった。「それでオイラーは生きることも計算することもやめたのだ！」 計算するために生きるなんて、外から見たらなんと退屈なことでしょう！

数学者は、日常のあらゆること、普通の人が興味を持っていることに無関心で耳が聞こえない人だと想像するのが通例です。

オイラーにちなんで名付けられたこの問題は、3 つの家と 3 つの井戸の問題です。

トポロジのブランチの 1 つ。 グラフは、特定の点を結ぶ線の体系である幾何学的な図です。 点は頂点と呼ばれ、それらを結ぶ線はエッジ（または円弧）と呼ばれます。 すべてのグラフ理論の問題は、グラフ形式と行列形式の両方で解決できます。 行列形式で記述する場合、ある頂点から別の頂点にメッセージを送信できる可能性は 1 で示され、存在しない場合は 0 で示されます。

18 世紀のグラフ理論の起源。 数学パズルと関連付けられていますが、その開発に特に強い刺激が与えられたのは 19 世紀です。 そして主に 20 世紀に、無線電子回路の計算、いわゆる問題の解決など、実用的な応用の可能性が発見されました。 50年代から輸送業務など。 グラフ理論は社会心理学や社会学でますます使用されています。

グラフ理論の分野では、F. Harry、J. Kemeny、K. Flament、J. Snell、J. French、R. Norman、O. Oyser、A. Beivelas、R. Weiss などの著作に言及する必要があります。ソ連では、T. g。 M. ボロドキンら。

グラフ理論言語は、さまざまな種類の構造を分析し、状態を転送するのに適しています。 これに従って、グラフ理論を使用して解決される社会学的および社会心理学的問題の次のタイプを区別できます。

複雑さのさまざまなレベルでの社会的オブジェクトの一般的な構造モデルの形式化と構築。 例えば、組織の構造図、ソシオグラム、異なる社会における親族関係システムの比較、集団の役割構造の分析など。

役割構造には、人、役職 (簡略化したバージョンでは役職)、および特定の役職で実行されるタスクという 3 つの要素が含まれていると考えることができます。

各コンポーネントはグラフとして表すことができます。

すべての位置または 1 つの位置のみについて 3 つのグラフすべてを組み合わせることが可能であり、その結果、c.l. の特定の構造について明確なアイデアが得られます。 この役割。 したがって、位置 P5 の役割については、グラフが得られます (図)。 指定された形式的な構造に非形式的な関係を織り込むと、グラフは大幅に複雑になりますが、現実のより正確なコピーになります。

a) 数量。 階層的な組織における個人の重み（ステータス）を評価すること。 ステータスを決定するための可能なオプションの 1 つは次の式です。

ここで、r (p) は特定の人 p のステータス、k は従属レベルの値、特定の人からその部下までの最小ステップ数として定義され、nk は特定のレベル k にある人の数です。 。 例えば、以下のような組織の場合。 カウント：

重さa=1・2+2・7+3・4=28; 6=1・3+2・3=9など

b) グループリーダーの決定。 リーダーは通常、他のリーダーと比べてグループの他のメンバーとのつながりが強いという特徴があります。 前のタスクと同様に、ここでもさまざまな方法を使用してリーダーを識別できます。

最も単純な方法は次の式で与えられます: r=Σdxy/Σdqx、つまり 各個人から他のすべての個人までのすべての距離の合計を、特定の個人から他のすべての個人までの距離の合計で割った商。

4) このシステムの活動の有効性の分析。これには、組織の最適な構造の探索、グループの結束力の向上、持続可能性の観点からの社会システムの分析などのタスクも含まれます。 情報の流れの研究（問題解決時のメッセージの伝達、グループを団結させる過程でのグループメンバーの相互影響）。 テクノロジーの助けを借りて、最適な通信ネットワークを見つけるという問題を解決します。

グラフ理論やあらゆる数学的装置に適用すると、問題を解決するための基本原理が実体理論 (この場合は社会学) によって設定されることは事実です。

タスク : 3 人の隣人には 3 つの共通の井戸があります。 各家から各井戸まで交差しない経路を構築することは可能ですか? 井戸や家屋の中は道が通れません（図1）。

米。 1. 家と井戸の問題について。

この問題を解決するには、グラフ理論の主要な定理の 1 つである、1752 年にオイラーによって証明された定理を使用します。 グラフ理論に関する最初の研究はレオンハルト・オイラー (1736 年) によるものですが、「グラフ」という用語は 1936 年にハンガリーの数学者デネス・ケーニッヒによって初めて導入されました。 グラフは、点と、これらの点を接続する直線または曲線のセグメントで構成される図と呼ばれていました。

定理。 多角形が有限数の多角形に分割され、そのパーティションの 2 つの多角形が共通の点をもたないか、共通の頂点をもたないか、共通の辺をもたない場合、等式が成り立ちます。

B - P + G = 1、(*)

ここで、B は頂点の総数、P はエッジの総数、G はポリゴン (面) の数です。

証拠。 与えられたパーティションの多角形に対角線が描かれた場合、等号が変わらないことを証明しましょう (図 2、a)。

A) b)

実際、このような対角線を描画した後、新しいパーティションには B 個の頂点、P+1 個のエッジが含まれ、ポリゴンの数は 1 つ増加します。 したがって、私たちは、

B - (P + 1) + (G+1) = B - P + G。

このプロパティを使用して、入力ポリゴンを三角形に分割する対角線を描き、結果として得られる分割について、関係の実現可能性を示します。

これを行うには、外側のエッジを順番に削除して、三角形の数を減らします。 この場合、次の 2 つのケースが考えられます。

三角形 ABC を削除するには、2 つのエッジ (この場合は AB と BC) を削除する必要があります。

三角形 MKN を削除するには、1 つのエッジ (この場合は MN) を削除する必要があります。

どちらの場合でも、等価性は変わりません。 たとえば、最初のケースでは、三角形を削除した後、グラフは B-1 頂点、P-2 エッジ、および G-1 ポリゴンで構成されます。

(B - 1) - (P + 2) + (G -1) = B - P + G。

したがって、三角形を 1 つ削除しても等式は変わりません。

この三角形を削除するプロセスを続けると、最終的には 1 つの三角形で構成されるパーティションに到達します。 このようなパーティションの場合、B = 3、P = 3、G = 1 となるため、次のようになります。

これは、元のパーティションにも等式が成り立つことを意味し、そこから最終的に、多角形のこのパーティションに対して関係が有効であることがわかります。

オイラーの関係は多角形の形状に依存しないことに注意してください。 ポリゴンは、辺が壊れない限り、変形、拡大、縮小したり、辺を曲げたりすることもできます。 オイラーの関係は変わりません。

それでは、3 つの家と 3 つの井戸の問題の解決に進みましょう。

解決。 これができると仮定しましょう。 家を点 D1、D2、D3 でマークし、井戸を点 K1、K2、K3 でマークしましょう (図 1)。 各ハウスポイントと各井戸ポイントを接続します。 ペアで交差しない 9 つのエッジが得られます。

これらのエッジは平面上に多角形を形成し、より小さな多角形に分割されます。 したがって、このパーティションでは、オイラー関係 B - P + G = 1 が満たされる必要があります。

検討中の面にもう 1 つの面を追加しましょう。これは、ポリゴンに対して面の外側の部分です。 この場合、オイラー関係は B - P + G = 2 の形式になり、B = 6 および P = 9 となります。

したがって、Г = 5 となります。問題の条件によれば、どのパスも 2 つの家または 2 つの井戸を直接接続する必要がないため、5 つの面のそれぞれには少なくとも 4 つのエッジがあります。 各エッジは正確に 2 つの面上にあるため、エッジの数は少なくとも (5 4)/2 = 10 でなければならず、これはエッジの数が 9 であるという条件と矛盾します。

結果として生じる矛盾は、問題に対する答えが否定的であることを示しています - 各家から各村まで交差しないパスを描くことは不可能です

化学におけるグラフ理論

グラフ理論を、トポロジー、モデルとも呼ばれるさまざまなクラスの化学および化学技術グラフの構築および分析に適用します。 頂点間の接続の性質のみを考慮するモデル。 これらのグラフの円弧 (エッジ) と頂点は、化学および化学技術の概念、現象、プロセス、またはオブジェクトを反映し、したがって、それらの間の定性的および定量的な関係、または特定の関係を反映します。

理論上の問題。 ケミカル グラフを使用すると、化学変換を予測し、本質を説明し、化学のいくつかの基本概念 (構造、配置、確認、分子の量子力学的および統計力学的相互作用、異性性など) を体系化することができます。ケミカル グラフには、分子グラフ、二部グラフ、シグナル グラフが含まれます。の運動反応方程式。 分子グラフは、立体化学や構造トポロジー、クラスターの化学、ポリマーなどで使用され、分子の構造を表示する無向グラフです。 これらのグラフの頂点と辺は、対応する原子とそれらの間の化学結合に対応します。

立体化学組織内。 最も一般的に使用されるのは分子ツリーです。原子に対応するすべての頂点のみを含む分子グラフのスパン ツリーです。分子ツリーのセットをコンパイルし、その同型性を確立することで、分子構造を決定し、アルカンの異性体の総数を見つけることができます。アルケンとアルキン。 分子グラフを使用すると、さまざまな化合物の分子のコーディング、命名法、構造的特徴 (分岐、環状など) に関連する問題を、分子グラフとそのツリーの純粋に数学的な特徴と特性の分析と比較に減らすことができます。それらに対応する行列。 分子の構造と化合物の物理化学的（薬理学的を含む）特性との間の多数の相関関係を特定するために、20 を超えるいわゆる相関関係が開発されています。 分子ツリーの行列と数値特性を使用して決定される、分子のトポロジカル インデックス (Wiener、Balaban、Hosoya、Plata、Randich など)。 たとえば、ウィナー指数 W = (m3 + m)/6 (m は C 原子に対応する頂点の数) は、分子体積と屈折、生成エンタルピー、粘度、表面張力、化合物のクロマトグラフィー定数、オクタン価と相関します。炭化水素の数、さらにはフィジオールの数も。 薬物の作用。 特定の物質の互変異性体とその反応性を決定するために、またアミノ酸、核酸、炭水化物、その他の複雑な天然化合物の分類に使用される分子グラフの重要なパラメーターは、平均および合計 (H) 情報容量です。 頂点がモノマーユニットに対応し、エッジがモノマーユニット間の化学結合に対応するポリマーの分子グラフを解析すると、たとえば品質につながる排除体積の影響を説明することができます。 ポリマーの予測される特性の変化。 グラフ理論と人工知能の原理を使用して、化学における情報検索システムだけでなく、分子構造の特定や有機合成の合理的な計画のための自動化システム用のソフトウェアが開発されています。 合理的な化学経路を選択するための操作をコンピュータ上で実際に実装するため。 逆合成およびシントニック原理に基づく変換では、解決オプションのマルチレベル分岐検索グラフが使用されます。その頂点は試薬と生成物の分子グラフに対応し、円弧は変換を表します。

化学技術システム (CTS) の分析と最適化の多次元問題を解決するには、フロー、情報フロー、信号および信頼性グラフの化学技術グラフが使用されます。 化学の勉強用。 多数の粒子からなる系における擾乱の物理学では、いわゆるものを使用します。 ファインマン線図はグラフであり、その頂点は物理粒子の基本相互作用、衝突後の粒子の経路のエッジに対応します。 特に、これらのグラフは、振動反応のメカニズムを研究し、反応システムの安定性を判断することを可能にします。マテリアル フロー グラフは、化学加熱システムの流量の変化を表示します。サーマル フロー グラフは、化学加熱システムの熱バランスを表示します。 グラフの頂点は、物理的な流れの熱消費が変化するデバイスに対応し、さらにシステムの熱エネルギーのソースとシンクにも対応します。 アークは物理的な熱流と架空の (デバイス内の物理化学的エネルギー変換) 熱流に対応し、アークの重みは流れのエンタルピーに等しくなります。 材料グラフと熱グラフは、複雑な化学システムの材料と熱のバランスに関する連立方程式を解くためのアルゴリズムを自動開発するためのプログラムをコンパイルするために使用されます。 情報フロー グラフは、数式系の論理情報構造を表示します。 XTSモデル。 これらのシステムを計算するための最適なアルゴリズムを開発するために使用されます。 二部情報グラフは、頂点がそれぞれ対応する無向グラフまたは有向グラフです。 方程式 f1 ～ f6 と変数 q1 ～ V であり、分岐はそれらの関係を反映しています。 情報グラフ - 方程式を解く順序を示す有向グラフ。 グラフの頂点はこれらの方程式、XTS 情報のソースと受信者に対応し、枝は情報に対応します。 変数。 シグナル グラフは、化学技術プロセスおよびシステムの数学モデルの線形方程式系に対応します。 信頼性グラフは、さまざまな信頼性指標 X を計算するために使用されます。

使用した文献:

1. Berge K.、T. g. およびその応用、フランス語からの翻訳、M.、1962 年。

2. Kemeny J.、Snell J.、Thompson J.、有限数学入門、トランス。 英語より、第 2 版、M.、1963 年。

3.Ope O.、グラフとその応用、トランス。 英語から、M.、1965年。

4. Belykh O.V.、Belyak E.V.、社会学における社会学の応用の可能性、人間と社会、第 1 巻。 1、[L.]、1966年。

5. 社会学研究における定量的方法、M.、1966年。 Belyaev E.V.、「社会学的測定の問題」、「VF」、1967 年、第 7 号。 バベラス。 本書では、タスク指向グループのコミュニケーション パターンについて説明しています。 ラーナー D.、ラスウェル H.、政治学、スタンフォード、1951 年。

6. Kemeny J. G.、Snell J.、社会科学における数学的モデル、ニューヨーク州、1962 年。 フィラメント C.、グループ構造へのグラフ理論の応用、ニューヨーク州、1963 年。 Оeser Ο. A.、Hararu F.、グラフ理論の観点からの役割構造と説明、著書: Biddle V.、Thomas E. J.、役割理論: 概念と研究、ニューヨーク、1966。E. Belyaev。 レニングラード。