グラフ理論: 基本的な概念とタスク。 データ構造としてのグラフ。 グラフ理論の実践 グラフ理論の応用的意義

1736年、ケーニヒスベルク。 プレゲルヤ川が市内を流れています。 市内には上の図に示すように 7 つの橋があります。 ケーニヒスベルクの住民は古くから、「すべての橋を一度だけ渡って渡ることは可能なのか？」という謎に悩まされてきました。 この問題は、理論的にも机上でも、実際に橋を渡って散歩することで解決されました。 これが不可能であることを証明できた人は誰もいませんでしたが、そのような「神秘的な」歩行で橋を渡ることは誰にもできませんでした。

有名な数学者レオンハルト・オイラーはこの問題を解決することに成功しました。 さらに、彼はこの特定の問題を解決しただけでなく、同様の問題を解決するための一般的な方法を考え出しました。 ケーニヒスベルクの橋の問題を解決する際、オイラーは次のように進めました。土地を点に「圧縮」し、橋を線に「引き伸ばし」ました。 このような点と点を結ぶ線で構成される図形を「図形」といいます。 カウント.

グラフは、空ではない頂点と頂点間の接続の集合です。 円はグラフの頂点と呼ばれ、矢印のある線は円弧、矢印のない線はエッジと呼ばれます。

グラフの種類:

1. 有向グラフ(簡単に言うと 有向グラフ) - エッジに方向が割り当てられます。

2. 無向グラフ線の方向のないグラフです。

3. 加重グラフ– 円弧またはエッジには重みがあります (追加情報)。



グラフを使用して問題を解決する:

タスク1。

解決策: 科学者をグラフの頂点として表し、各頂点から他の 4 つの頂点まで線を引きます。 10 行を取得し、ハンドシェイクとみなされます。

タスク2。

学校の敷地には、リンゴの木、ポプラ、カバノキ、ナナカマド、オーク、カエデ、カラマツ、マツの8本の木が生えています。 ナナカマドはカラマツより高く、リンゴの木はカエデより高く、オークはカバノキより低いが松より高く、松はナナカマドより高く、カバノキはポプラより低く、カラマツはリンゴの木より高いです。 樹木を背の低いものから高いものへと並べます。

解決：

グラフの頂点はツリーであり、ツリー名の最初の文字で示されます。 このタスクには、「低くする」と「高くする」という 2 つの関係があります。 「下にある」という関係を考えて、下の木から上の木に矢印を描きます。 山の灰がカラマツよりも高いという問題があれば、カラマツから山の灰に矢印を置きます。 最も背の低い木がカエデで、次にリンゴ、カラマツ、ナナカマド、マツ、オーク、カバノキ、ポプラであることを示すグラフが得られます。

タスク3。

ナターシャは、普通封筒と航空封筒の 2 つの封筒と、長方形、正方形、三角形の 3 つの切手を持っています。 ナターシャは手紙を送るための封筒と切手を何通り選ぶことができますか?

解決：

以下にタスクの内訳を示します。


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

準備した

レグココネツ・ウラジスラフ、クラス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 つあります。これらの個々のセクションにつながる橋の数は偶数または奇数です。したがって、この場合、セクション A につながる橋は 5 つ、残りのセクションにはそれぞれ 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 原子に対応するすべての頂点のみを含む分子グラフのメイン ツリーとしてよく使用されます。 木とその同型性の確立により、彼らが言うことを決定することが可能になります。 構造を調べて、アルカン、アルケン、アルキンの異性体の総数を調べます。

タンパク質ネットワーク

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

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

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

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

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

