Skip to main content
LibreTexts - Ukrayinska

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

  • Page ID
    65827
  • \( \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}}\)

    Теорія графів стосується проблем маршрутизації та мережі, і якщо можна знайти «найкращий» маршрут, незалежно від того, чи означає це найменш дорогий, найменший проміжок часу або найменшу відстань. Деякі приклади проблем маршрутизації - маршрути, охоплені поштовими працівниками, водіями ДБЖ, поліцейськими, працівниками сміття, зчитувачами лічильників води, учасниками перепису населення, екскурсійними автобусами тощо Деякі приклади мережевих проблем - телефонні мережі, залізничні системи, канали, дороги, трубопроводи та комп'ютерні чіпи.

    • 6.1: Теорія графів
      Деякі визначення важливо зрозуміти, перш ніж заглиблюватися в теорію графів: (1) Граф - це зображення точок, які називаються вершинами і лініями, які називаються ребрами. (2) Ребро, яке починається і закінчується на одній вершині, називається циклом. (3) Якщо є дві або більше ребер, які безпосередньо з'єднують однакові дві вершини, то ці ребра називаються кратними ребрами. (4) Якщо є спосіб дістатися від однієї вершини графа до всіх інших вершин графа, то граф з'єднується, інакше він відключений.
    • 6.2: Мережі
      Мережа - це з'єднання вершин через ребра. Інтернет є прикладом мережі з комп'ютерами як вершини і зв'язки між цими комп'ютерами як ребра.
    • 6.3: Схеми Ейлера
      Леонхард Ейлер вперше обговорив і використовував шляхи та схеми Ейлера в 1736 році. Замість того, щоб знайти мінімальне остовне дерево, яке відвідує кожну вершину графа, шлях Ейлера або ланцюг можна використовувати, щоб знайти спосіб відвідати кожне ребро графіка один раз і лише один раз. Це буде корисно для перевірки паркувальних лічильників вздовж вулиць міста, патрулювання вулиць міста або доставки пошти.
    • 6.4: Гамільтонові схеми
      Завдання комівояжера (TSP) - це будь-яка проблема, коли ви повинні відвідати кожну вершину зваженого графа один раз і лише один раз, а потім повернутися до початкової вершини. Прикладами ситуацій TSP є поставки пакетів, виготовлення друкованих плат, планування робочих місць на машині та виконання доручень по місту.
    • 6.5: Вправи

    Мініатюра: Графік Кенігсберга (CC BY-SA 3.0; Booyabazooka через Вікіпедію)