Flashcards
1. Основные понятия теории графов
Cards in this deck (32)
- 1Неориентированный графЭто совокупность множества вершин V, множества рёбер E и отношения инцидентности I. I(e) = {x, y} (неупорядоченная пара вершин) для любого e в E.
- 2Степень вершиныКоличество рёбер, инцидентных данной вершине
- 3Изолированная вершинаВершина, степень которой равна 0
- 4k-регулярный графГраф, у которого степень всех вершин одинаковы и равна k
- 5Теорема о сумме степеней вершин графа. Следствие.Сумма степеней вершин графа равна удвоенному числу его рёбер. Следствие: в любом графе число вершин, имеющих нечётную степень, чётно.
- 6Простой неориентированный графНеориентированный граф без петель и мультирёбер.
- 7Полный граф и пустой граф. Дополнение графаПолный граф - граф, в котором каждая вершина связана с каждой.
Пустой граф - граф, в котором все вершины изолированы.
Дополнение графа - граф на тех же вершинах, при чём все рёбра, не входящие в исходный граф, входят в его дополнение. - 8Ориентированный графЭто совокупность множества вершин V, множества рёбер E и отношения инцидентности I. I(e) = (x, y) (упорядоченная пара вершин) для любого e в E.
- 9Входящая и исходящая степень вершиныВходящая степень - число рёбер, входящих в вершину. Исходящая степень - число рёбер, исходящих из вершины.
- 10Простой ориентированный графОрграф называется простым, если он не имеет петель, а также рёбер с одинаковой упорядоченной парой вершин.
- 11Понятие смежности в неориентированном и ориентированном графеВ неор. графе вершины x и y называются смежными, если существует ребро, соединяющее x и y.
В орграфе y называется смежной к x, если есть ребро, исходящее из x и входящих в y. - 12Задание графа в памяти компьютера1) Матрица смежности M, такая, что Mij равно числу рёбер, выходящих из i-го ребра и входящих в j-е.
2) Список смежности - для любой вершины задаётся мультимножество вершин, смежных с этой вершиной. - 13Количество простых неориентированных графов на n вершинах
- 14Изоморфизм графовДва графа называют изоморфными, если существует некоторое однозначное отображение вершин первого графа в вершины второго графа, которое сохраняет отношение смежности.
- 15Непомеченный графЭто класс эквивалентности - множество изоморфных друг другу графов.
- 16Автоморфизм графа. Группа автоморфизмовАвтоморфизм - такая перестановка вершин графа, при которой он переходит сам в себя. Отражает симметрию графа.
Множество автоморфизмов образует группу, называемую группой автоморфизмов. - 17Число способов разметки непомеченного графагде G1 - какой-то помеченный граф
- 18ТурнирОриентированный граф, в котором каждая вершина соединена с каждой другой одним ребром
- 19Понятие подграфаH является подграфом G, если:
V(H) ⊆ V(G)
E(H) ⊆ E(G)
∀e ∈ E(H) : {x, y} => e ∈ E(G) : {x, y}
Подграф можно получить, применяя к исходному графу операции удаления ребра и вершины. - 20Остовный подграфПодграф, получаемый из исходного графа только удалением рёбер
- 21Индуцированный подграфПодграф, полученный из исходного графа только удалением вершин
- 22Понятие маршрута и его длинаМаршрут - чередующаяся последовательность x0, e1, x1, ..., ek, xk, где xi ∈ V(G) и I(ei) = {x(i-1), xi}. Такой маршрут имеет длину k.
- 23Понятие пути в графе. Простой путьПуть - маршрут, в котором рёбра не повторяются.
Простой путь - путь, в котором вершины не повторяются. - 24Цикл и простой цикл в графеЦикл - путь, в котором начальная и конечная вершины совпадают.
Простой цикл - цикл, в котором вершины не повторяются (кроме первой, которая встречается дважды). - 25Связанность вершин в неориентированном графеВершины x и y называются связанными, если они соединены хотя бы одним путём.
- 26Компоненты связности в графе. Связный графКомпонента связности - набор вершин, каждая из которых связана со всеми остальными вершинами в этом наборе.
Граф связен, если у него всего одна компонента связности. - 27Связность вершин в орграфе. Сильно и слабо связный граф.В орграфе вершины x и y называются связанными, если есть хотя бы 1 путь из x в y и хотя бы один путь из y в x.
Граф сильно связен, если все его вершины связаны.
Граф слабо связен, если он был бы связным, будучи неориентированным. - 28Компонента сильной связности в орграфе. Граф компонент сильной связностиЭто набор вершин в орграфе, каждая из которых связана со всеми другими.
Г. к. с. с. - граф, в котором каждая вершина представляет компонент сильной связности исходного графа. Нет циклов. - 29Понятие дерева и леса. Лист.Дерево - простой связный граф без циклов.
Лес - простой граф без циклов. В общем случае состоит из нескольких деревьев.
Лист - вершина степени 1. - 30Число листов и число рёбер в дереве, построенном на n вершин.В любом дереве минимум 2 листа.
Число рёбер n-1. - 31Какой граф точно является деревом? Следствие.Простой связный граф, построенный на n вершинах и имеющий n-1 рёбер.
Следствие: любой связный граф, построенный на n вершинах, имеет как минимум n-1 ребро. - 32Минимально связный графГраф называется минимально связным, если при удалении любого ребра он перестаёт быть связным. Любой м.с.г. является деревом, а любое дерево - м.с.г.
Information
- Description
- Карточки по первой лекции курса "Основы теории графов" на stepic.org
- Created by
- Sergei Fomin
- Views
- 128
- Tags
- Rating