もう 1 つの例。 写真は聖書の家系図を示しています [付録図 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

応用

応用

論理問題の解決に関連する問題の中でも、この種の問題にグラフ理論を適用するという問題は、近年研究者の注目を集めています。

グラフ理論は、現在集中的に開発されている離散数学の分野です。 これは、通信ネットワーク、電気・電子機器の回路、化学分子、人々の関係など、多くのオブジェクトや状況がグラフ モデルの形式で記述されているという事実によって説明されます。

グラフ タスクには、想像力を養い、論理的思考を向上させるために使用できる多くの利点があります。 グラフの問題は、楽しく遊び心のある形式で提示できます。

研究対象 この作品では、グラフを使用して論理的な問題を解決します。

研究の目的： 論理的な問題を解決するためにグラフ装置を適用します。

仮説： 私たちの意見では、多くの論理問題を解決するのにそれほど労力はかからないため、これにはグラフ理論を使用します。

研究目的：

    グラフを使用して問題を解決することを検討します。

    問題をグラフ言語に翻訳することを学びます。

    従来の問題解決手法とグラフ理論手法を比較します。

1736 年、偉大な数学者レオンハルト オイラーは、ケーニヒスベルク橋問題と呼ばれるパズルの解決策を発見しました。 カリーニングラード（以前はケーニヒスベルクと呼ばれていた都市）を流れるプレーゲル川は、2 つの島を流れています（図 1 図 1）。 オイラーの時代には、図に示すように川岸と島々は橋で結ばれていました。 このパズルでは、4 つの陸塊すべてを 1 回通過するルートを見つける必要があり、パスの終点と始点が一致する必要があります。

写真1

L.オイラーは、パズルの条件を満たすルートが存在しないことを証明し、この種のパズルを解くための理論を開発しました。 「グラフ入門」コースの導入部の内容を理解していれば、L. オイラーの推論のアイデアを再現するのは難しくありません。 これを行うには、まず図 1 を図 2 に示す図に置き換える必要があります。図では、島と海岸が点で表されています。

図2

図 2 に示す図は、厳密に言えばグラフではありません。複数のエッジがあります。 しかし、この謎が解けた1736年がグラフ理論が生まれた年と一般に考えられている。

100 年以上後の 1874 年、ドイツの科学者 G. キルヒホッフは、後にグラフ理論で市民権を得た方法と概念を使用して、電気回路の電流値を決定する効果的な方法を開発しました。 さらに 10 年後、イギリスの数学者 A. ケリ (彼の母親はロシア人で、彼はロシア語を話し、ロシアの数学文献に従った。彼は最初から N.I. ロバチェフスキーの考えを理解し、支持していた数少ない数学者の一人であった) は、次の理論を発展させた。指定された数の飽和炭化水素の異性体の数を数えるツリー n炭素原子。

数学では、グラフは頂点と呼ばれる点の有限の集合です。 グラフのエッジと呼ばれる線で相互に接続されているものはどれですか。

グラフは、平面 (紙、板) 上に描かれた点の集合であり、そのいくつかのペアが線で接続されています。 点はグラフの頂点と呼ばれ、線はエッジと呼ばれます。 頂点の次数は、頂点から現れるエッジの数です。

地理地図を見ていると、鉄道網がすぐに目に止まります。 これは典型的なグラフです。円はグラフの頂点であるステーションを表し、それらを接続するパスはエッジを表します。

図3

図 3 のグラフは、村 M、A、B、C、D の間の道路の図を示しています。ここでは、2 つの頂点ごとにエッジで接続されています。 このようなグラフは完全と呼ばれます。 図中の数字は、これらの道路沿いの村間の距離を示しています。 村 M に郵便局があり、郵便配達員は他の 4 つの村に手紙を届けなければなりません。 さまざまな旅行ルートがあります。 最短のものを選択するにはどうすればよいですか? 最も簡単な方法は、すべてのオプションを分析することです。 新しいグラフはこれを行うのに役立ち、可能なルートを簡単に確認できるようになります。 頂上のピークMがルートの始まりです。 そこから、A へ、B へ、C へ、または D へという 4 つの異なる方法で旅を始めることができます。村の 1 つを訪れた後、ルートを続けるには 3 つのオプションがあり、次に 2 つ、そして最後の村への道を進みます。合計 43 21  24 通り。

店舗に商品を配送したり、建設現場に資材を配送したりするための最適なオプションを見つけるときにも、同様の問題がよく発生します。

最も単純な問題の 1 つを考えてみましょう。「赤、青、黄、緑の鉛筆が 4 つの箱に 1 つずつ入っています。 鉛筆の色は箱の色と異なります。 緑の鉛筆は青い箱に入っているが、赤い鉛筆は黄色の箱に入っていないことが知られています。 各鉛筆はどの箱に入っていますか?」

鉛筆と箱を点で表しましょう。 実線は鉛筆が対応するボックス内にあることを示し、点線は鉛筆が入っていないことを示します。 次に、問題を考慮して、次のようになります。 G 1 (図4)。

図4

次に、次のルールに従ってグラフを完成させます。ボックスの中にちょうど 1 本の鉛筆が入るので、各点から 1 本の実線と 3 本の点線が出てくるはずです。 結果はグラフです G 2 、問題の解決策が得られます。

一般的な科学や方法論の文献で通常論理的と呼ばれる問題を解決する場合、原則として、学校の知識やスキルに大きく依存することはありません。 この点において、それらは伝統的に創意工夫の尺度、数学的能力、思考の鋭さ、記憶力のレベルの指標と考えられており、学校の数学クラブでよ​​く議論されます。

グラフを使用して多くの論理的な問題を解決することは、低学年の学生にとっても非常に簡単です。 これを行うには、グラフとその最も明白な特性を直感的に理解するだけで十分です。

いくつかのよく知られた問題を解決するためにグラフを使用する例を見てみましょう。 この場合、オブジェクトを点で表し、オブジェクト間の関係をセグメントで表します (点の位置とセグメントの長さは任意です)。

適用される解決方法の観点から論理的問題の構造を明確にすることで、そのような問題の特定のクラスを分離することが可能になります。

タスク1。 ベロクロフ、チェルノフ、リゾフという 3 人の友人が話しています。 ブルネットの女性はベロクロフにこう語った。「私たちのうちの一人が金髪、もう一人がブルネット、三人目が赤なのが不思議だけど、髪の色が姓と一致する人は一人もいない」 あなたの友達はそれぞれどんな髪の色をしていますか?

具体的な解決策を紹介しましょう。 問題ステートメントで指定された関係のグラフを作成してみましょう。 そのためには、まず、たくさんの姓を強調表示しましょう Mそしてたくさんの髪の色 に、その要素はドットで示されます。 セットポイント Mそれらを文字 B、Ch、R (ベロクロフ、チェルノフ、リゾフ) と呼びましょう。 2番目のセットのポイント - b、br、p（金髪、ブルネット、赤）。 あるセットの点が別のセットの点に対応する場合は実線で接続し、対応しない場合は破線で接続します。 問題の状態は不一致のみを示しているため、最初に図 5 に示すグラフが表示されます。

図5

問題の条件から、集合の各点について次のことがわかります。 Mたくさんあるトンカのうち、たったひとつしかない に、これは最初の点に対応し、逆にセットの各点に対応します。 にセットの 1 つの点にのみ対応します M.タスクは、セットの要素間で唯一可能な対応関係を見つけることになります。 Mそして に、つまり、セットの対応する点を接続する 3 本の実線を見つけることです。

問題を解決する原理は単純です。 ある点が別のセットの 2 つの点に破線で接続されている場合、その 3 番目の点に実線で接続する必要があります。 したがって、図 5 のグラフには、点 B と点、P と点 b を結ぶ実線が追加されます (図 6)。

図7

したがって、この図のグラフでは、ベロクロフは赤毛、チェルノフは金髪、リジョフはブルネットという答えが自動的に読み取られます。 同じ手法を使用して、たとえば問題 2 と 3 を解決することができます。

タスク2。 ワーニャ、コーリャ、ミーシャのためにパイが焼かれました。1つはキャベツ、もう1つは米、3つ目はリンゴです。 ミーシャはアップルパイが好きではなく、キャベツと一緒に食べません。 ヴァーニャはキャベツパイが好きではありません。 誰がどのパイを食べるの？

タスク3。 機械工、旋盤工、溶接工という 3 人の友人が同じ工場で働いています。 彼らの姓はボリソフ、イワノフ、セミョノフです。 鍵屋には兄弟も姉妹もおらず、友人の末っ子です。 セミョノフはボリソフの妹と結婚しており、ターナーよりも年上である。 整備士、旋盤工、溶接工の名前は何ですか?

上記の問題は、テーブルを使用してうまく解決できます。 この方法またはその修正方法は、多くの一般的な科学書籍や教材で推奨され、議論されています。 ただし、点とセグメントで表されるグラフの使用がより便利で正当であることが判明する問題のクラスを示すことは可能です。 決定においてトーナメント表やその一般化などの表の手法を使用すると、推論の重要な部分が「口頭」で実行されることになります。 同時に、問題の状況や中間結果に繰り返し戻り、多くのことを覚えて、適切なタイミングで受け取った情報を使用する必要があります。 このタイプの問題には、3 つ以上のオブジェクトのセットが考慮されている問題が含まれます。

タスク4。 3人の同志 - イワン、ドミトリー、ステパン - モスクワ、レニングラード、キエフの学校でさまざまな科目（化学、生物学、物理学）を教えています。 既知:

1. イワンはモスクワでは働いておらず、ドミトリーもレニングラードでは働いていない。

2. モスクヴィッチは物理学を教えていない。

3. レニングラードで働いている人は化学を教えています。

4. ドミトリーは生物学を教えません。

それぞれの同志はどの都市でどの科目を教えていますか?

解決。 名前のセット、オブジェクトのセット、都市のセットの 3 つのセットを区別しましょう。 図 4 の各セットの要素は、独自の点によって与えられます (この図の文字は、対応する単語の最初の文字です)。 異なるセットの 2 つの点が異なる人々の特徴を特徴付ける場合、そのような点を破線で結びます。 異なるセットの 2 つの点が 1 人の人の特徴に対応する場合、そのような点をペアにして実線で接続します。 問題の条件に従って、他の各セット内の任意のセットの各点に対して、それに対応する点が 1 つだけ存在することが重要です。

図8

したがって、図 8 のグラフには、条件で指定されたセットのすべての要素とそれらの間の関係が含まれています。 グラフ言語の問題は、結局のところ、異なるセットの頂点を持つ 3 つの「中実」三角形を見つけることになります。

図 8 のグラフを考えてみましょう。破線のセグメント XD はそれ自体を示唆しています。実際、A は X に対応しますが、同時に A は D に対応しません。つまり、X は D に対応できません。したがって、これに対する典型的なグラフ演算は次のようになります。ある種の問題が使用されます。3 つの異なるセットの頂点を持つ三角形の場合、1 つの辺が実線、2 番目の辺が破線である場合、3 番目の辺は破線でなければなりません。 問題の条件から、グラフ上の別の操作は均一であることがわかります。ある点が破線のセグメントによって 2 番目のセットの 2 つの点に接続されている場合、その点は実線のセグメントによってこのセットの 3 番目の点に接続されるはずです。 このようにして、DF の連続したセグメントが描画されます。 次に、破線セグメント DM (三角形 DFM では側面 DF が実線、FM が破線)、DK が実線 (DM と DL が破線) を描きます。次に、点 F と K を実線セグメントで接続します。 異なるセットの頂点を持つ三角形の 2 つの辺がソリッドである場合、3 番目の辺もソリッドになります。 最初の「実線」三角形 DFK が見つかりました。 したがって、問題の本文に戻ることなく、上記のグラフに対する自然な操作のみに基づいて、解決策を見つけます (図 9)。

図9

セグメントが実行された順序に注目してください: HD、DF、DM、DK、FC、MS、IL、CI、BM、BS。 結果として得られる 3 つの「中実」三角形のそれぞれの頂点によって、問題の答えが決まります。イワンはレニングラードで化学を教え、ドミトリーはキエフで物理を教え、ステパンはモスクワで生物学を教えています。

次の問題では、グラフを使用することで 2 つの解の存在を検出できます。

タスク5。 マーシャ、リダ、ジェーニャ、カティアは、異なる楽器 (チェロ、ピアノ、ギター、ヴァイオリン) を演奏できますが、それぞれ 1 つしか使用できません。また、異なる外国語 (英語、フランス語、ドイツ語、スペイン語) も話せますが、それぞれ 1 つしか使用できません。 。 周知された ：

1. ギターを弾く女の子はスペイン語を話します。

2. リダはヴァイオリンもチェロも弾けませんし、英語もわかりません。

3. マーシャはヴァイオリンもチェロも弾けませんし、英語もわかりません。

4. ドイツ語を話す女の子はチェロを弾きません。

5. ジェーニャはフランス語を知っていますが、バイオリンを弾きません。

誰がどんな楽器を演奏し、どんな外国語を知っていますか?

問題の状況は、図 10 に示すグラフに対応します。

図10

ここでの表記と解法の原理は問題 4 と同じです。KS、VZH、VF、AK という実線を順番に描きます (図 11)。

図11

したがって、2 つの「中実」三角形 ZHVF および KSA が形成されます。 私たちは打ち上げロケットの別の連続セグメントを実行します。 ここで、問題の条件によって、RN と GI の各ペアの 3 番目の点の明確な選択が保証されないことがわかりました。 「実線」三角形では、MGI と OSR、または LGI と MRN のオプションが可能です。 したがって、この問題には 2 つの解決策があります。

グラフを使用して条件の冗長性を非常に簡単に検出できる問題を提示しましょう。

タスク6。 さまざまな職業の 6 人のパートナー (旋盤工、機械工、エンジニア、教師、医師、運転手) がチェス トーナメントに参加しました。 既知:

1. 第1ラウンドでは、アンドレーエフは医師と、教師はボリソフと、グリゴリエフはエフドキモフとプレーした。

2. 第2ラウンドでは、ドミトリエフはターナーとプレーし、ドクターはボリソフとプレーした。

3. 第3ラウンドでは、エフドキモフはエンジニアとプレーした。

4. トーナメントの終わりに、順位は次のように配分されました - ボリソフ私グリゴリエフとエンジニアが共有した場所ⅡそしてⅢドミトリエフが取った場所Ⅳゾロタレフと整備士は5位と6位を分け合った。

グリゴリエフ、ドミトリエフ、エフドキモフはどのような職業に就いていましたか?

画像や数式を使わずに作品のテキストを掲載します。
作品の完全版は、[作品ファイル] タブから PDF 形式で入手できます。

導入

「数学で覚えるべきは公式ではなく、思考のプロセスです...」

E.I.イグナティエフ

グラフ理論は、現在集中的に開発されている数学の分野です。 これは、多くのオブジェクトや状況がグラフ モデルの形式で記述されているという事実によって説明され、これは社会生活が正常に機能するために非常に重要です。 この要素が、彼らのより詳細な研究の妥当性を決定します。 したがって、この作品のテーマは非常に関連性があります。

目標研究活動: さまざまな知識分野および論理問題の解決におけるグラフ理論の応用の特徴を見つけること。

目標では次のことが特定されました タスク:

    グラフ理論の歴史を知る。

    グラフ理論の基本概念とグラフの主な特徴を学びます。

    さまざまな知識分野におけるグラフ理論の実際の応用を示します。

    グラフを使用して問題を解決する方法を検討し、独自の問題を作成します。

オブジェクト研究: グラフ手法を適用するための人間の活動範囲。

アイテム研究: 数学「グラフ理論」のセクション。

仮説。私たちは、グラフ理論を学ぶことで生徒が数学の論理問題を解くのに役立ち、それが生徒の将来の興味を形作るだろうと仮説を立てています。

メソッド研究活動:

私たちの調査では、次の方法が使用されました。

1) さまざまな情報源を活用する。

