Элементы теории графов и их технические приложения - 16 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

16
Утверждение 1. При u ≠ v всякий (u, v)-маршрут содержит простую (u, v)-цепь.
Утверждение 2
. Всякий цикл содержит простой цикл.
Справедливы также:
Утверждение 3
. Объединение двух несовпадающих простых (u, v)-цепей
содержит простой цикл.
Утверждение 4
. Если С и Д – два несовпадающих простых цикла, имеющих
общее ребро е, то граф (С
∪Д) – е также содержит простой цикл.
Для связанный графов очевидно следующее.
Утверждение 5
. Для связности графа необходимо и достаточно, чтобы в нем
для какой-либо фиксированной вершины u и каждой другой вершины v существовал
(u, v)-маршрут.
Всякий максимальный связный подграф графа G называется
связной
компонентой
(или просто компонентой) графа G. В этом понятии слово
максимальный означает максимальный относительно включения, т.е. не
содержащийся в связном подграфе с большим числом элементов. Множество
вершин связной компоненты называется
областью связности графа.
Справедливо утверждение: каждый граф представляется в виде дизъюнктного
объединения своих связных компонент. Разложение графа на связные компоненты
определено однозначно.
Некоторые проблемы (например, проблема изоморфизма) сводятся к случаю
связных графов с помощью
Утверждение 6
. Для любого графа либо он сам, либо его дополнение является
связным.
Полезно также:
Утверждение 7
. Пусть G – связный граф, е
∈
ЕG. Тогда:
1) если ребро е принадлежит какому-либо циклу графа G, то граф G-е связен;
2) если ребро е не входит ни в какой цикл, то граф G-е имеет ровно две
компоненты.
Обозначим через m(G) число ребер графа G, а К(G) – число его компонент.
Возникает вопрос: сколько ребер может быть в графе порядка
n с фиксированным
числом К компонент. Ответ дает следующая теорема.
Теорема
.Если К(G)=к для n-вершинного графа G, то n-k
≤
m(G) ≤(n-k)(n-k+1)/2,
причем обе эти оценки для m(G) достижимы.
4. Характеристики графов.
Рассмотрим некоторые важнейшие характеристики графов, полезные для их
приложений, так как решение многих технических задач методами теории графов
сводится к определению тех или иных характеристик графов.
Циклическое число. Пусть G – неориентированный граф, имеющий n
вершин, m ребер и r компонент связности. Циклическим числом графа G называют
число
ν =m-n+r
Физический смысл этого числа заключается в том, что оно равно
наибольшему числу независимых циклов в графе. При расчете электрических цепей
цикломатическое число используется для определения числа независимых контуров.

Страницы