2. Циклы в графах

Description

Карточки по второй лекции курса "Основы Теории Графов" на stepic.org
Sergei Fomin
Flashcards by Sergei Fomin, updated more than 1 year ago
Sergei Fomin
Created by Sergei Fomin about 8 years ago
15
0

Resource summary

Question Answer
Эйлеров цикл и эйлеров граф Эйлеров цикл - цикл, проходящий по каждому ребру графа ровно 1 раз. Эйлеров граф - граф, содержищий Эйлеров цикл.
Необходимое и достаточное условие существования Эйлерова цикла Каждая вершина в графе должна иметь чётную степень.
Гамильтонов цикл и путь Цикл, проходящий все вершины графа ровно 1 раз, называется Гамильтоновым. Путь, проходящий каждую вершину графа ровно 1 раз, называется Гамильтоновым.
Теорема о преобразовании Гамильтонова пути в цикл Если в графе существует Гамильтонов путь x1 -> xn, x1 не смежна с xn и deg(x1) + deg(xn) >= n, то существует и Гамильтонов цикл.
Теорема о максимальном пути и цикле Если P = x1, ..., xk - простой путь максимальной длины в графе, то из этого пути можно сделать простой цикл, если x1 смежна с xk, либо если deg(x1) + deg(xk) >= k
Теорема Оре Пусть G - простой граф на n > 2 вершинах. Пусть для любых двух не смежных вершин сумма их степеней больше или равна n-1. В таком графе точно существует Гамильтонов путь.
Следствия из теоремы Оре 1) Если deg(x) + deg(y) для любых x, y >= n, то в графе есть Гамильтонов цикл. 2) Если степень любой вершины >= (n-1)/2, то в графе есть Гамильтонов путь. Если deg(x) >= n/2, то Гамильтонов цикл.
Последовательность де Брейна Это циклическая последовательность символов n-элементного алфавита, такая, что в ней встречаются все возможные на данном алфавите k-меры. Для любых n и k существует последовательность де Брейна длинной n^k.
Граф де Брейна с Гамильтоновым циклом Это граф, в котором каждый k-мер - вершина, а ребро - символ алфавита. Гамильтонов цикл в таком графе даёт последовательность де Брейна.
Граф де Брейна с Эйлеровым циклом Это граф, в котором каждое ребро соответствует определённому k-меру, а вершина - суффиксу длины k-1. Эйлеров цикл в таком графе даёт последовательность де Брейна.
Show full summary Hide full summary

Similar

3. Связность в графах
Sergei Fomin
4. Связность в графах (ч. 2)
Sergei Fomin
7. Раскраска графов
Sergei Fomin
8. Планарные графы
Sergei Fomin
5. Паросочетания в графах
Sergei Fomin
6. Паросочетания в графах (ч. 2)
Sergei Fomin
1. Основные понятия теории графов
Sergei Fomin
Деление двузначного числа на двузначное
Эльвира Шемякина
Доли и дроби
Татьяна Иващенко
Тест 1- събиране и изваждане на числата до 6
Светла Събева
Събиране и изваждане до 6
Светла Събева