2) 資料の説明、収集、体系化。

3) 観察、分析、比較。

4) タスクの準備。

理論的および実際的な重要性この作品は、その結果がコンピュータ サイエンス、数学、幾何学、描画、教室での教育に使用できるという事実だけでなく、このトピックに興味のある幅広い読者にも提供できるという事実によって決定されました。 著者はその研究の中で、多くの知識分野におけるグラフの使用例を多数提示し、独自の課題を作成しているため、この研究成果には明確な実用的な方向性があります。 この教材は数学の選択授業で使用できます。

第 I 章 研究テーマに関する資料の理論的検討

    1. グラフ理論。 基本概念

数学では、「グラフ」は線で結ばれた多数の点を表す絵として表すことができます。 「伯爵」はラテン語の「グラフィオ」に由来しており、よく知られた高貴な称号のように私は書きます。

数学では、グラフの定義は次のように与えられます。

数学における「グラフ」という用語は次のように定義されます。

グラフ - これは有限の点の集合です - ピーク, 線でつながることができる - リブ .

グラフの例には、多角形の図、電気回路、航空会社、地下鉄、道路などの概略図が含まれます。 家系図はグラフでもあり、頂点は一族のメンバーであり、家族の絆はグラフの端として機能します。

米。 1グラフの例

1つの頂点に属する辺の数を といいます。 グラフの頂点次数 . 頂点の次数が奇数の場合、その頂点は - 奇数 。 頂点の次数が偶数の場合、その頂点は と呼ばれます。 平.

