1. Основные понятия теории графов

Frage	Antworten
Неориентированный граф	Это совокупность множества вершин 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 вершинах	Image: 9f5bfddd-cda1-42ed-a39b-7400cfbc8acc.gif (image/gif)
Изоморфизм графов	Два графа называют изоморфными, если существует некоторое однозначное отображение вершин первого графа в вершины второго графа, которое сохраняет отношение смежности.
Непомеченный граф	Это класс эквивалентности - множество изоморфных друг другу графов.
Автоморфизм графа. Группа автоморфизмов	Автоморфизм - такая перестановка вершин графа, при которой он переходит сам в себя. Отражает симметрию графа. Множество автоморфизмов образует группу, называемую группой автоморфизмов.
Число способов разметки непомеченного графа	где G1 - какой-то помеченный граф Image: 85b80f19-bac1-4f27-8e0b-755da62d7487.gif (image/gif)
Турнир	Ориентированный граф, в котором каждая вершина соединена с каждой другой одним ребром
Понятие подграфа	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 ребро.
Минимально связный граф	Граф называется минимально связным, если при удалении любого ребра он перестаёт быть связным. Любой м.с.г. является деревом, а любое дерево - м.с.г.

Nächster

1. Основные понятия теории графов

Beschreibung

Zusammenfassung der Ressource

ähnlicher Inhalt

	Erstellt von Sergei Fomin vor fast 9 Jahre