Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Пример 1.




2

1

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

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

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

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

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

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

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

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

 

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

 

В примере 1

, .

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

 

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

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

жен.

 

 

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

 

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

 

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

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

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

 


Поделиться:

Дата добавления: 2015-07-26; просмотров: 53; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты