4282179
Beschreibung
Karteikarten von Sergei Fomin, aktualisiert more than 1 year ago
|
Erstellt von Sergei Fomin
vor fast 9 Jahre
|
|
| Frage | Antworten |
| Эйлеров цикл и эйлеров граф | Эйлеров цикл - цикл, проходящий по каждому ребру графа ровно 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. Эйлеров цикл в таком графе даёт последовательность де Брейна. |
Möchten Sie mit GoConqr kostenlos Ihre eigenen Karteikarten erstellen? Mehr erfahren.