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

Граф – это математическое понятие, которое служит для моделирования связей между объектами. Различают ориентированные и неориентированные графы. Точные определе- ния даны ниже.

Основные понятия

(Неориентированным) графом называется пара конечных множеств (V, E), где V – произ- вольное множество объектов, называемых вершинами, и E ⊆ {{i, j}|i, j ∈ V } – множество неупорядоченных пар вершин, где {i, j} ∈ E называется ребром.

Ориентированным графом (орграфом) называется пара конечных множеств (V, A), где V

– множество вершин, и A ⊆ { (i, j) |i, j ∈ V } – множество упорядоченных пар вершин, где (i, j) ∈ A называется дугой.

Мультиграфом (ориентированным мультиграфом) называется граф с кратными ребрами

(кратными дугами).

Примеры: рисунки графов с 3 вершинами.

Определения. Вершина i является начальной, а вершина j – конечной вершиной дуги (i, j). При этом i и j – смежные вершины, а дуга (i, j) инцидентна вершинам i и j. Та- кая же терминология используется для неориентированных графов – смежные вершины и инцидентные ребра. Дуга (i, j) выходит из i и входит в j. Если (i, j) – дуга, то i назы- вается непосредственным предшественником j, а j – непосредственным последователем i. Количество дуг, входящих в вершину i называется степенью захода этой вершины, а количество дуг, выходящих из вершины i называется степенью исхода этой вершины. В

неориентированном графе вершины i и j называются концами ребра {i, j}. Количество

ребер, инцидентных вершине i, называется степенью вершины i.

Маршрутом в неориентированном графе G = (V, E) называется такая последователь- ность вершин W = (v 0, v 1 ,..., vk), k ≥ 0, что {vi− 1, vi} ∈ E, i = 1 ,..., k. Граф называется

связным, если существует маршрут, связывающий любые его две вершины. Говорят, что маршрут W связывает вершины v 0 и vk, а вершины v 1 ,..., vk− 1 являются внутренними

вершинами этого маршрута. Количество вершин маршрута называется его длиной. Марш-

рут W называется замкнутым, если k > 0 и vk = v 0. Маршрут называется цепью, если в нем нет повторяющихся вершин. Замкнутый маршрут, в котором никакие вершины, кроме первой и последней, не повторяются, называется циклом.

Аналогами приведенных выше определений для орграфов являются следующие.

Граф	Маршрут	Цепь	Цикл
Орграф	Путь	Простой путь	Цикл

Цикл, который включает все вершины графа, называется гамильтоновым. Граф, который содержит гамильтонов цикл, называется гамильтоновым.

Замкнутый маршрут, который включает каждое ребро графа ровно один раз, называется эйлеровым маршрутом, а граф, который содержит такой маршрут, называется эйлеровым графом. Задачу, является ли граф эйлеровым, впервые поставил и решил Эйлер. В 1736 г. он писал: ”В городе Кенигсберге есть два острова, которые соединяются между собой и

с берегами реки семью мостами (см. Pис. 3).

❦b

✟✟✟

✟✟✟

❦a ❦c

❍❍❍

d

❍❍❍

❦

Рис. 3: Граф "Кенигсбергские мосты". a и c - острова, b и d - берега.

Можно ли спланировать прогулку так, чтобы, начиная с одного из 4 участков суши a, b, c, d,

пройти по каждому из этих мостов один раз и вернуться в начальный пункт?

Теорема 3 (Эйлер, 1736 г) Связный мультиграф является эйлеровым тогда и только тогда, когда все его вершины имеют четную степень.

Дата добавления: 2015-07-08