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

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

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

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

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

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

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

Теорема 14.1. Для неографа G с n вершинами без петель следующие условия эквивалентны:

1) G – дерево;

2) G – связной граф, содержащий n – 1 ребро;

3) G – ациклический граф, содержащий n – 1 ребро;

4) Любые две несовпадающие вершины графа G соединяет единственная цепь;

5) G – ациклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.

Теорема 14.2. Неограф G является лесом тогда и только тогда, когда коранг графа v(G)=0.

Висячая вершина в дереве – вершина степени 1. Висячие вершины называются листьями, все остальные – внутренними вершинами.

Если в дереве особо выделена одна вершина, называемая корнем, то такое дерево называется корневым, иначе – свободным.

Корневое дерево можно считать орграфом с ориентацией дуг из корня или в корень. Очевидно, что для любой вершины корневого дерева, кроме корня, . Для корня , для листьев .

Вершины дерева, удаленные на расстояние k (в числе дуг) от корня, образуют k-й ярус (уровень) дерева. Наибольшее значение k называется высотой дерева.

Если из какой-либо вершины корневого дерева выходят дуги, то вершины на концах этих дуг называют сыновьями (в английской литературе – дочери (daughter)).

Развернуть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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