グラフ理論とは何ですか？グラフはどのように定義されていますか？

1736年、スイスの物理学者で数学者のレオンハルトオイラー（1707-1783）の研究に基づいて、一連の頂点が次のように定義することが観察されました。 ただし、パスがエッジを繰り返さずに異なる頂点で構成されている場合、そのパスはパスまたはパスと呼ばれます。 オイラー; さらに、開始点に到達し、各エッジを1回だけ通過すると、オイラーサイクル（回路）が発生します。

見積もり（APA）

アレクサンダーバラザ | 7月 2022
物理学の学位

その一部として、グラフを順序対として定義します （GOES） どこ v グラフのすべての頂点またはノードの（空でない）セットを指定します。 A グラフの頂点を結ぶすべてのエッジまたは線のセット（空の場合もあります）を指定します。 セットの要素 A 順序付けされていないペア{v、w}として指定できます。ここで、vとwはの要素（ノードまたは頂点）です。 v、このようにして、vとwは隣接する頂点であると言われます（これらはエッジで結合されています）。

グラフ理論は、オイラーが7つの橋を渡る方法を疑問に思った人気のある創意工夫の問題に対する答えから生じています。 ケーニヒスベルクのコミュニティの2つの島（当時はドイツの一部であり、現在はロシアのカリーニングラード）に、2つの島を使わずに本土と合流しました。 同じ橋を回して、それが何であれ出発点（本土にある）に到着し、この場合、最終的には できる。

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

オイラーはケーニヒスベルクをグラフとしてモデル化しました。ここで、各ポイント（頂点またはノード）は橋を表し、各線（エッジ）は陸地のパスを表します。

この問題の解決策は何ですか？

ありません 解決 オイラーが示したように、頂点の次数が均一ではないため、つまり、偶数の線が各点に影響を与えないため、これは課せられた条件を満たします。 _[3]. このように単純に定義された構造では多くのことができるようには思えませんが、 算数、時々物事は彼らが見ているものではありません。 したがって、最も多作で、横断的で、学際的な領域の1つです。 _[4] 人間の知識、グラフ理論の。

オイラーグラフまたはオイラー軌道を使用しますか？

次のグラフはすべてオイラーパスを持っています _[5]. それらはすべてオイラーサイクルを持っていますか？

3番目のグラフを見てみましょう。

頂点に番号を付けましょう：

シーケンス{3,4,6,2,1,3,7,6,5,4,2}で定義されるパスは、オイラーパスであることがわかります。 エッジを繰り返さずにグラフ全体を通過しますが、開始点に到達しないため、オイラーサイクルではありません。 頂点に異なる番号を付けたらどうなるでしょうか。 パスが別の連続で定義されることを除いて、それほど多くはありません。 最初のソリューションで提案されたものとは異なるパスをたどった場合、どうなるでしょうか。 この質問への回答は少し複雑で、ソフトウェアエンジニアが通常喜んでいるアルゴリズムが含まれています。 プログラミング.

ここで公開されているもののより厳密な証拠については、次の結果を参照する必要があります。

"なれ G 連結グラフ _[6]. それならはい G 持っている 回路 オイラー、各頂点の次数は偶数ですが、 G オイラーパスがあり、Gには奇数次の頂点が2つあります _[7] （正確には、パスが開始および終了する頂点）".

次に、実際に、取得したグラフで、頂点3と6のみが奇数の次数を持っていることを確認できます（これは 頂点の番号付けが異なっていたとしても発生します）、したがって、上記のグラフにはパスがあります オイラー _[8]. 残りのグラフについても、同様の方法で進めて、実際にパスがあり、 オイラー閉路、または別の言い方をすれば、鉛筆を手に取って繰り返すことなく、そのようなグラフを描くことができますか？ 行？ この質問に対する答えは、これまでに説明したことから推測できますが、これは演習になります。 細かい運動技能、創意工夫、忍耐力の面で興味深いので、読者に6つ以上のグラフを見つけて描くように勧めます の頂点 軌道 オイラー。

他の種類のグラフはありますか？ グラフ理論は「現実の」世界に応用できますか？

非常に簡単にレビューしたこれらのグラフは、グラフ理論で見られる多くの種類のグラフの1つにすぎません。 また、ツリーなどのグラフを見つけることもできます。これらのグラフは、要素を階層やカウント計算で分類できるセットで非常に代表的です。 確率_[9]、有向グラフ、ハミルトングラフ _[10]、など。

サイコのグラフィックモデルとネットワークの画像、Ruiz、AnaMaría著。

これらの謎は、私たちがそれらをそれと呼びたいのであれば、今日の世界で、次のような多様な状況で非常に適用可能です。 生物学 分子 _[11], コンピューティング_[12]、電気通信 _[13] およびネットワーク分析 _[14]. それなら尋ねる価値があります：少なくとも、ほとんどの問題が 平凡 数学の最も興味深く、目立つ結果の1つになるのでしょうか。 おそらく、このためには、人類の最も輝かしい心の1人の貢献が必要でした。