4: Теорія графів
- Page ID
- 64452
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Теорія графів - відносно нова область математики, вперше вивчена надвідомим математиком Леонардом Ейлером в 1735 році. З тих пір вона розцвіла до потужного інструменту, який використовується майже в кожній галузі науки і в даний час є активною областю математичних досліджень.
- 4.0: Прелюдія до теорії графів
- Картинки, такі як крапковий і лінійний малюнок, називаються графіками. Графіки складаються з колекції точок, які називаються вершинами та лініями, що з'єднують ці точки, звані ребрами. Коли дві вершини з'єднані ребром, ми говоримо, що вони суміжні.
- 4.1: Визначення
- Те, як ми уникаємо неясностей у математиці, полягає в тому, щоб надати конкретні та суворі визначення. Створення хороших визначень непросто, але це неймовірно важливо. Визначення є узгодженою відправною точкою, з якої виходять всі істини в математиці. Чи існує графік без ребер? Ми повинні подивитися на визначення, щоб побачити, чи це можливо. Ми хочемо, щоб наше визначення було точним і однозначним, але воно також повинно погоджуватися з нашою інтуїцією щодо предметів, які ми вивчаємо.
- 4.2: Планарні графіки
- Коли можна намалювати графік так, щоб жодна з країв не перетиналася? Якщо це можливо, ми говоримо, що графік плоский (так як ви можете намалювати його на площині). Зверніть увагу, що визначення плоского включає в себе словосполучення «можна». Це означає, що навіть якщо графік не виглядає так, як він плоский, він все одно може бути.
- 4.3: Забарвлення
- Враховуючи будь-яку карту країн, штатів, округів тощо, скільки кольорів потрібно для фарбування кожного регіону на карті, щоб сусідні регіони були пофарбовані по-різному? Як це пов'язано з теорією графів? Ну, якщо ми розмістимо вершину в центрі кожного регіону (скажімо, в столиці кожної держави), а потім з'єднаємо дві вершини, якщо їх стани поділяють межу, ми отримаємо граф.
- 4.4: Шляхи та схеми Ейлера
- Шляхом Ейлера, у графіку або мультиграфі, є прогулянкою по графіку, який використовує кожне ребро рівно один раз. Схема Ейлера - це шлях Ейлера, який починається і зупиняється на одній вершині. Наша мета - знайти швидкий спосіб перевірити, чи має графік (або мультиграф) шлях або схему Ейлера.
- 4.5: Відповідність у двосторонніх графіках
- Враховуючи двочастковий граф, відповідність є підмножиною ребер, для якої кожна вершина належить рівно одному з ребер. Наша мета в цій діяльності полягає в тому, щоб виявити певний критерій того, коли двосторонній граф має відповідність.
- 4.S: Теорія графів (резюме)
- Сподіваємось, ця глава дала вам певний сенс для широкого спектру тем теорії графів, а також чому ці дослідження цікаві. Є ще багато цікавих областей, які слід розглянути, і список постійно збільшується; теорія графів є активною сферою математичних досліджень.