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

Раздел Транспорт
/
Основные определения

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

Выберите учебное заведение

Основные определения

Основные определения - раздел Транспорт, Лекция № 12. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ Ребро ...

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

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

Основание орграфа – неограф с теми же вершинами, но ребрами вместо соответствующих дуг.

Маршрут в орграфе – последовательность вершин, соединенных дугами, направленными в одну сторону.

Маршрут, в котором все дуги разные, есть путь.

Путь, в котором начало и конец совпадают, есть контур. Длина пути измеряется числом входящих в него дуг, а для взвешенного орграфа – это сумма весов дуг.

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

, (13.1)

где суммирование производится по всем вершинам графа.

Множество вершин v, образующих дугу [v, u] с вершиной u, называется множеством предшественников вершины u, а множество вершин u, образующих дугу [v, u] с вершиной v, называется множеством преемников вершины v. Мощности этих множеств соответственно равны: , .

В дальнейшем под графом будем понимать как неограф, так и орграф.

Развернуть

Открыть в широком формате

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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