4: Теорія графів

Last updated

Oct 27, 2022
Save as PDF
- 3.S: Символічна логіка та докази (резюме)
- 4.0: Прелюдія до теорії графів

$\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.E: Теорія графів (Вправи)
4.S: Теорія графів (резюме)
Сподіваємось, ця глава дала вам певний сенс для широкого спектру тем теорії графів, а також чому ці дослідження цікаві. Є ще багато цікавих областей, які слід розглянути, і список постійно збільшується; теорія графів є активною сферою математичних досліджень.