米。 2グラフの頂点

ヌルグラフ は、エッジによって接続されていない孤立した頂点のみで構成されるグラフです。

完全なグラフ は、頂点の各ペアがエッジで接続されているグラフです。 すべての対角線が描かれた N 角形は、完全なグラフの例として機能します。

開始点と終了点が一致するグラフ内のパスを選択した場合、そのようなパスは次のように呼ばれます。 グラフサイクル . グラフの各頂点が最大 1 回通過する場合、 サイクル呼ばれた 単純 .

グラフ内の 2 つの頂点がすべてエッジで接続されている場合、これは 接続されています グラフ。 グラフは次のように呼ばれます 無関係 接続されていない頂点のペアが少なくとも 1 つ含まれている場合。

グラフが接続されているがサイクルを含まない場合、そのようなグラフは と呼ばれます。 木 .

    1. グラフの特徴

伯爵の道 共通の頂点を共有する 2 つの隣接するエッジが 1 回だけ出現するシーケンスです。

頂点の最短チェーンの長さ あるそしてbは呼ばれます 距離 峰の間 あるおよび b.

バーテックス あ呼ばれた 中心 グラフ、頂点間の距離の場合 あ他の頂点は可能な限り最小の頂点になります。 そんな距離あるのね 半径 グラフ。

グラフの任意の 2 つの頂点間の最大可能距離は次のように呼ばれます。 直径 グラフ。

グラフの色付けと応用。

地理地図をよく見ると、鉄道や高速道路がグラフで表示されます。 さらに、地図上には国（地方、地域）間の境界線で構成されるグラフがあります。

1852 年、英国の学生フランシス ガスリーは、英国の地図に色を塗り、各郡を別の色で強調表示するという課題を与えられました。 塗料の選択肢が少なかったため、ガスリーはそれらを再利用しました。 彼は、国境の共通部分を共有する郡が必然的に異なる色で塗られるように色を選択しました。 さまざまな地図を着色するために必要な塗料の最小量はどれくらいかという疑問が生じました。 フランシス・ガスリーは、証明はできませんでしたが、4 色あれば十分であると示唆しました。 この問題は学生サークルで激しく議論されましたが、後に忘れ去られました。

「4 色問題」はますます関心を集めましたが、著名な数学者によってさえも解決されることはありませんでした。 1890 年、英国の数学者パーシー ヒーウッドは、どんな地図でも色を塗るには 5 色で十分であることを証明しました。 40 か国未満を描いた地図を色づけするには 4 色で十分であることを証明できたのは 1968 年のことです。

1976 年、この問題は 2 人のアメリカ人数学者 Kenneth Appel と Wolfgangt Haken によってコンピュータを使用して解決されました。 それを解決するために、すべてのカードを2000種類に分けました。 4 色では色を付けるのに十分でないカードを識別するために、すべてのタイプを検査するコンピューター プログラムが作成されました。 コンピュータは 3 種類の地図しか研究できなかったので、数学者はそれらを自分で研究しました。 その結果、2000種類のカードすべてを着色するには4色で十分であることが判明した。 彼らは 4 色の問題の解決策を発表しました。 この日、アペルさんとハーケンさんが働いていた大学の郵便局では、すべての切手に「4色で十分です」と書かれたスタンプが押された。

4 つの色の問題を少し違った方法で想像することもできます。

これを行うには、グラフの形式で表す任意の地図を考えます。州の首都はグラフの頂点であり、グラフの端は州が共通の境界線を持つ頂点 (首都) を接続します。 このようなグラフを得るには、次の問題を定式化します。共通のエッジを持つ頂点が異なる色で着色されるように、4 つの色を使用してグラフを着色する必要があります。

オイラー グラフとハミルトニアン グラフ

1859年、英国の数学者ウィリアム・ハミルトンは、20の頂点にスタッドが付いている木製の十二面体（十二面体）というパズルを発表しました。 それぞれの山頂には、カントン、デリー、ブリュッセルなど、世界最大の都市の名前が付いていました。 課題は、各頂点を 1 回だけ訪問しながら、多面体のエッジに沿って進む閉じたパスを見つけることでした。 道を示すために、釘に引っ掛けた紐が使用されました。

ハミルトン サイクルは、そのパスがグラフのすべての頂点を 1 回通過する単純なサイクルであるグラフです。

カリーニングラード市 (旧ケーニヒスベルク) はプレーゲル川沿いにあります。 川は 2 つの島を洗い流し、それらの島は互いに、また橋で岸とつながっていました。 古い橋はもうありません。 彼らの記憶は街の地図の上にだけ残っている。

ある日、都市住民が友人に、すべての橋を歩いて渡り、それぞれの橋を 1 回だけ訪れて、歩き始めた場所に戻ることは可能かどうか尋ねました。 この問題は多くの町民の関心を集めましたが、誰も解決できませんでした。 この問題は、多くの国の科学者の関心を集めています。 この問題の解決策は数​​学者レオンハルト・オイラーによって得られました。 さらに、彼はそのような問題を解決するための一般的なアプローチを策定しました。 これを行うために、彼は地図をグラフに変換しました。 このグラフの頂点は土地であり、端はそれをつなぐ橋です。

