[Править] р

• Радиус графа — минимальный из эксцентриситетов вершин связного графа; вершина, на которой достигается этот минимум, называется центральной вершиной.

• Разбиение графа — представление исходного графа в виде множества подмножеств вершин по определенным правилам.

• Разделяющая вершина — то же, что и шарнир.

• Развёртка графа — функция, заданная на вершинах ориентированного графа.

• Размеченный граф — граф, для которого задано множество меток S, функция разметки вершин f : A → S и функция разметки дуг g : R → S. Графически эти функции представляются надписыванием меток на вершинах и дугах. Множество меток может разделяться на два непересекающихся подмножества меток вершин и меток дуг.

• Разрез — множество ребер, удаление которого делает граф несвязным.

• Раскраска графа — разбиение вершин на множества (называемые цветами). Если при этом нет двух смежных вершин принадлежащих одному и тому же множеству (то есть две смежные вершины всегда разного цвета), то такая раскраска называется правильной.

• Расстояние между вершинами — длина кратчайшей цепи (в орграфе пути), соединяющей заданные вершины. Если такой цепи (пути) не существует, расстояние полагается равным бесконечности.

• Ребро — базовое понятие. Ребро соединяет две вершины графа.

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

  • Регулярный граф степени 0 (вполне несвязный граф, пустой граф, нуль-граф) — граф без рёбер.

[Править] с

• Самодвойственный граф — граф, изоморфный своему двойственному графу.

• Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.

• Связный граф — граф, в котором все вершины связаны.

• Сечение графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть тривиальным графом.

• Сеть — в принципе, то же, что и граф, хотя сетями обычно называют графы, вершины которых определённым образом помечены.

  • Ориентированная сеть — ориентированный граф, не содержащий контуров.

• Сильная связность. Две вершины в ориентированном графе сильно связаны, если существует путь из первой во вторую и из второй в первую.

  • Сильно связный орграф — орграф, в котором все вершины сильно связаны.

• Смежность — понятие, используемое в отношении только двух рёбер либо только двух вершин: Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. (ср. Инцидентность.)

• Смешанный граф — граф, содержащий как ориентированные, так и неориентированные рёбра.

• Спектр графа — множество всех собственных значений матрицы смежности с учётом кратных рёбер.

• Степень вершины — количество рёбер графа G, инцидентных вершине x. Обозначается . Минимальная степень вершины графа G обозначается . а максимальная — .

• Стягивание ребра графа — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Граф стягиваем к , если второй можно получить из первого последовательностью стягиваний рёбер.

• Суграф (частичный граф) исходного графа — граф, содержащий все вершины исходного графа и подмножество его рёбер. (ср. Подграф.)

[править] Т

• Тождественный граф — граф, у которого возможен один единственный автоморфизм — тождественный. Образно говоря, тождественный граф — это «абсолютно несимметричный» граф.

• Точка сочленения — то же, что и шарнир.

• Триангуляция поверхности — укладка графа на поверхность, разбивающая её на треугольные области; частный случай топологической триангуляции.

• Тривиальный граф — граф, состоящий из одной вершины.

• Турнир — ориентированный граф, в котором каждая пара вершин соединена одним ребром.

[править] У

• Узел — то же, что и Вершина.

• Укладка: граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы рёбра графа при этом не пересекались. (См. Планарный граф, Плоский граф.)

• Упорядоченный граф — граф, в котором рёбра, выходящие из каждой вершины, однозначно пронумерованы, начиная с 1. Рёбра считаются упорядоченными в порядке возрастания номеров. При графическом представлении часто рёбра считаются упорядоченными в порядке некоторого стандартного обхода (например, против часовой стрелки).

[править] Ф

• n-Фактор графа — регулярный остовный подграф степени .

• n-Факторизация графа — разбиение графа на независимые n-факторы.

[править] Х

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

[править] Ц

• Центр графа — множество вершин , для которых справедливо равенство: , где — это эксцентриситет вершины, а — радиус графа.

• Цепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной). В цепи вершины и называются концами цепи. Цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v обозначается . Для орграфов цепь называется орцепью.

В некоторых источниках простая цепь — цепь, рёбра которой различны, что является более слабым условием.

• Цикл — замкнутая цепь. Для орграфов цикл называется контуром.

  • Цикл (простой цикл) в орграфе — это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.

  • Цикл Гамильтона — то же, что и Гамильтонов цикл.

• Цикломатическое число графа — минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим. Для связного графа существует соотношение: где — цикломатическое число, — число компонент связности графа, — число рёбер, а — число вершин.

[править] Ч

• Частичный граф — то же, что и суграф.

• Чётный граф — то же, что и двудольный граф.

[править] Ш

• Шарнир — вершина графа, в результате удаления которой вместе со всеми инцидентными ей рёбрами количество компонент связности в графе возрастает.

[править] Э

• Эйлеров граф — это граф, в котором существует цикл, содержащий все рёбра графа по одному разу (вершины могут повторяться).

• Эйлерова цепь (или Эйлеров цикл) — это цепь (цикл), которая содержит все рёбра графа (вершины могут повторяться).

• Эксцентриситет вершины — максимальное из расстояний от данной вершины до других вершин.

• Элементарный путь — путь, вершины которого, за исключением, быть может, первой и последней, различны. Другими словами, простой путь не проходит дважды через одну вершину, но может начаться и закончиться в одной и той же вершине, в таком случае он называется циклом (элементарным циклом).

• Элементарным стягиванием называется такая процедура: берем ребро (вместе с инцидентными ему вершинами, например, u и v) и «стягиваем» его, то есть удаляем ребро и отождествляем вершины u и v. Полученная при этом вершина инцидентна тем ребрам (отличным от), которым первоначально были инцидентны u или v.

[править] Ссылки

• Толковый словарь по теории графов

• Теория графов

[править] Литература

• Харари Ф. Теория графов. — М.: УРСС, 2003. — 300 с. — ISBN 5-354-00301-6

Источник — «http://ru.wikipedia.org/w/index.php?title=Глоссарий_теории_графов&oldid=48675638»

Категории:

• Глоссарии

• Теория графов

• Дискретная математика

Скрытые категории:

• Википедия:Нет источников с мая 2009

• Википедия:Статьи с утверждениями без источников более 14 дней

Персональные инструменты

• Создать учётную запись

• Представиться системе

Пространства имён

• Статья

• Обсуждение

Варианты

Просмотры

• Читать

• Правка

• История

Действия

Поиск

Начало формы

Конец формы

Навигация

• Заглавная страница

• Рубрикация

• Указатель А — Я

• Избранные статьи

• Случайная статья

• Текущие события

Участие

• Сообщить об ошибке

• Портал сообщества

• Форум

• Свежие правки

• Новые страницы

• Справка

• Пожертвования

Печать/экспорт

• Создать книгу

• Скачать как PDF

• Версия для печати

Инструменты

• Ссылки сюда

• Связанные правки

• Спецстраницы

• Постоянная ссылка

• Сведения о странице

• Цитировать страницу

На других языках

• Boarisch

• Català

• Deutsch

• English

• Esperanto

• Español

• Français

• עברית

• Magyar

• Italiano

• 한국어

• Português

• Română

• ไทย

• Українська

• Tiếng Việt

• Последнее изменение этой страницы: 02:51, 4 октября 2012.

• Текст доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия. Подробнее см. Условия использования. Wikipedia® — зарегистрированный товарный знак некоммерческой организации Wikimedia Foundation, Inc.