Документ Microsoft Word. Дерево (2 определения). ппэйло
 Скачать 22.44 Kb.
|
|
Дерево (2 определения).ппэйло Связный ациклический граф. Граф, в котором любые вершины u и v соединены единственным простым путём. Граф блоков и точек сочленения. Граф, в котором блоки и точки сочленения исходного графа являются вершинами. Если в исходном графе данная точка сочленения принадлежит данному блоку, то в полученном графе между соответствующими им вершинами будет ребро. Граф компонент реберной двусвязности. Связный граф, где компоненты реберной двусвязности сжаты в виде вершин и соединены мостами исходного графа. Остов графа. Дерево, включающее все вершины графа, являющееся при этом его подграфом. Цикломатическое число Сколько ребер нужно удалить, чтобы получился остов. (= ЧИСЛО КОМПОНЕНТ СВЯЗНОСТЬ + ЧИСЛО РЕБЕР - ЧИСЛО ВЕРШИН) Цикл, ассоциированный с остовом Это цикл полученный при помощи добавления к остову одного ребра исходного графа(которое было удалено при получении остова). Фундаментальная система циклов - множество циклов графа, ассоциированных с остовом - множество фундаментальных циклов графа, где фундаментальный цикл - цикл, полученный добавлением к остову ребра исходного графа, не принадлежащего остову. Минимальное остовное дерево Остов, в котором сумма весов ребер минимально возможная. Безопасное ребро! Ребро, при добавлении которого в подграф MST получится подграф MST. (ребро, содержащееся во множестве ребер MST, но не проведенное в данном подграфе MST) Разрез - разбиение множества вершин графа на 2 непересекающихся множества. Ребро, пересекающее разрез - ребро графа, концы которого принадлежат разным множествам вершин, а образованным в результате разреза. Лемма о безопасном ребре (суть) Суть: ребро минимального веса среди ребер, пересекающих разрез, является безопасным. Формулировка: В собственном подграфе MST исходного графа существует такой разрез, при котором ни одно ребро данного подграфа его не пересекает. Тогда ребро исходного графа минимального веса, пересекающее этот разрез будет безопасным для данного подграфа MST исходного графа. *MST - минимальное остовное дерево. Расстояние между двумя вершинами графа. Длина кратчайшего пути между этими вершинами. Диаметр графа Наибольшее расстояние между всеми парами вершин графа. Центр графа Множество вершин, максимальное расстояние от которых до всех остальных вершин минимально. Радиус графа. Минимальный эксцентриситет среди всех вершин графа. Кратчайший путь между двумя вершинами. Путь сумма весов ребер которого - минимально возможная. Теорема о поиске числа путей заданной длины по матрице смежности орграфа. - Ячейка mij матрицы смежности орграфа, возведенной в степень k покажет количество путей длины k от i до j вершины. Лемма о белых путях Не существует такого момента выполнения поиска в глубину, в который бы существовало ребро из черной вершины в белую. Пусть в процессе выполнения процедуры dfs нашлось ребро из черной вершины v в белую вершину u. Рассмотрим момент времени, когда мы запустили dfs(v). В этот момент вершина v была перекрашена из белого в серый, а вершина u была белая. Далее в ходе выполнения алгоритма будет запущен dfs(u), поскольку обход в глубину обязан посетить все белые вершины, в которые есть ребро из v. По алгоритму вершина v будет покрашена в черный цвет тогда, когда завершится обход всех вершин, достижимых из нее по одному ребру, кроме тех, что были рассмотрены раньше нее. Таким образом, вершина v может стать черной только тогда, когда dfs выйдет из вершины u, и она будет покрашена в черный цвет. Получаем противоречие. Эйлеров путь Путь, проходящий по всем ребрам графа и притом по одному разу. Отличие эйлерова и полуэйлерова графов Эйлеров граф - граф содержащий Эйлеров цикл, полуэйлеров граф - граф содержащий Эйлеров путь, но не содержащий Эйлеров цикл. Эквивалентные определения эйлерова графа Граф G - эйлеров, если любая вершина G имеет четную степень. Граф G - эйлеров, если множество всех ребер графа G можно разбить на циклы. Теорема о покрытии ребер графа путями Граф G, в котором 2N вершин имеют нечетную степень, можно покрыть N реберно простыми путями. (“покрыть” подразумевает, что все пути рёберно не пересекаются) Критерий эйлеровости (должны выполняться одновременно) Все вершины графа имеют четную степень. Все компоненты связности кроме одной не содержат ребер. Произвольно вычерчиваемый граф G - произвольно вычерчиваемый из вершины v, если любая цепь с началом в v может быть продлена до эйлерова цикла графа G. Теорема о произвольно вычерчиваемости G - неодноэлементный эйлеров граф произвольно вычерчиваем из v, тогда и только тогда, когда v принадлежит всем циклам графа G. Гамильтонов путь Путь, проходящий через все вершины графа и притом по одному разу. Теорема Оре Если в неориентированном графе больше 2х вершин, и сумма степеней любых двух несмежных вершин больше или равна количеству вершин графа, то такой граф гамильтонов. Теорема Дирака - если в неориентированном графе n вершин, n > 2, и у каждой вершины степень больше либо равно n/2, то такой граф гамильтонов. Теорема Гуйя-Ури - если в ориентированном сильно связном графе степень входа и степень выхода каждой вершины >= n/2, где n - количество вершин графа, то такой граф гамильтонов. Для любого ли гамильтонова графа будут выполняться условия теорем о гамильтоновости и почему? Эти теоремы являются достаточными условиями, но не необходимыми. То есть, если какая-то из теорем выполняется – граф гамильтонов, но какая-то из теорем (Или даже все) могут не выполняться, но граф всё равно будет гамильтонов Определение сочетания (не формулой) Неупорядоченный набор из k элементов, выбранных из множества n элементов. Определение размещения (не формулой). Упорядоченный набор из k элементов, выбранных из множества n элементов. Определение перестановки (не формулой) С лекции Булановой: переупорядочение набора объектов или формула его задающая (подразумевается что изначальный набор упорядоченный) Отличие перестановок и размещений. в случае перестановок изменяется порядок расположения элементов набора. в случае размещений изменяется и порядок расположения элементов, и сами элементы набора. перестановки могут совпадать с размещениями в случае n = k: количество способов выбрать все элементы множества и упорядочить их = количество способов изменить порядок расстановки n элементов. Принцип Дирихле Если m объектов поместить в n контейнеров (m > n), то хотя бы в одном контейнере будет находится не менее m/n объектов (с округлением в большую сторону), и хотя бы в одном контейнере будет находится не более m/n объектов (с округлением в меньшую сторону) или Если m объектов поместить в n контейнеров (m > n), то хотя бы в одном контейнере будет находится более 1 объекта. Принцип сложения Если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то выбрать A или B можно n + m способами. Принцип умножения Если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n·m способами Принцип включения-исключения Принцип сложения с возможностью пересечения множеств Лексикографический порядок на строках Строка А лексикографически меньше строки B, если выполняется одно из 2 условий: строка А является собственным префиксом строки B Найдется k-й элемент в А такой, что все символы в А и В до k-го равны, а Ak |