ケーニヒスベルク橋問題を解決しながら、オイラーはグラフの特性を定式化することに成功しました。

    グラフのすべての頂点が均等であれば、1 つの頂点から開始して 1 つのストロークで同じ頂点で終了することによって (同じ線に沿って 2 回描画せず、紙から鉛筆を離さずに) グラフを描くことができます。

    奇数の頂点が 2 つあるグラフがある場合、その頂点も 1 つのストロークで接続できます。 これを行うには、一方の頂点から開始して、もう一方の奇数の頂点で終了する必要があります。

    奇数の頂点が 2 つ以上あるグラフがある場合、そのグラフは 1 つのストロークで描画できません。

これらの特性を橋の問題に適用すると、研究対象のグラフのすべての頂点が奇数であることがわかります。これは、このグラフを 1 つのストロークで接続できないことを意味します。 すべての橋を一度渡って、旅が始まった場所で旅を終えることは不可能です。

グラフに、グラフのすべてのエッジを 1 回含むサイクル (必ずしも単純である必要はない) がある場合、そのようなサイクルは と呼ばれます。 オイラーサイクル . オイラー連鎖（パス、サイクル、コンター）は、グラフのすべてのエッジ（円弧）を一度に含む連鎖（パス、サイクル、コンター）です。

第 2 章 研究とその結果の説明

2.1. 研究の段階

仮説を検証するために、研究には 3 つの段階が含まれていました (表 1)。

研究段階

表1。

使用される方法

問題の理論的研究

教育および科学文献を調査および分析します。

- 独立した思考;

- 情報源の調査。

- 必要な文献を検索します。

問題の実践的研究

グラフの実際の応用分野を検討および分析します。

- 観察;

- 分析;

- 比較;

- 調査。

ステージ3。 結果の活用

調べた情報を要約します。

- システム化;

 報告書（口頭、書面、資料の実演付き）

2017年9月

2.2. グラフの実用化分野

グラフと情報

情報理論では、二分木の特性が広範囲に利用されます。

たとえば、さまざまな長さの 0 と 1 の特定のシーケンスの形式で特定の数のメッセージをエンコードする必要がある場合です。 平均語長が他の確率分布と比較して最小である場合、そのコードは、コードワードの特定の確率に対して最適であると見なされます。 この問題を解決するために、ハフマンは、検索理論の枠組み内でコードをツリー グラフとして表現するアルゴリズムを提案しました。 頂点ごとに質問が提案され、その答えは「はい」または「いいえ」のいずれかになります。これは、頂点から出ている 2 つのエッジに対応します。 このようなツリーの構築は、必要なものを確立した後に完了します。 これは、複数の人にインタビューする場合に使用できます。前の質問に対する答えが事前に不明な場合、インタビュー計画は二分木として表されます。

グラフと化学

A. Cayley は、飽和 (または飽和) 炭化水素の考えられる構造の問題も考慮しました。その分子は次の式で与えられます。

CnH 2n+2

すべての炭化水素原子は 4 価であり、すべての水素原子は 1 価です。 最も単純な炭化水素の構造式を図に示します。

各飽和炭化水素分子はツリーとして表すことができます。 すべての水素原子が除去されると、残った炭化水素原子は次数が 4 以下の頂点を持つツリーを形成します。 これは、考えられる望ましい構造 (特定の物質の相同体) の数が、頂点次数が 4 以下のツリーの数に等しいことを意味します。この問題は、特定のタイプのツリーを列挙するという問題に帰着します。 D. Polya は、この問題とその一般化を検討しました。

グラフと生物学

細菌の繁殖プロセスは、生物学理論で見られる分岐プロセスのタイプの 1 つです。 それぞれの細菌を一定時間後に死滅させるか、2 つに分裂させます。 したがって、1 つの細菌について、その子孫の繁殖の二分木が得られます。 問題の質問は次のとおりです。その中にはいくつのケースが含まれていますか? k 1 つの細菌の n ​​世代目の子孫? 生物学におけるこの関係は、ゴルトン・ワトソン過程と呼ばれ、必要なケースの必要な数を示します。

グラフと物理学

アマチュア無線家にとって、難しく退屈な作業は、プリント回路 (誘電体 - 絶縁材料のプレートと金属ストリップの形でエッチングされたトラック) を作成することです。 トラックの交差は、特定のルールに従って、特定の点（三極管、抵抗器、ダイオードなどの位置）でのみ発生します。 その結果、科学者は頂点を持つ平らなグラフを描くという課題に直面することになります。

したがって、上記のすべてにより、グラフの実用的な価値が確認されます。

インターネット数学

インターネットは、情報を保存および送信するための相互接続されたコンピュータ ネットワークの世界的なシステムです。

インターネットはグラフとして表すことができます。グラフの頂点はインターネット サイト、端はサイト間を結ぶリンク (ハイパーリンク) です。

数十億の頂点と辺を持つ Web グラフ (インターネット) は常に変化しています。サイトは自然に追加されたり消えたり、リンクは消えたり追加されたりします。 ただし、インターネットは数学的な構造を持ち、グラフ理論に従い、いくつかの「安定した」特性を持っています。

Web グラフはまばらです。 頂点の数倍のエッジしか含まれていません。

インターネットはまばらであるにもかかわらず、非常に混雑しています。 リンクを使用すると、5 ～ 6 回のクリックであるサイトから別のサイトに移動できます (有名な「6 回のハンドシェイク」理論)。

ご存知のとおり、グラフの次数は頂点が属するエッジの数です。 Web グラフの頂点の次数は、ある法則に従って分布します。つまり、リンク (エッジ) の数が多いサイト (頂点) の割合が小さく、リンクの数が少ないサイトの割合が大きくなります。 数学的には次のように書くことができます。

ここで、 は特定の次数の頂点の割合、 は頂点の次数、 はウェブ グラフ内の頂点の数に依存しない定数です。 サイト (頂点) を追加または削除するプロセス中には変化しません。

このべき乗則は、生物学的ネットワークから銀行間までの複雑なネットワークに普遍的です。

インターネット全体は、サイトに対するランダムな攻撃に対して耐性があります。

サイトの破壊と作成は独立して同じ確率で発生するため、Web グラフは 1 に近い確率で整合性を維持し、破壊されません。

インターネットを研究するには、ランダムなグラフ モデルを構築する必要があります。 このモデルは実際のインターネットの特性を備えている必要があり、複雑になりすぎないようにする必要があります。

