Rambler's Top100


Дискретная математика. Часть 3 (Курс лекций). Авторы: Емцева Е.Д., Солодухин К.С., редактор: в авторской редакции

Определение 13 (подразбиение ребер)

Пусть - ребро графа . Удалим ребро  и добавим два новых ребра  и , где  – новая вершина. Произведенная операция называется подразбиением ребра .

Пример

Граф H получился из графа G подразбиением ребра (u, v).

§6. Цепи. Циклы. Связные графы.
Определение 1

Последовательность вершин и ребер графа вида  называется маршрутом, соединяющим вершины  и .

Замечание

Очевидно, что маршрут можно однозначно задать последовательностью только вершин:

или только ребер: .

Определение 2

a)      Маршрут называется цепью, если все его ребра различны.

b)       Маршрут называется простой цепью, если все его вершины, кроме, возможно, крайних, различны. Обозначают:  – простая цепь длины n.

Определение 3

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

b)       Простая цепь, у которой совпадают первая и последняя вершины, называется простым циклом. Обозначают:  – простой цикл длины n.

Пример

 

1,2,3,4,1,3 – цепь, не являющаяся простой.

1,2,3,4,6 – простая цепь.

2,3,5,6,4,3,1,2 – цикл, не являющийся простым.

3,5,6,4,3 – простой цикл.

 

Определение 4

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

Пример

Определение 5

Всякий максимальный по включению (т.е. не содержащийся в связном подграфе с большим числом элементов) связный подграф графа  называется связной компонентой (или просто компонентой) графа .

 

Теорема 6

 

Для любого графа либо он сам, либо его дополнение – связный граф.

Доказательство

 

Возьмем произвольный граф . Если он связный, то теорема очевидна. Пусть граф  – несвязный. Покажем, что дополнение графа  будет связным графом, то есть любые две его вершины  и  соединены маршрутом.

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

Если вершины  и  принадлежат одной и той же компоненте связности, то в дополнении к графу  они будут соединены маршрутом , где  – произвольная вершина любой другой компоненты связности.

 

Теорема 7

 

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

 

Доказательство

Необходимость. Пусть связный граф остался связным после удаления ребра . Докажем, что принадлежит циклу. Так как граф остался связным, то существует маршрут из  в . Вернув ребро  , получим цикл.

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

Граф остался связным.

 

Теорема 8

 

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

 

Доказательство

 

Рассмотрим любое ребро связного графа .

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

Если ребро  – единственный маршрут, соединяющий  и , то после его удаления граф становится не связным, он разбивается на два подграфа :

Очевидно,  – связные графы.

 

Теорема 9

 

В связном -вершинном графе число ребер не меньше .

 

Доказательство

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

1)       Базис индукции: при теорема верна.

2)       Допустим теорема верна при .

3)       Докажем, что при  , где  – количество

вершин и количество ребер в связном графе G соответственно.

Будем удалять ребра графа G, пока он не распадется на две компоненты , где - граф, – граф. Пусть процесс закончится на - том шаге (-конечное число, так как граф конечный). По индуктивному предположению для  каждой компоненты теорема справедлива, т. е. .

Тогда , т.е. .

 

 

Poker razz odds calculator