4268504
Description
Flashcards by Sergei Fomin, updated more than 1 year ago
|
Created by Sergei Fomin
almost 9 years ago
|
|
| Question | Answer |
| Неориентированный граф | Это совокупность множества вершин V, множества рёбер E и отношения инцидентности I. I(e) = {x, y} (неупорядоченная пара вершин) для любого e в E. |
| Степень вершины | Количество рёбер, инцидентных данной вершине |
| Изолированная вершина | Вершина, степень которой равна 0 |
| k-регулярный граф | Граф, у которого степень всех вершин одинаковы и равна k |
| Теорема о сумме степеней вершин графа. Следствие. | Сумма степеней вершин графа равна удвоенному числу его рёбер. Следствие: в любом графе число вершин, имеющих нечётную степень, чётно. |
| Простой неориентированный граф | Неориентированный граф без петель и мультирёбер. |
| Полный граф и пустой граф. Дополнение графа | Полный граф - граф, в котором каждая вершина связана с каждой. Пустой граф - граф, в котором все вершины изолированы. Дополнение графа - граф на тех же вершинах, при чём все рёбра, не входящие в исходный граф, входят в его дополнение. |
| Ориентированный граф | Это совокупность множества вершин V, множества рёбер E и отношения инцидентности I. I(e) = (x, y) (упорядоченная пара вершин) для любого e в E. |
| Входящая и исходящая степень вершины | Входящая степень - число рёбер, входящих в вершину. Исходящая степень - число рёбер, исходящих из вершины. |
| Простой ориентированный граф | Орграф называется простым, если он не имеет петель, а также рёбер с одинаковой упорядоченной парой вершин. |
| Понятие смежности в неориентированном и ориентированном графе | В неор. графе вершины x и y называются смежными, если существует ребро, соединяющее x и y. В орграфе y называется смежной к x, если есть ребро, исходящее из x и входящих в y. |
| Задание графа в памяти компьютера | 1) Матрица смежности M, такая, что Mij равно числу рёбер, выходящих из i-го ребра и входящих в j-е. 2) Список смежности - для любой вершины задаётся мультимножество вершин, смежных с этой вершиной. |
| Количество простых неориентированных графов на n вершинах | |
| Изоморфизм графов | Два графа называют изоморфными, если существует некоторое однозначное отображение вершин первого графа в вершины второго графа, которое сохраняет отношение смежности. |
| Непомеченный граф | Это класс эквивалентности - множество изоморфных друг другу графов. |
| Автоморфизм графа. Группа автоморфизмов | Автоморфизм - такая перестановка вершин графа, при которой он переходит сам в себя. Отражает симметрию графа. Множество автоморфизмов образует группу, называемую группой автоморфизмов. |
| Число способов разметки непомеченного графа | где G1 - какой-то помеченный граф |
| Турнир | Ориентированный граф, в котором каждая вершина соединена с каждой другой одним ребром |
| Понятие подграфа | H является подграфом G, если: V(H) ⊆ V(G) E(H) ⊆ E(G) ∀e ∈ E(H) : {x, y} => e ∈ E(G) : {x, y} Подграф можно получить, применяя к исходному графу операции удаления ребра и вершины. |
| Остовный подграф | Подграф, получаемый из исходного графа только удалением рёбер |
| Индуцированный подграф | Подграф, полученный из исходного графа только удалением вершин |
| Понятие маршрута и его длина | Маршрут - чередующаяся последовательность x0, e1, x1, ..., ek, xk, где xi ∈ V(G) и I(ei) = {x(i-1), xi}. Такой маршрут имеет длину k. |
| Понятие пути в графе. Простой путь | Путь - маршрут, в котором рёбра не повторяются. Простой путь - путь, в котором вершины не повторяются. |
| Цикл и простой цикл в графе | Цикл - путь, в котором начальная и конечная вершины совпадают. Простой цикл - цикл, в котором вершины не повторяются (кроме первой, которая встречается дважды). |
| Связанность вершин в неориентированном графе | Вершины x и y называются связанными, если они соединены хотя бы одним путём. |
| Компоненты связности в графе. Связный граф | Компонента связности - набор вершин, каждая из которых связана со всеми остальными вершинами в этом наборе. Граф связен, если у него всего одна компонента связности. |
| Связность вершин в орграфе. Сильно и слабо связный граф. | В орграфе вершины x и y называются связанными, если есть хотя бы 1 путь из x в y и хотя бы один путь из y в x. Граф сильно связен, если все его вершины связаны. Граф слабо связен, если он был бы связным, будучи неориентированным. |
| Компонента сильной связности в орграфе. Граф компонент сильной связности | Это набор вершин в орграфе, каждая из которых связана со всеми другими. Г. к. с. с. - граф, в котором каждая вершина представляет компонент сильной связности исходного графа. Нет циклов. |
| Понятие дерева и леса. Лист. | Дерево - простой связный граф без циклов. Лес - простой граф без циклов. В общем случае состоит из нескольких деревьев. Лист - вершина степени 1. |
| Число листов и число рёбер в дереве, построенном на n вершин. | В любом дереве минимум 2 листа. Число рёбер n-1. |
| Какой граф точно является деревом? Следствие. | Простой связный граф, построенный на n вершинах и имеющий n-1 рёбер. Следствие: любой связный граф, построенный на n вершинах, имеет как минимум n-1 ребро. |
| Минимально связный граф | Граф называется минимально связным, если при удалении любого ребра он перестаёт быть связным. Любой м.с.г. является деревом, а любое дерево - м.с.г. |
Want to create your own Flashcards for free with GoConqr? Learn more.