この問題はまだ完全に解決されていません。 この問題を解決すること、つまりインターネットの高品質モデルを構築することにより、情報検索を改善し、スパムを識別し、情報を広めるための新しいツールを開発できるようになります。

生物学的および経済的モデルの構築は、インターネットの数学的モデルを構築するという課題が生じるよりもずっと早くに始まりました。 しかし、インターネットの開発と研究の進歩により、これらすべてのモデルに関する多くの質問に答えることが可能になりました。

インターネット数学は、生物学者 (細菌集団の増殖を予測する)、投資家 (危機のリスク) など、多くの専門家によって需要があります。 このようなシステムの研究は、応用数学とコンピューター サイエンスの中心的な分野の 1 つです。

グラフを使用したムルマンスク。

人が新しい都市に到着すると、通常、最初の願望は主要な観光スポットを訪問することです。 しかし同時に、時間は限られていることが多く、出張の場合は非常に短いです。 そのため、事前に観光の計画を立てる必要があります。 グラフはルートを構築するのに非常に役立ちます。

例として、空港から初めてムルマンスクに到着する典型的なケースを考えてみましょう。 私たちは以下の観光スポットを訪れる予定です。

1. 水上の救世主海洋正教会;

2. 聖ニコラス大聖堂;

3. 水族館;

4. 猫セミョンの記念碑。

5. 原子力砕氷船「レーニン」。

6. ムルマンスクの公園の灯り。

7. パーク・バレー・オブ・コンフォート。

8. コラ橋。

9. ムルマンスク海運会社の歴史博物館。

10. ファイブコーナーズスクエア。

11. 海上貿易港

まず、地図上でこれらの場所を見つけて、場所とアトラクション間の距離を視覚的に表現しましょう。 道路網もかなり整備されており、車での移動もそれほど難しくありません。

地図上の観光スポット (左側) とその結果のグラフ (右側) は、付録 No. 1 の対応する図に示されています。 したがって、新参者はまずコラ橋の近くを通過します（そして、必要に応じて橋を前後に渡ることができます）。 その後、ムルマンスク公園の灯りや慰めの谷でリラックスして、先に進みます。 結果として、最適なルートは次のようになります。

グラフを利用することで、世論調査のスキームを可視化することもできます。 例は付録 No. 2 に示されています。 与えられた回答に応じて、回答者にはさまざまな質問が行われます。 たとえば、社会学調査 No. 1 で、回答者が科学の中で数学が最も重要であると考えている場合、物理の授業に自信があるかどうか尋ねられます。 もし彼がそうでないと考えるなら、2番目の質問は人文科学の需要に関するものになるだろう。 このようなグラフの頂点は質問であり、端は回答の選択肢です。

2.3. 問題解決へのグラフ理論の応用

グラフ理論は、数学、生物学、コンピューター サイエンスなど、多くの主題分野の問題を解決するために使用されます。 グラフ理論を使って問題を解く原理を学び、研究テーマに基づいて独自の問題を作成しました。

タスクその1。

高校の同窓会で5人の同級生が握手を交わした。 握手は何回行われましたか？

解決策: クラスメートをグラフの頂点で表しましょう。 各頂点を他の 4 つの頂点に線で接続しましょう。 10行あります、これは握手です。

答え: 10 回の握手 (各行は 1 回の握手を意味します)。

タスクその2。

家の近くにある祖母の村には、ポプラ、オーク、カエデ、リンゴの木、カラマツ、カバノキ、ナナカマド、マツの 8 本の木が生えています。 ナナカマドはカラマツより高く、リンゴの木はカエデより高く、オークはカバノキより低いが松より高く、松はナナカマドより高く、カバノキはポプラより低く、カラマツはリンゴの木より高いです。 木の高さは最も高いものから最も低いものまでどのような順序で配置されますか?

解決：

ツリーはグラフの頂点です。 それらを丸の中の最初の文字で表しましょう。 低い木から高い木へ矢印を描いてみましょう。 ナナカマドはカラマツより高いので、カラマツからナナカマドに矢を置き、カバノキはポプラより低いので、ポプラからカバノキに矢を当てる、などと言われています。 最も背の低い木がカエデ、次にリンゴ、カラマツ、ナナカマド、マツ、オーク、カバノキ、ポプラであることがわかるグラフが得られます。

答え：カエデ、リンゴ、カラマツ、ナナカマド、松、樫、樺、ポプラ。

タスクその3。

お母さんは普通封筒と航空封筒の 2 枚と、正方形、長方形、三角の 3 枚の切手を持っています。 お母さんはお父さんに手紙を送るための封筒と切手を何通り選ぶことができますか?

答え: 6 つの方法

タスクその4。

集落A、B、C、D、Eの間には道路が建設されています。 点 A と点 E の間の最短経路の長さを決定する必要があります。図に示されている長さの道路に沿ってのみ移動できます。

タスクNo.5。

クラスメートのマキシム、キリル、ヴォヴァの３人はスポーツを志し、スポーツ部門の選考に合格した。 少年1人がバスケットボール部門に応募し、3人がホッケーを希望したことが知られている。 マキシムはセクション 1 のみのオーディションを受け、キリルは 3 つのセクションすべてに選ばれ、ヴォヴァはセクション 2 に選ばれました。どのスポーツセクションに選ばれたのは男子生徒のうち誰ですか?

解決策: この問題を解決するには、グラフを使用します。

バスケットボールの格言

フットボールキリル

ホッケー ヴォバ

以来 バスケットボール 1本の矢印だけが進み、キリルがセクションに選ばれました バスケットボール。 そうすればキリルはプレーしないでしょう ホッケー、つまり、 ホッケーこのセクションのみをオーディションしたマキシムによって選ばれた場合、Vovaは サッカー選手.

タスクその6。

一部の教師の病気のため、学校の校長は、以下の状況を考慮して、少なくとも 1 日分の学校スケジュールの一部を作成する必要があります。

1. 生命安全教師は最後のレッスンのみを行うことに同意します。

2. 地理教師は 2 番目または 3 番目のレッスンを行うことができます。

3. 数学者は、最初のレッスンのみまたは 2 番目のレッスンのみを行う準備ができています。

4. 物理教師は、第 1 レッスン、第 2 レッスン、または第 3 レッスンのいずれかを行うことができますが、1 つのクラスに限ります。

学校の校長はどのようなスケジュールを立てれば、すべての教師が満足できるのでしょうか？

解決策: この問題は考えられるすべてのオプションを実行することで解決できますが、グラフを描くとより簡単になります。

1. 1) 物理 2. 1) 数学 3. 1) 数学

2) 数学 2) 物理学 2) 地理

