Kolloc Flashcards
- Дерево(два определения)
- связный ациклический граф
- граф, любые две вершины которого соединены единственным простым путём
- связный граф, у которого вершин на одну меньше, чем рёбер
…
- Граф блоков-точек сочленения
двудольный граф, к одной доли которого относятся блоки графа, каждый из которых стянут в одну вершину, а к другой доли относятся все точки сочленения графа, при этом между точкой сочленения и стянутым блоком есть ребро, если точка сочленения принадлежала этому блоку
- Граф компонент рёберной двусвязности
граф, вершинами которого являются компоненты рёберной двусвязности исходного графа, соединённые мостами исходного графа
- Остов графа
частичный граф данного графа, являющийся деревом
- Цикломатическое число
число, показывающее, сколько рёбер надо удалить из графа, чтобы получился остов
- Фундаментальная система циклов
множество циклов графа, ассоциированное с остовом
- Минимальное остовное дерево графа
остов этого графа, обладающий минимальным суммарным весом рёбер
- Безопасное ребро
ребро, при добавлении которого к подграфу некого МСТ графа, граф остаётся подграфом некого МСТ этого графа, причём данное ребро не должно принадлежать изначальному подграфу МСТ
- Разрез, Ребро, пересекающее разрез
Разрез – разбиение множества вершин графа на два не пересекающихся подмножества.
Ребро, пересекающее разрез – ребро, один конец которого при разрезе принадлежит одному подмножеству вершин, а второй конец другому подмножеству
- Лемма о безопасном ребре
если взять такой разрез, что все вершины подграфа некоторого мст принадлежат одной части, то минимальное ребро, пересекающее этот разрез будет безопасным ребром
- Диаметр графа
максимальный эксцентриситет среди всех вершин графа, где эксцентриситет вершины – это кратчайшее расстояние в рёбрах до вершины, наиболее удалённой от данной
- Центр графа
множество всех вершин с минимальным эксцентриситетом
- Радиус графа
минимальный эксцентриситет среди всех вершин графа, где эксцентриситет вершины – это кратчайшее расстояние в рёбрах до вершины, наиболее удалённой от данной
- Теорема о поиске числа путей заданной длины по матрице смежности орграфа
число путей из iой вершины в jую длины L равно значению в ij ячейке матрицы смежности, возведённой в степень L
- Лемма о белых путях
запустим дфс на графе, назовём первым моментом времени, момент когда дфс выполнялся от некоторой вершины v, когда она окрашена в серый цвет, вторым моментом времени назовём момент, когда вершина v стала чёрной, тогда вершины графа кроме вершины v, которые были серые и чёрные к 1му моменту не изменят цвет ко второму моменту, а белые вершины либо останутся белыми, либо станут чёрными, причём Чёрными станут те, что были достижимы из v по белым путям
- Эйлеров путь
путь, единожды проходящий по каждому ребру графа
- Эквивалентные определения эйлерова графа
- граф, содержащий Эйлеров цикл
- граф, любая вершина которого имеет чётную степень
- граф, множество всех рёбер которого можно разбить на циклы
- Теорема о покрытии рёбер графа путями
если в графе 2N вершин имеют нечётную степень, то этот граф можно покрыть N рёберно-простыми путями
- Критерий эйлеровости
граф Эйлеров тогда и только тогда, когда:
- все вершины графа имеют чётную степень
- все компоненты связности кроме, (может быть)? одной, не содержат рёбер
- Произвольно вычерчиваемый граф
- Граф называется произвольно вычерчиваемым из вершины v, если любая цепь с началом в v может быть продлена до эйлерова цикла данного графа
- Гамильтонов путь
путь, единожды проходящий через каждую вершину графа
- Теорема Оре
если в неориентированном графе не меньше 3 вершин и для любых двух различных несмежных вершин выполняется то, что сумма их степеней не меньше количества вершин, то данный граф гамильтонов
- Теорема Дирака
если в неориентированном графе не меньше 3 вершин и минимальная степень его вершин не меньше количества вершин, делённого на два, то граф гамильтонов
- Теорема Гуйя-Ури
если в сильно связанном ориентированном графе для каждой вершины её степени входа и выхода не меньше числа вершин, делённого на два, то граф гамильтонов
- Сочетание
Сочетание из n по m – набор размера m из n элементов
- Размещение
Размещение из n по m – упорядоченная последовательность длины m из n элементов
- Перестановка
Перестановка - переупорядочение набора объектов или функция его задающая
- Отличие перестановок и размещений
размещения кроме порядка объектов, могут отличаться набором этих объектов
- Принцип Дирихле
если поместить n + 1 объект в n контейнеров, то по крайней мере в одном контейнере будет более одного объекта
- Кратчайший путь
путь с наименьшей возможной суммой весов рёбер
- Транспортная сеть
ориентированный граф, где каждое ребро данного графа имеет пропускную способность, большую нуля, и нет антипараллельных рёбер; если данное ребро не входит в граф, его пропускная способность полагается равной 0
- Поток
функция, которая возвращает рациональное значение для пары вершин сети и удовлетворяет условиям:
- Ограничение пропускной способности, т.е. для любой пары вершин в сети поток между ними не меньше 0 и не больше пропускной способности
- Сохранение потока, т.е. для любой вершины, кроме начальной и конечной, суммарный поток выходящий из неё будет равен суммарному потоку в неё входящему
- Величина потока
разность суммарного потока, который вытекает из стартовой вершины и суммарного потока, который в неё втекает
- Остаточная сеть
сеть, состоящая из тех же вершин, что и исходная сеть и из рёбер, через которые можно допустить поток
- Увеличивающий путь
простой путь из истока в сток в остаточной сети
- Минимальный разрез сети
разрез с минимально возможной пропускной способностью
- Паросочетание в двудольном графе
произвольное подмножество рёбер двудольного графа, такое что никакие два ребра не смежны
- Конденсация графа
орграф граф, вершинами которого служат компоненты сильной связности исходного графа, а дуга между ними присутствуют только когда в исходном графе существует хотя бы одна дуга между вершинами, входящими в эти компоненты связности
- Топологическая сортировка
упорядочивание вершин ориентированного ацикличного графа такое, что если есть дуга из v в u, то номер вершины v меньше номера вершины u
- Префикс-функция
максимальный по длине собственный префикс строки, являющийся её суффиксом
