§12.1 Элементы теории графов

Опр Графом называется пара , состоящая из конечного множества точек (вершины (vertex) графа) и подмноже ства упорядоченных пар вершин (дуги графа) или неупорядочен ных пар вершин (ребра (edge) графа).

◄ В соответствии с условием искомый закон удовлетворяет дифференциальному уравнению с начальным условием .

Решение однородного уравнения с этим условием имеет вид .

Для нахождения частного решения исходного уравнения с нулевыми начальными условиями используем обобщенное преобразование Лапласа. Учитывая , имеем

.

Тогда обратное преобразование дает частное решение

.

Поэтому искомое колебание материальной точки осуществляется по закону

.

Дифференцированием нетрудно убедиться, что в момент времени скорость материальной точки скачком изменяется на величину .►

§12.1 Элементы теории графов

Опр Графом называется пара , состоящая из конечного множества точек (вершины (vertex) графа) и подмноже ства упорядоченных пар вершин (дуги графа) или неупорядочен ных пар вершин (ребра (edge) графа).

ЗАМЕЧАНИЕ Ребро, соединяющее вершины , будем обозначать , а дугу, соединяющую эти вершины, .

Опр Граф называется орграфом (ориентированным графом), если состоит только из дуг и неориентированным, если состоит только из ребер.

Пример 1 Изображенный на рисунке граф имеет такие множества вершин и ребер: .

Пример 2 Орграф , .

Опр Графом называется пара , состоящая из конечного множества точек (вершины (vertex) графа) и подмноже ства упорядоченных пар вершин (дуги графа) или неупорядочен ных пар вершин (ребра (edge) графа).

ЗАМЕЧАНИЕ Ребро, соединяющее вершины , будем обозначать , а дугу, соединяющую эти вершины, .

Опр Граф называется орграфом (ориентированным графом), если состоит только из дуг и неориентированным, если состоит только из ребер.

Пример 1 Изображенный на рисунке граф имеет такие множества вершин и ребер: .

Опр Ребро (дуга) с началом и концом в одной и той же вершине, называется петлёй.

Опр Два ребра с общим началом и общим концом или две дуги с

Опр Ребро (дуга) с началом и концом в одной и той же вершине, называется петлёй.

Опр Два ребра с общим началом и общим концом или две дуги с общим началом и общим концом называются кратными.

Опр Вершины с общим ребром (дугой), а так же рёбра (дуги), имеющие общую вершину, называются смежными.

Определение Если есть вершина ребра , то и называются инцидентными.

Определение Матрицей инцидентности орграфа называет ся матрица размера , у которой .

Пример Построим по орграфу матрицу инцидентности

	0	-1	1	-1
	1	0	-1	1
	-1	1	0	0

Рис12.4

Опр Орграфы называются изоморфными, если существуют биекции , которые сохраняют ориентацию:

.

ЗАМЕЧАНИЕ Если графы изоморфны, то и .

Пример Следующие орграфы не изоморфны.

Рис.12.5

Опр Последовательность ребер графа (дуг орграфа

) называется маршрутом длины (путем длины ). Маршрут (путь) называется замкнутым, если .

Опр Композицией маршрутов , называется маршрут .

Аналогично определяется композиция путей.

Опр Маршрут называется обратным к маршруту .

Опр Незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется цепью. Цепь называется простой, если в ней все вершины попарно различны.

Определение Замкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется циклом (контуром). Цикл (контур) называется простым, если все его вершины попарно различны.

Пример В орграфе

Рис12.8

замкнутый путь содержит простой контур .

ЗАМЕЧАНИЕ Во всяком замкнутом маршруте (замкнутом пути) можно выделить простой цикл (простой контур).

Опр Подграфом графа называется граф , со свойством .

Контрпример В предыдущем орграфе пара не является подграфом.

_____

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

Обозначение - число компонент связности графа .

Опр Цикломатическим числом графа называется величина .

Опр Число рёбер инцидентных вершине , называется степенью вершины. Если , то называется изолированной. Если , то называется висячей (концевой)

ЗАМЕЧАНИЕ 1) Для связного графа (доказательство проводится индукцией по числу вершин). 2) . Действительно, пусть , есть связные компоненты графа . Для каждой из них необходимо

.

3) Изолированная вершина является компонентой связности. 4) Все вершины замкнутой цепи (с более чем одной вершиной), не являются висячими, то есть .

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

Определение Деревом называется связный граф, не имеющий циклов.

ТЕОРЕМА 12.1 (свойства дерева) 1) Дерево необходимо имеет висячую вершину.

2) Следующие утверждения равносильны:

а) - дерево; б) - связный граф и , то есть ;

в) любые две вершины графа можно соединить единственной простой цепью.

3) Дерево не содержит циклов, но соединяя какие-либо его вершины ребром, получаем граф, в котором ровно один простой цикл и этот цикл содержит добавленное ребро.

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

ЗАМЕЧАНИЕ Так как у остовного дерева связного графа должно быть ребер, то оно не должно содержать ребер графа .

АЛГОРИТМ построения остовного дерева.

Шаг 1. Выберем в любую вершину , и объявим её первым

подграфом искомого остовного дерева . . -

дерево. .

Шаг 2. Если для подграфа , то есть искомое

остовное дерево. Если , то переходим к шагу 3.

Шаг 3. Выберем из вершину , смежную с какой-

либо вершиной . Это возможно в силу связности .

Образуем дерево , добавив к вершину и ребро .

Переходим к шагу 2, положив .

Пример Рассмотрим граф на рис.12.10.

. Выберем, например, . Так как , то процесс построения продолжаем.

.

Остовное дерево построено. Оно не содержит ребра графа.