3) 地理 3) 地理 3) 物理学

4) OBZH 4) OBZH 4) OBZH

結論

この研究では、グラフ理論が詳細に研究され、グラフの研究が論理的問題の解決に役立つという仮説が証明されました。さらに、科学のさまざまな分野のグラフ理論が考慮され、7 つの問題がまとめられました。

問題の解決策を見つける方法を生徒に教えるときにグラフを使用すると、生徒はグラフィック スキルを向上させ、一部の点が線で結ばれた有限の点のセットに関する特別な言語で推論を伝えることができます。 これらすべてが、生徒に思考を教えるという仕事に貢献します。

思考力の発達における教育活動の効果は、数学の問題を解決する際の生徒の創造的活動の程度に大きく依存します。 したがって、学童の精神活動を活性化するような数学的な課題や演習が必要です。

学校の選択授業における課題の適用とグラフ理論の要素の使用は、生徒の精神活動を活性化するという目標を正確に追求しています。 私たちの研究に関する実践的な資料は、選択数学の授業に役立つと信じています。

したがって、研究作業の目標は達成され、問題は解決されました。 将来的には、グラフ理論の研究を続け、独自のルートを開発する予定です。たとえば、ZATO アレクサンドロフスクのスクールバスからムルマンスクの博物館や思い出の場所までの周遊ルートをグラフを使用して作成するなどです。

使用した参考文献のリスト

    ベレジナ L. ユ「グラフとその応用」 - M.: 「啓蒙」、1979 年

    ガードナー M.「数学的余暇」、M.「ミール」、1972 年

    ガードナー M.「数学パズルとエンターテイメント」、M.「ミール」、1971

    ゴルバチョフ A.「オリンピック問題集」 - M. MTsNMO、2005

    Zykov A. A. グラフ理論の基礎。 - M.: 『University Book』、2004年。 - P. 664

    カサトキン V. N.「数学の異常な問題」、キエフ、「ラディアンスカ学校」、1987 年

    数学コンポーネント / エディターおよびコンパイラー N.N. アンドレーエフ、S.P. コノバロフ、ニューメキシコ州 パニュシキン。 - M.: Foundation "数学練習曲" 2015 - 151 p.

    メルニコフ O. I. 「グラフ理論における面白い問題」、Mn. 「テトラシステムズ」、2001

    メルニコフ O.I. 伯爵の国では分からない: 学生向けのマニュアル。 エド。 3番目、ステレオタイプ。 M.: KomKniga、2007. - 160 p.

    オレニク S. N.、ネステレンコ ユ. V.、ポタポフ M. K. 「古い面白い問題」、M. 「科学」、1988 年

    Ore O.「グラフとその応用」、M.「ミール」、1965

    ハラリ F. グラフ理論 / 英語からの翻訳。 そして序文 V.P.コジレバ。 エド。 G.P.ガブリロワ。 エド。 2番目。 - M.: 論説 URSS、2003 年。 - 296 p。

付録 No. 1

主要観光スポットを巡る最適なルートを作成

グラフを使用したムルマンスク。

最適なルートは次のようになります。

8.コラ橋6． ムルマンスクの公園の灯り7． コンフォートのパークバレー２． 聖ニコラス大聖堂10. ファイブコーナーズスクエア5． 原子力砕氷船「レーニン９」。 ムルマンスク海運会社の歴史博物館11. 海上貿易港１． 水上の救世主海洋正教会4． 猫セミョンの記念碑3． 海洋水族館。

ムルマンスクの観光スポットガイド

付録 No. 2

社会学調査第1、2

教育版

ユユキン・ニコライ・アレクセーヴィチ

LR番号 印鑑に署名

うーん。 エド。 l..、.

ヴォロネジ州立工科大学

394026 ヴォロネジ、モスコフスキー通り 14

磁気ディスクのディレクトリ

高等数学および物理数学モデリング学科

で。 ゆゆきん

離散数学パート 1. グラフ理論の要素

チュートリアル

で。 ゆゆきん

離散数学パート 1. グラフ理論の要素

チュートリアル

ヴォロネジ 2004

導入

このマニュアルは、次の専門分野を学ぶ VSTU の学生によるコース「離散数学」で使用できます。

090102 – コンピューターのセキュリティ。

090105 – 自動化システムの情報セキュリティの包括的な提供。

090106 - 電気通信システムの情報セキュリティ。

「離散数学」という学問は、国の一般教育基準に沿った知識と技能の習得を保証すると同時に、基礎教育の習得、世界観の形成、論理的思考の発達を促進します。

グラフ理論は、個別のオブジェクトに関連する現代の工学問題を形式化するための効果的なツールです。 集積回路と制御回路の設計、オートマトンと論理回路の研究、システム分析、自動生産制御、コンピュータと情報ネットワークの開発、回路設計と設計トポロジカル設計などに使用されます。

このチュートリアルでは、グラフ理論の基礎、基本的な手法、アルゴリズムについて概説します。 ここでは、n グラフと有向グラフを紹介します。 同型写像。 木; オイラーグラフ; 平面グラフ。 カバーリングと独立したセット。 強力な接続性

V ダイグラフ。 マルコフ連鎖グラフ分析。 グラフ内の最短経路を見つけるアルゴリズム。 ハミルトニアンサイクル探索問題

V グラフ; 巡回セールスマン問題。 グラフとマッピングの列挙。 極端なタスク。 最適化の問題。 普遍的なタスク。 分岐結合メソッド。 また、上記の概念を使用するための実践的なスキルも開発します。

このコースの目的は、自然科学と技術におけるプロセスと現象のモデル化の分野における学生の理論的知識、実践的なスキルと能力を開発することです。

ke、数学記号を使用して、情報セキュリティの分野で高度な専門レベルの公式活動を実行するために必要なオブジェクトの定量的および定性的な関係を表現する能力を備えています。

この目標を達成するには、次のタスクが役立ちます。

可能な限り幅広いグラフ理論の概念を研究する。

教育上および実践上の問題を解決するスキルを習得します。

マスター最適化メソッド。

情報に関する問題の設定と解決、グラフを使用した情報のモデル化と分析のスキルを開発します。

「離散数学」という学問は応用数学学問の一つです。 これは、学生が「代数」と「数学的論理とアルゴリズムの理論」の学問を勉強する間に得た知識に基づいています。 「離散数学」という学問で得た知識やスキルが研究に活かされます。 一般的な専門家そして特殊な分野。

1. グラフ理論の基本概念。

1.1. グラフ理論の問題。

