18.6: Graph Theory

Last updated
Save as PDF

Page ID: 34294

$ \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. The first and the third graphs are connected

9. Bern to Frankfurt to Munchen to Berlin: 12hrs 50 min. (Though trip through Lyon, Paris and Amsterdam only adds 30 minutes)

11. The first graph has an Euler circuit. The last two graphs each have two vertices with odd degree.

13. One of several possible eulerizations requiring 5 duplications:

$clipboard_eaf5da7be9319b846ed672db1b9d49043.png$

17. Only the middle graph has a Hamiltonian circuit.

19.

Ft Worth, Arlington, Mesquite, Plano, Denton, Ft Worth: 183 miles
Same as part a
Same as part a

21.

ABDCEA
ACEBDA
ADBCEA

23.

$clipboard_edbeba508cc3b2c66ec8f63a87530f2b4.png$

25.

$clipboard_e7e0355653e2ab74bdb23ef82356422b0.png$