4282179
Description
Flashcards by Sergei Fomin, updated more than 1 year ago
|
Created by Sergei Fomin
almost 9 years ago
|
|
| 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. Эйлеров цикл в таком графе даёт последовательность де Брейна. |
Want to create your own Flashcards for free with GoConqr? Learn more.