グラフ理論は、関係の概念と同様に、異なるオブジェクト間の接続システムを研究する数学の一分野です。 ただし、グラフを独立して定義すると、理論の表現が簡素化され、より理解しやすく視覚的になります。

グラフ理論の最初の問題は、エンターテイメントの問題やパズルを解くことに関連していました。

最初のタスク。 ケーニヒスベルク橋の問題は 1786 年にオイラーによって提起され、解決されました。 この都市はプレゴリャ川のほとりと 2 つの島に位置していました。 図に示すように、島と島の間は 7 つの橋で結ばれていました。

疑問が生じました。家を出て、それぞれの橋を一度だけ渡って戻ることは可能でしょうか?

2番目のタスク。 3つの家と3つの井戸の問題。 家が３つと井戸が３つあります。

各家から各井戸までは交差しないように道を引く必要があります。 課題は

ポントリャギンによって解決され、彼とは独立してクラトフスキーによって解決されました。

3番目のタスク。 色は4色くらい。 隣接する 2 つのエリアが同じ色で塗られないように、平面上の地図を 4 色で色付けします。

グラフ理論から得られる多くの結果は、科学技術における実際的な問題を解決するために使用されます。 したがって、19 世紀半ば、キルヒホッフはグラフ理論を使用して複雑な電気回路を計算しました。 しかし、数学的学問としてグラフ理論が形成されたのは 20 世紀の 30 年代になってからです。 この場合、グラフは抽象的な数学的オブジェクトと見なされます。 これらは、回路とシステムの分析と合成、ネットワークの計画と管理、オペレーションズリサーチ、プログラミング、生物の生命のモデリングなどの分野で使用されます。

1.2. 基本的な定義。

グラフ G= (V,E) は、空ではない頂点 V のセットと、順序なしおよび順序付きの頂点 E のペアのセットという 2 つのセットのコレクションです。 以下では、有限グラフ、すなわち、 頂点の有限セットとペアの有限ファミリーを持つグラフ。 順序のない頂点のペアはエッジと呼ばれ、順序のあるペアはアークと呼ばれます。

通常、グラフは図で表されます。頂点は点 (または円)、エッジは任意の構成の線です。 さらに、矢印は円弧上の方向を示します。 グラフを描くとき、​​キャリアは

エッジの幾何学的特性 (長さ、曲率) と、平面上の頂点の相対位置が重要です。

どのエッジ(円弧)にも属さない頂点は孤立と呼ばれます。 エッジまたは円弧によって接続された頂点を隣接と呼びます。 エッジ (円弧) とその 2 つの頂点のいずれかを入射と呼びます。

彼らは、エッジ (u,v) が頂点 u と v を接続し、弧 (u,v) が頂点 u で始まり頂点 v で終わると言い、u をこの弧の始点、v を終点と呼びます。

頂点のペアは、2 つ以上のエッジ (同じ方向の円弧) で接続できます。 このようなエッジ (円弧) を多重と呼びます。 円弧 (またはエッジ) は、同じ頂点で開始または終了することができます。 このような円弧（エッジ）をループと呼びます。 ループを含むグラフは擬似グラフと呼ばれます。 複数のエッジ (円弧) を持つグラフをマルチグラフと呼びます。

ループや複数のエッジのないグラフは単純と呼ばれます。 単純なグラフは、頂点のペアにそれらを接続するエッジ (円弧) がある場合に完全であると呼ばれます。 n 個の頂点を持つ完全なグラフは K n で示されます。 たとえば、これらはグラフです

1 つの孤立した頂点 (K 1) から構成されるグラフは自明と呼ばれます。

グラフ G の補数は、グラフ G と同じ頂点を持ち、完全なグラフを得るためにグラフ G に追加する必要があるエッジを含むグラフ G です。

ダイグラファーではないすべての人へ 正規に一致する同じ頂点のセットを持つ有向グラフ。各エッジは、同じ頂点に入射し、反対方向を持つ 2 つの円弧に置き換えられます。

1.3. グラフの頂点の次数。

単純なグラフ G の頂点 v の次数 (価数) (表記 d (v) または deg (v)) は、特定の頂点 v に付随するエッジまたはアークの数です。 擬似グラフの頂点の価数を計算する場合、各ループを 2 回カウントする必要があります。

n グラフのすべての頂点の次数が k に等しい場合、そのグラフは次のように呼ばれます。 レギュラー（均一） k度。 頂点の次数が 0 の場合、その頂点は孤立しています。 頂点の次数が 1 の場合、その頂点は終端頂点 (ぶら下がり、行き止まり) と呼ばれます。

有向グラフの場合、頂点 v から出る弧の数は次のように呼ばれます。

不定 中程度の成果

(v) および入ってくるもの – セミステップ –

新しい電話

(v)、この場合、関係 d (v)=

(v)+

(v)。

オイラーの定理: グラフの頂点の次数の合計は次のようになります。

リブの数を2倍にする、つまり

d(vi)

(v)

ここで、n は頂点の数です。 m – 数値

肋骨（アーチ）。 このステートメントは、頂点の次数の合計を計算するときに、各エッジがエッジの一方の端ともう一方の端で 2 回考慮されるという事実によって証明されます。

1.4. グラフの同型性。

グラフの頂点が何らかの形で互いに異なる場合、そのグラフはラベルが付けられた (または番号が付け直された) と呼ばれます。

ラベル（数字）。 カウントが考慮されます 厳密な意味で完全に与えられた、頂点とエッジの番号付けが固定されている場合。 この場合、頂点と辺のセットが一致する場合、グラフ G 1 と G 2 は等しいと呼ばれます (指定 G 1 = G 2)。 2 つのグラフまたは擬似グラフ G 1 = (V 1 ,E 1 ) および G 2 = (V 2 ,E 2 ) と呼ばれます。

同型（表記G）

それらが存在する場合

1 対 1 マッピング: 1)

：V1V2

: E 1 E 2 は、グラフ内の任意の 2 つの頂点 u、v に対して

関係 ((u, v)) ((u), (v)) は有効です。

2 つの単純なグラフ (ループと複数のエッジなし) G 1

とG2

相互に同一のものがある場合は同型であることが判明する

値のマッピング

：V1V2

だから何？

(u , v ) ((u ), (v )) 。

したがって、頂点と辺の番号付けのみが異なるグラフは同形です。 グラフの同型性は次の特性を持つため、同値関係です。

反射性 -

G1、

そして全単射

は同一の関数です。

対称。

全単射あり

全単射あり

推移性。

G1G2

全単射

1、a

全単射あり

それから G G

全単射あり

2 (1 ) .



読むことをお勧めします