Е. А. Перминов методическая система обучения дискретной математике в аспекте интеграции образования монография

Маршрут в графе G определяется как последовательность ребер 

(v1, v2), (v2, v3), (v3, v4),…, (vn – 1, vn) с началом v1 и концом vn. Этот 

маршрут соединяет вершины v1 и vn. 

Приводятся примеры маршрутов и примеры последовательно- 

стей ребер, не являющихся маршрутами. Начать можно с примера 

графа Г (рис. 4.1), в котором последовательность ребер (a, v), (v, c), 

(c, d) является маршрутом, соединяющим вершины a и d. 

Далее нужно отметить, что в маршруте каждые два соседних, 

записанных рядом ребра имеют общую вершину. Но не любая такая 

последовательность ребер графа является маршрутом. Приводится 

пример последовательности ребер, не являющейся маршрутом. 

Один из возможных примеров – последовательность ребер (a, v), 

(b, v), (c, v), (v, d) графа Г, в которой каждые два соседних ребра име- 

ют общую вершину. Однако эта последовательность ребер не являет- 

ся маршрутом, соединяющим вершины a и d. Действительно, по оп- 

ределению маршрута общая вершина v двух соседних ребер (a, v), 

(b, v) должна быть записана следующим образом: (a, v), (v, b). 

a
b

v

d
c

Граф Г 

Граф G 

Рис. 4.1 
Рис. 4.2 

213 

Объяснение определения связного графа можно предложить на- 

чать со следующего примера. 

Пусть вершины графа обозначены числами 1, 2, 3, 4, 6, 12. Две 

вершины n и m образуют ребро (n, m) тогда и только тогда, когда одно 

из чисел n, m делится нацело на другое. Очевидно, в графе имеется 

12 ребер: (1, 1), (2, 1), (3, 1), (4, 1), (6, 1), (12, 1), (4, 2), (6, 2), (6, 3), 

(12, 3), (12, 4), (12, 6) (рис. 4.2). 

Далее даются определения понятий цепи и связанных вершин. 

Маршрут (1, 2), (2, 4), (4, 12) является цепью, т. е. маршрутом, 

в котором все ребра различны. Всего в графе имеется восемь цепей, 

соединяющих вершины 1 и 12. Две вершины a и b графа называются 

связанными, если существует цепь, соединяющая вершины a и b. 

Определение. Граф называется связным, если любые две его вер- 

шины связанные. 

Граф на рис. 4.2 связный, поскольку есть цепь, соединяющая лю- 

бые две вершины из множества {a, b, c, d, v}. Граф на рис. 4.3 несвяз- 

ный, поскольку нет цепи, соединяющей вершины a, p. 

Рис. 4.3 

Доказательство признака связного графа предваряет задача. 

Задача. В стране Океании 11 островов. Каждый из островов со- 

единен мостами не менее чем с пятью другими. Требуется доказать, 

что с любого острова можно добраться пешком через мосты до любо- 

го другого. 

Доказательство начинается с предположения, что найдутся два 

таких острова, которые не связаны пешеходным маршрутом, прохо- 

дящим через мосты. Предлагается изобразить эти два острова точка- 

ми A и B, а линиями – мосты, соединяющие эти острова с другими. Каж- 

дый из этих островов связывают с другими островами не менее пяти 

214 

мостов, что и показано на рис. 4.4. Поэтому в Океании есть не менее 

12 островов. Отсюда легко обнаруживается противоречие условию. 

Объясняется, что граф, вершинам которого соответствуют острова, 

а ребрам – мосты, является связным. Иными словами, граф островов 

и мостов Океании связен, т. е. для любых двух его вершин существует 

цепь, их соединяющая. 

A


B

Рис. 4.4 

После решения этой задачи даже слабым студентам будет легко 

понять, как аналогично доказывается следующая теорема. 

Теорема (признак связного графа). Граф с n вершинами связен, 

если степень каждой его вершины не менее 

− 
. 

Для облегчения восприятия доказательства студентам после 

аналогичного предположения о том, что существуют две такие вер- 

шины A и B, для которых нет цепи, их соединяющей, следует предло- 

жить обозначить степени вершины A и вершины B через 


m = 

− 
. По

определению степени вершины из вершины A, как и из вершины B, 

выходит не менее m ребер (где m записано уже не в виде дроби). 

Для доказательства других теорем используется тот же методи- 

ческий прием (сюжетный фактор). 

Дерево определяется как граф, в котором любые две вершины 

соединены ровно одной цепью, состоящей из различных вершин. 

Слабым студентам можно предложить изучение важнейшего 

понятия изоморфных графов на основе методической редукции этого 

понятия, изложенной в подп. 3.2.3.2. 

215