15: Планарні графіки
- Page ID
- 64749
\( \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}}\)
- 15.1: Планарні графіки
- Візуально завжди існує ризик плутанини, коли графік малюється таким чином, що деякі його краї перетинаються один над одним. Також у фізичних реалізаціях мережі така конфігурація може призвести до зайвих витрат (подумайте про будівництво естакади в порівнянні з будівництвом перехрестя). Тому корисно мати можливість з'ясувати, чи можна намалювати певний графік таким чином, щоб жодні ребра не перетиналися.
- 15.2: Формула Ейлера
- Ейлер придумав формулу, яка відповідає дійсності для будь-якого планарного вбудовування зв'язаного графа. Якщо ви спробуєте довести формулу Ейлера шляхом індукції на кількість вершин, видалення вершини може відключити граф, що означатиме, що індукційна гіпотеза не застосовується до отриманого графіка. Однак існує інша операція графа, яка зменшує кількість вершин на 1 і тримає графік зв'язним. Ця операція називається скороченням краю.
- 15.3: Карта розмальовки
- Припустимо, у нас є карта острова, який був розділений на держави. Традиційно виробники карт забарвлюють різні штати таким чином, щоб гарантувати, що якщо дві держави мають межу, вони не пофарбовані однаковим кольором. Питання в тому, не знаючи заздалегідь, як виглядатиме карта, чи існує прив'язка до того, скільки кольорів буде потрібно, щоб її розфарбувати? Якщо так, то що це пов'язано? Іншими словами, яка найбільша кількість кольорів може знадобитися для фарбування якоїсь карти?
- 15.4: Резюме
- Ця сторінка містить короткий зміст тем, охоплених у розділі 15.