Пример 1.

2

1

Маршрут длины kиз вершины v в вершину w – это последовательность вершин (не обязательно различных) , , , …, таких, что , , …, - ребра графа.

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

Маршрут замкнутый v=w.

Замкнутая цепь называется циклом.

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

Деревом называется связный граф без циклов.

Простой маршрут: из каждой его вершины выходит только одно ребро.

Полный маршрут – проходит через каждую вершину графа.

Теорема. Пусть А – матрица смежности графа Г. Тогда = число маршрутов длины k от вершины к вершине .

В примере 1

, .

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

переход от вершины к вершине возможен,

переход от вершины к вершине невозмо-

жен.

Пример – дорога с односторонним движением.

Определение. Граф Г называется нагруженным, если каждому его ребру поставлено в соответствие некоторое число – «длина ребра», или «цена прохода по ребру».

Основные задачи:

1. Нахождение минимальных маршрутов в нагруженном графе.

2. Когда граф может быть помещен на плоскость без пересечения его ребер? Применение: можно ли обойтись без пространственной развязки дорог; конструирование печатных плат в электронике.