Математическая культура. Мациевский С.В. - 40 стр.

                       § 4. Теория графов
                                 Для чего, в самом деле, полюса, параллели,
                                 Зоны, тропики и зодиаки?
                                 И команда в ответ: «В жизни этого нет,
                                 Это — чисто условные знаки».
                                              Льюис Кэрролл. Охота на Снарка.
                             п. 1. Граф
    1. Граф. Два множества: конечное непустое множество V и множество
X неупорядоченных пар различных элементов из V,— называются графом.
    Вершины графа — элементы множества V, ребра графа — элементы X.
    Две вершины графа смежные, если они соединены ребром.
    Число вершин называется порядком графа. Граф с p = |V| вершинами и
q = |X| ребрами называется (p, q)-графом.
    Два графа изоморфны и не различаются, если существует биекция
множеств их вершин, сохраняющая смежность вершин.
    Примеры.
    1. (4, 5)-граф:
    2. Не граф: фигура с ребром-петлей:
    3. Не граф: фигура с кратными ребрами:
    4. Существует всего 4 разных графа порядка 3.
    Упр. 1. Нарисуйте все 11 графов порядка 4, упорядочив их по количе-
ству имеющихся ребер.
    2. Связный граф. Маршрут —последовательность вершин графа та-
кая, что любые две последовательные вершины смежные, вместе с ребра-
ми, их соединяющими. Цепь — маршрут, у которого все ребра различны.
    Примеры.
    1. Две цепи из трех разных ребер:
    2. Три разные ребра, из которых нельзя образовать цепь:
    Если в цепи и все вершины различны, кроме, быть может, первой и по-
следней, то это простая цепь. Граф называется связным, если любые две
различные его вершины соединены простой цепью.
    Пример. Существуют всего два связных графа порядка 3.
    Упр. 2. Нарисуйте все 6 связных графов порядка 4.
    3. Подграфом данного графа называется граф, состоящий из вершин и
ребер данного графа. ∀ граф разбивается на непересекающиеся связные
подграфы — компоненты — следующим образом. Зададим отношение
эквивалентности на множестве вершин графа: две вершины эквивалент-
ны, или связаны, если ∃ простая цепь, их соединяющая. Тогда множество
вершин графа распадается на связные классы эквивалентности.
    Очевидно, что связный граф состоит из одной компоненты. Граф не-
связен, если число его компонент больше 1.
    Пример. Единственный 2-компонентный граф порядка 3.
    Упр. 3. Нарисуйте все три 2-компонентных графа порядка 4.

                                  39