Основы теории графов и связность

Основы теории графов вводят понятия графов, их базовых параметров, а также понятия связности и обхода, которые описывают, как граф держится вместе.

Definition

Граф состоит из множества вершин и множества рёбер, соединяющих пары вершин; связность измеряет степень, в которой граф остаётся единым целым при удалении вершин или рёбер.

Scope

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

Core questions

• Каковы основные параметры графа — порядок, размер и степень?
• Когда граф является связным и насколько устойчива его связность к удалению элементов?
• Когда граф допускает замкнутый маршрут, проходящий по каждому ребру ровно один раз?
• Как пути и циклы кодируют достижимость и структуру?

Key concepts

• Вершины, рёбра и степень
• Маршруты, пути и циклы
• Компоненты связности
• Вершинная и рёберная связность
• Эйлеровы циклы
• Гамильтоновы циклы

Key theories

Лемма о рукопожатиях

В любом графе сумма степеней всех вершин равна удвоенному числу рёбер, что немедленно подразумевает, что число вершин нечётной степени является чётным.

Теорема Эйлера об эйлеровых циклах

Связный граф имеет замкнутый маршрут, проходящий по каждому ребру ровно один раз, тогда и только тогда, когда каждая вершина имеет чётную степень; этот результат лежит в основе решения Эйлера задачи о Кёнигсбергских мостах.

Clinical relevance

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

History

Работа Эйлера 1736 года о Кёнигсбергских мостах ввела понятие обхода графа; теорема Менгера 1927 года дала фундаментальную двойственность между связностью и непересекающимися путями, которая лежит в основе современной теории.

Key figures

• Leonhard Euler
• Karl Menger

Seminal works

• diestel2017

Frequently asked questions

В чём разница между эйлеровым и гамильтоновым циклом?

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

Что значит, что граф является k-связным?

Граф является k-связным, если он остаётся связным при удалении менее k вершин, что количественно определяет его устойчивость к отказам вершин.