![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Пример 1. ⇐ ПредыдущаяСтр 4 из 4
Маршрут длины kиз вершины v в вершину w – это последовательность вершин (не обязательно различных) Маршрут называется цепью, если все его ребра различны. Маршрут замкнутый Замкнутая цепь называется циклом. Граф называется связным, если каждая пара его вершин может быть соединена маршрутом. Деревом называется связный граф без циклов. Простой маршрут: из каждой его вершины выходит только одно ребро. Полный маршрут – проходит через каждую вершину графа.
Теорема. Пусть А – матрица смежности графа Г. Тогда
В примере 1 , . Определение.Граф Г называется ориентированным (орграфом), если у каждого его ребра задано направление:
переход от вершины жен.
Определение. Граф Г называется нагруженным, если каждому его ребру поставлено в соответствие некоторое число – «длина ребра», или «цена прохода по ребру».
Основные задачи: 1. Нахождение минимальных маршрутов в нагруженном графе. 2. Когда граф может быть помещен на плоскость без пересечения его ребер? Применение: можно ли обойтись без пространственной развязки дорог; конструирование печатных плат в электронике.
|