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

Last updated
Save as PDF

Page ID: 66115

$ \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}}$

$clipboard_e032b8010d0c6f99465d364eb5603f9df.png$

$clipboard_ea2d27e6c4265d2350161e21174a3ad82.png$

7. Перший і третій графи пов'язані між собою.

9. Берн до Франкфурта до Мюнхена до Берліна: 12 годин 50 хв. (Хоча поїздка через Ліон, Париж та Амстердам додає лише 30 хвилин)

11. Перший графік має схему Ейлера. Останні два графіки мають дві вершини з непарним ступенем.

13. Одна з декількох можливих евлерізацій, що вимагають 5 дублікатів:

$clipboard_eaf5da7be9319b846ed672db1b9d49043.png$

17. Тільки середній графік має гамільтонівський контур.

19.

Форт-Уорт, Арлінгтон, Мескіт, Плано, Дентон, Фут Уорт: 183 милі
Те саме, що і частина a
Те саме, що і частина a

21.

АБДЕЧА
АЦЕБДА
ADBCEA

23.

$clipboard_edbeba508cc3b2c66ec8f63a87530f2b4.png$

25.

$clipboard_e7e0355653e2ab74bdb23ef82356422b0.png$