4431
правка
Связность графа: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
Нижние границы для k-связных остовных подграфов | Нижние границы для k-связных остовных подграфов | ||
Каждая вершина k-связного графа имеет по меньшей мере k инцидентных ей дуг. Следовательно, сумма степеней всех его вершин составляет по меньшей мере kn, где n – количество вершин графа. Поскольку в эту сумму каждое ребро входит дважды, мощность множества ребер составляет не менее kn/2. Назовем ее нижней границей степени. Несколько расширив эту идею, мы получим более сильную нижнюю границу мощности k-связного остовного подграфа исходного графа. Пусть | Каждая вершина k-связного графа имеет по меньшей мере k инцидентных ей дуг. Следовательно, сумма степеней всех его вершин составляет по меньшей мере kn, где n – количество вершин графа. Поскольку в эту сумму каждое ребро входит дважды, мощность множества ребер составляет не менее kn/2. Назовем ее нижней границей степени. Несколько расширив эту идею, мы получим более сильную нижнюю границу мощности k-связного остовного подграфа исходного графа. Пусть <math>D_k \;</math> – подграф, у которого каждая вершина имеет степень не меньше k. В отличие от k-связного подграфа, <math>D_k \;</math> не имеет ограничений по связности. Согласно вышеприведенному рассуждению, <math>D_k \;</math> имеет не менее kn/2 ребер. Сведя задачу к задаче паросочетания, мы сможем вычислить <math>D_k \;</math> минимальной мощности за полиномиальное время; этот вариант будет называться нижней границей по паросочетанию. | ||
