рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Маршруты в орграфе

Маршруты в орграфе - раздел Транспорт, Лекция № 12. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ Задачи, Связанные С Маршрутами В Орграфе, Имеют Большое Практическое Значение...

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

Пример 13.1. Дан орграф (рис. 13.1). Сколько в нем маршрутов длиной 3?

Рис. 13.1

 

Решение. Используем алгебраический метод решения задачи на основании теоремы 12.4. Запишем матрицу смежности. Матрица смежности орграфа – несимметричная.

, .

Возведем эту матрицу в степень 3. Суммируя все элементы полученной матрицы, находим, что число маршрутов длиной 3 равно восьми. Три единицы, стоящие по диагонали, показывают, что сюда входит 3 помеченных контура. Очевидно, что это контуры: 1–4–3, 4–3–1, 3–1–4.

 

– Конец работы –

Эта тема принадлежит разделу:

Лекция № 12. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ

Основные определения Каждое ребро e из E инцидентно ровно двум вершинам и... Циклы... Маршрут в котором начало и конец совпадают циклический Циклический маршрут называется циклом если он цепь...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Основные определения
Граф – это совокупность двух множеств: вершин

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

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

Реберный граф
Рассмотрим два графа G и L(G). Граф G имеет произвольную форму, а вершины графа L(G) расположены на ребрах графа G. В этом случае граф L(G) называется

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

Ранг-полином графа
Ранг графа определяется как , где n – число вершин, k – число компонент связности графа. Ко

Основные определения
Ребро в графе G может быть ориентированным и иметь начало и конец. Такое ребро называется

Транзитивное замыкание
Прямым (декартовым) произведением множеств A и B называется множество

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

Основные определения
Дерево – связный граф без циклов. Лес (или ациклический граф) – неограф без циклов. Компонентами леса являются деревья.

Центроид дерева
Ветвь к вершине v дерева – это максимальный подграф, содержащий v в качестве висячей вершины. Вес

Десятичная кодировка
Деревья представляют собой важный вид графов. С помощью деревьев описываются базы данных, деревья моделируют алгоритмы и программы, их используют в электротехнике, химии. Одной из актуальных задач

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги