Компоненты графа. Точки сочленения. Число связности графа

Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа.

Точка сочленения - вершина графа, при удалении которой количество компонент связности возрастает

Подграф G' графа G называется компонентой связности графа G, если все вершины G' составляют класс эквивалентности по отношению связности, а множество рёбер G' это все инцидентные этим

Числом вершинной связности графа наз. наименьшее число вершин, удаление к-рых (вместе с нцидентными им ребрами) приводит к несвязному графу

Билет 13

Аксиома выбора и эквивалентные ей утверждения

Аксиомой выбора называется следующее высказывание теории множеств: «Для каждого семейства непустых непересекающихся множеств существует (по меньшей мере одно) множество d, которое имеет только один общий элемент c c каждым из множеств b данного семейства».

Теорема Цермело

Любое множество можно вполне упорядочить.

Принцип максимума Хаусдорфа

В любом частично упорядоченном множестве существует максимальное линейно упорядоченное подмножество

Лемма Куратовского-Цорна

Частично упорядоченное множество, в котором любая цепь имеет верхную грань, содержит максимальный элемент.