дерева дискретная математика

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

Е – е4 – С – е5 – Е;

А – е1 – В – е3 – С – е4 – Е – е2 – А;

М3: А – е1 – B – е3 – C – е5 – Е – е4 – С (цепь, но не путь).

М2: А – е2 – Е – е6 – Д – е7 – Д – е6 – Е – е5 – С (не цепь);

М1: А – е1 – В – е3 – С (путь);

Можно составить следующие маршруты из А в С в графе G:

Цикл – это цепь, у которой совпадают начальная и конечная вершины, а все остальные различны.

Путь – это цепь, все вершины которой (за исключением, быть может, начальной и конечной) различны.

Цепь – это маршрут без повторяющихся ребер.

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

Прежде всего, уточним термины "маршрут", "цепь", "цикл" и "путь". Эти четыре понятия находятся в следующем соотношении: пути и циклы – это особые виды цепей, цепь – особый вид маршрута.

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

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

Последние добавленные новости

Навигация по предметам

Поиск в библиотеке

У нас Вы найдете много книг, лабораторных, курсовиков, учебных пособий, лекций, готовых шпор и много другого добра..

Самая домашняя библиотека - SDB.SU - это бесплатная электронная библиотека для программиста

Страница 5. Глава - Элементы теории графов - Рабочий учебник по дискретной математике » Самая домашняя библиотека - книги, лабораторные, курсовики, учебные пособия, лекции, исходники, шпоры - все для программиста и не только..